Learning latent causal graphs via mixture oracles
Authors: Bohdan Kivva
Goutham Rajendran
Pradeep Kumar Ravikumar
Bryon Aragam
Venue: NeurIPS 2021 Poster (2021)
Keywords: causal graphical models
latent variables
mixture model
algorithms

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.

Learning latent causal graphs via mixture oracles
Bohdan Kívva University Chicago bki Mkivvuuuchicago.ooo edu
Goutham Rajendran University of Chicago
Pradeep Ravikumar Carnegie Mellon University pradeepr@cs cmu edu
goutham@uchicago edu
Bryon Aragam University of Chicago bryon@chicaggbootta edu
Abstract
We study the problem of reconstructing causal graphical model from data in the presence 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 observa- tions (e.g. pixels in image) is much less relevant than the dependence between certain high-level, latent features (e.g. concepts or objects), and this is the setting interest. We provide conditions under which both the latent representations and the underlying latent causal model are identifiable by reduction to a mixture oracle. These results highlight an intriguing connection between the well-studied problem of learning the order of 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.
Introduction
Understanding causal relationships between objects and/or concepts is component of human reasoning, and by extension, a core component of artificial intelligence [40 53) Causal relationships robust perturbations, encode invariances in system, and enable agents reason effectively about the effects of their actions in an environment. Broadly speaking, the problem of inferring causal relationships can be broken down into main steps: 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 the problem of learning causal representations [63]. This problem should be contrasted with the equally important problem of causal inference the presence of latent confounders [e.g. 18 35
72 see also Remark 2.1
Causal graphical models 53 used model causal systems with hidden variables 26 588 [59]. It is well-known that in general, without additional assumptions, causal graphical model given by directed acyclic graph (DAG) identifiable in the presence of latent variables [e.g.. [3) 71. In fact, this is generic property of nonparametric structural models: Without assumptions, identifiability is impossible, however, given enough structure, identifiability can be rescued. Examples this phenomenon include linearity
provide a natural framework for this problem, and have long been
3 6 [5] 28 78), independence [[ [0] 78 rank [1 28 sparsity [6], and graphical constraints
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

In this paper, we consider 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-gived access only to the observed data-and and learning the parameters of finite mixture model. This observation leads to new identifiability conditions and algorithms for learning causal models with latent structure.
Overview
Our starting point is 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(H)) over the hidden variables H, and
3. A directed acyelic graph (DAG) A over the latent distribution.
From here, the crucial observation is to reduce the recovery problems for I' and P(H) to the problem of learning a finite mixture over the observed data. The latter is 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 G is iden- tifiable (Thcorem 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) 4 We carefully analyze the problem of reconstructing I under progressively weaker assumptions: First, we derive a brute-force algorithm that identifies I' 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 's algorithm (Theorem 4.8).
3. (Section 5) Building 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 PHH) from observed data (Theorem 5.4..
4. (Section 7 We implement these algorithms 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 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 Friedman et al. (27). Martin and LanLehn
this problem includes seminal work by Elidan et al. 22
[7]] More recent work has focused on linear models 3
28
68
78 or known structure [2]] 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 Causal 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

---

H1
H2
H1
H2
H3
Hi
X1
X2
X1
X2
X1
X2
X3
(a) A single hidden (b) Two
independent
hidden
(c) Three dependent hidden states.
state.
states.
Figure Illustration of the basic model. Note that there are no edges between observed variables or edges oriented from observed to hidden. (a) A latent variable model with single hidden state; i.c a mixture model. (b)-(c) Two examples of latent variable models with more complicated hidden structure.
review, we were made aware the recent work 46 that studies a similar problem to ours general, nonlinear setting under faithfulness assumptions. It is also worth noting recent progress on learning discrete Boltzmann machines [1] which can be interpreted as an Ising model with bipartite structure and a single hidden layer- in particular, there is 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 variety of other applications including latent Dirichlet allocation g 9. phylogenetics [51 [4
and hidden
Markov models 2 30).
prevailing theme the causal inference literature has been negative results asserting that in
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 discrete and well-separated identifiability and exact recovery of latent causal relationships is indeed possible. This optimistic approach is implicit in recent progress visual relationship detection [52], causal feature learning this spirit, our work provides theoretical grounding for
[14 43), and interaction modeling 37 41
some of these ideas.
Mixture models and clustering While our theoretical results in Sections 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 assumptions. Although much is known about parametric models [e.g. [2]. 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, grouped observations [60 75 and general nonparametric mixtures (66. In each of these cases, mixture oracle be implemented without parametric assumptions. In practice, we use clustering algorithms such as K-means or hierarchical clustering to implement this oracle. We
be learned under variety of parametric and nonparametric
also that the specific problem of consistently estimating the order of mixture model, which will be of particular importance in the sequel, has been the subject of intense scrutiny
the statistics literature [c.g. [6 19
39 45
Broader impacts and societal impact Latent variable models have numerous practical applica- tions. 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 an important problem, and our results shed light on when this and isn't possible.
2 Background
Let G (V, E) be DAG with V VV(XH,, where X E Bh denotes the observed part and H E Ω = Q ... x Ωtm denotes the hidden, latent, part. Throughout this paper, we assume that each Q is a discrete space with [[2 > 2. We assume further that there are edges between

---

observed variables and no edges from observed to hidden variables, and that the distribution of V satisfies the Markov property with respect to G' (see the supplement for definitions). Under these assumptions, G decomposes as the union of two subgraphs G r U A, where I is directed, a DAG over the latent variables H. Similar assumptions have appeared in previous work K 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 [4].
bipartite graph of edges pointing from H to X, and
See Figure | for examples.
Throughout this paper, we use standard notation such as pa(j) for parents, ch(j) for children, and ne(j) for neighbors. Given subset V C V. pa(V") := UjeV pa(j) and given a subgraph G' G. pag (V') = pa(V")nG with similar notation for children and neighbors. We let E {0, 1) denote the adjacency matrix of I and denote its columns by dj E {0, (0,1)
Remark 2.1. Our goal is learn the hidden variables H and the causal graph between them, defined above by A. To accomplish this, our main result (Theorem 3.2) shows how to identify (HH)) from which A can be recovered (see Section for details). It is important to contrast this problem with problems involving latent confounders (e.g. 3 [8] 35 68 [72]. where the goal is to learn the causal graph between the observed variables X. In our setting, there are no edges between the observed variables.
2.1 Assumptions
It is well-known that without additional assumptions, the latent variables H cannot be identified from X, let alone the DAG A. For example, we can always replace a pair of distinct hidden variables H, and H, with single hidden variable Ho that takes values in Q4 S2, 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 H4 + H3 have ner (H;) o ner (Hz)-
Assumption 2.3 (Maximality). There is no DAG G' = ((X, H'), E') such that:
1. PPX, Markov with respect to G';
from 2. G' is obtained from G by splitting a hidden variable (equivalently, G is obtained from G' by merging pair of vertices);
3. G' satisfies Assumption 2.2
These assumptions are necessary for the recovery of A in the sense that, without these assumptions, latent variables can be created destroyed without changing the observed distribution P(X). Infor- mally, the maximality assumption says that there are several DAGs that are Markov with respect to the given distribution, we make a mild assumption on the probabilities, in order to avoid degenerate cases where certain configurations of the latent variables have zero probability:
interested in recovering the most informative among them. Finally,
Assumption 2.4 (Nondegeneracy). The distribution over V = (X, H) satisfies:
(a) PHH = h) > for all h E Q2 x... x Okk-
(b) For all c X and a + b, pa()) = a) & IPS) (S))) = b). where a and are distinct configurations of pS(
Without this nondegeneracy condition, cannot be identified; see the supplement for details.
2.2
Mixture oracles
Let S C X be a subset of the observed variables. We can always write the marginal distribution P(S)
as
PP(S)
Σ = -= h).

---

When S = X, this can be interpreted as mixture model with K := |92] components. When S S X, however, multiple components can "collapse" onto the same component, resulting mixture with fewer than K components. Let k(S) denote this number, so that we may define discrete random variable Z with k(S) states such that for all j E [k(()),, we have
M(S)
M(S)
P(S) P(
-= Σ ((S.))
(S)() C(S5)
Then j) is the weight of the jth mixture component over S, and C(S, is the corresponding jth component. It turns out that these probabilities precisely encode the conditional independence structure of H. To make this formal, we define the following oracle:
Definition 2.5. A mixture oracle is oracle that takes S C X as input and returns the number of components kS)) as well as the weights π (S,j) and components C) for each j E [k((S)]. This oracle will be denoted by MixOracle(S).
Although our theoretical results are couched in the language of this oracle, we provide practical implementation details in Section 66 and experiments to validate our approach in Section 7
sufficient condition for the existence of mixture oracle that the mixture model over X is identifiable. This is because identifiability implies that the number of components K, the weights
P(Z = j). and the mixture components P(X Z j) are determined by P(X). The marginal weights π j) and components j) can then be recovered by simply projecting the full mixture over X onto
Remark 2.6. In fact, we do not need the full power of MixOracle. For our algorithms is sufficient to have access to k(S) for a sufficiently large family of S C X, the list of weights π TX,,j), and map that relates components in the full mixture over X the components in the marginal mixtures over each variable X, (see Section flrr details).
Before concluding this section, we note an important consequence of Assumption tha will be used in the sequel: Observation 2.7. Under Assumption 2.4 for any S S X
k(()) = II HSEpa(S)
tim(H,) =: dim(pa(S)).
Proof. By the Markov property. S is independent of H \ 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) = dia()).
3 Recovery of the latent causal graph
We first consider the oracle setting in which have access MixOracle(S)..
Observe that the problem of learning G can be reduced to learning (T.P(H)): Since we can decompose G into bipartite subgraph I' and latent subgraph A, it suffices to lear these two components separately. We then further reduce the problem of learning to learning the latent distribution P(H). First, will show how to reconstruct I from MixOracle(S). Then, will show how to learn the latent distribution PP ()) from MixOracle(S).
Thus, the problem of learning G is reduced to the mixture oracle:
G + (T, TP(H)) >> MixOracle(S)).
In the sequel, we focus our attention on recovering ((H). In order recover F(H), will require the following assumption:
Assumption 3.1 (Subset condition). We say that the bipartite graph I satisfies the subset condition (SSC) for any pair of distinct hidden variables H;, H2 the set nep(H,) is not subset of ner (H₃).
5

---

This assumption is weaker than the common "anchor words" assumption from the topic modeling literature. The latter assumption says that every topic has word that is unique to this topic, and commonly assumed for efficient recovery of latent structure g
Under Assumption 3.1
have the following key result:
Theorem 3.2. Under Assumptions 2.2 2.3 2.4 and 3.1 (T,P(H)) can be reconstructed from P(X)
and MixOracle( Furthermore, if additionally the columns of the bipartite adjacency matrix A 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 this result are presented in Sections 4 and [ 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(SS) exist, and 2) How can we identify A from P(H)? As 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(S) A mixture oracle exists if the mixture model over X is identifiable. As discussed in Section [ such identifiability results are readily available in the literature. For example, assume that for every S C X, the mixture model ( comes from any of the following families:
1. mixture of gaussian distributions 73 79
2. mixture of Gamma distributions 73 or
3. an exponential family mixture 79 or
4. mixture of product distributions 774,
5. a well-separated (i.e. in TV distance) nonparametric mixture 7
Then (T, (T,P(H)) 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 (8)).
identifying A from IP(H) is well-studied problem with many solutions [33 (1]. For simplicity, it suffices assume that TP (H) is faithful to A, which implies that A can be learned up to Markov equivalence. This assumption is not necessary, and any number of alternative identifiability assumptions on PHH) can be plugged in place of faithfulness, for example triangle faithfulness [70]. independent noise [56 671. post-nonlinearity
Identifiability of A Once we know P(H)) (e.g. via Theorem 3.2
81 equality of variances 29 55), etc.
4 Learning the bipartite graph
In this section we outline the main ideas behind the recovery of I in Theorem 3.2 establishing conditions that ensure I is identifiable, and then proceed to consider efficient algorithms for its recovery.
We begin by
4.1 Identifiability result
We study a slightly more general setup in which the identifiability of I' 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 I is t-recoverable if I can be uniquely recovered from X and the sequence (MixOracle(S) |S] S t).
Theorem 4.2. Let I' be the bipartite graph between X and H.
(a) Assume that (or(H;) + ner(H,) for any i + j. Then I and dim (H:) are n-recoverable.
(b) Let 2 3. Assume that for every S C with |S| 2 2 we have
dim dimspan(a,
$} 2 S| + 1,

---

then I and dim(H,) 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 in fact necessary:
Observation 4.3. If there a pair of distinct variables H4, H E H such that (er - ner H2)) then P not n-recoverable.
4.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 I' into 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 H₁ E H define w wH)) log(dim(HH)) Then for every set S C X
log(k(S))
E (H.).
()Epa(S)
In order to argue about the causal structure of the hidden variables we first need to identify the variables themselves. By Assumption [.2 every hidden variable leaves a "signature" among the observed variables, which is the set (er(H; of observed variables it affects. In particular, note that H, E Nx, (ner(() pa(X,), and if there is no Hj with ner (H,) C nHr, then H, is the unique element of the intersection. The lemma above allows to extract information about the union of parent sets, and wish to turn it into the information about intersections. This motivates the following definitions.
Definition 4.5. Let I' and w be as above. Define
sner(S) = 0
nor(z) and WSner(S) =
Σ
w(r)
(4)
#ES
(E)ner(S)
Lemma 4.6. For a set S XX we have
Wsner(S) Σ
(-)(UU)+W-(UU)
where Wr(S)
Σ vEDer(S)
w(v).
(5)
UCS,U+0
The proof of this lemma a simple application of the Inclusion Inclusion-Exclusion principle.
Remark 4.7. The RHS Eq. (5) only depends W evaluated on subsets of S. Thus, particular, (S|S] < L to compute Wsne(S) S) is enough to know MixOracle on all sets of size S t.
Finally, the values of the function Wsner can be organized into tensor, and from here the problem of learning I 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 I' can be recovered efficiently. We are primarily interested in the case = 3. The main idea is note that a rank-three tensor involving the columns of A can be written in terms of Wsner. We can then apply Jennrich's 's algorithm [4 to decompose the tensor and
recover these columns, which yield To see this, let I (i1. ig, i3) S X be triple of indices, and note that
Σ (a) jEH
(Σ w(j)a, 8 a, ( JEH
Wsner
(6)
(6 (2.5))
Theorem 4.8. Assume that the columns of A are linearly independent. Then I' and dimmHt)) for all 3-recoverable in O(n²) space and O time.
Proof. It takes ( space and O(n²) time to compute M3 and then Jennrich's 's algorithm can decompose the tensor in (nn²) space and O(n²) time.
7

---

visualization
04
?
0.3
2nd observed variable
4
0
H1
?
H2
Ha
5
0.0
-0.
2
8
4
-02
1
6
X
X2
X3
-03
23
A bipartite graph r
-0.6
-0.4
-0.2
0.0
0.2
variable
Figure 2: Example of latent DAG and corresponding mixture distribution
Learning the latent distribution
In this section we outline the main ideas behind the recovery of IP(H) in Theorem 3.2 Remark 5.1. Since the variables H are not observed, MixOracle(S) only tells the set
{(i, π (S, i), C(S, i)) i [k(S)]}- But the correspondence Ω 3 h ++ E [K] between a possible tuple h of values of hidden variables and the corresponding mixture component is unknown.
Since the values H are not observed, we may learn this correspondence only up to relabeling of Ω4. By definition, the input distribution has K = [S2] mixture components over X and h; k(X.) mixture components over X,. Fix any enumeration of these components by [A] and [Ki], respectively. To recover the correspondence Si è h ++ E [K]. ]. we will need access to the map
L: [K] + [k1] ..... x [kin]:
defined so that [[(j)] equals to the index of the mixture component C(X,) J) (marginalized over X,) in the marginal distribution over X,. Crucially, this discussion establishes that can be computed from combination of MixOracle( and MixOracle(X., (X;) for each i.
The map J. encodes partial information about the causal structure in G. Indeed, if h h2 E Ω are pair of states of hidden variables H that coincide on pa(X;) )) for some X; E X, then by the Markov property the components that correspond fı and h2 should have the same marginal distribution over X,,
Example 5.2. Consider the DAG Figure 2 We do not make any assumptions about the causal structure between hidden variables. This DAG has hidden variables, and we assume that each of them takes values in the set {0, Then by Assumption 2.4 every observed variable is 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 satisfied. The map L [8] + [4] [4] for an example as in Fig. hha
8: L(i): (2,4,3) (4,3,4),
3
4
6
7
8
(2,3, 1), (1,1,3), (3, (3,2,4), (4,,
(1,
Our goal is to find the correspondence between Q = {0, 1]3 and E (8). (The projection on the third variable is not shown Figure 2 the third coordinate of L cannot be deduced from the plot.)
We now show that there is an algorithm that exactly recovers P(H) from the bipartite graph I, the map L
[ + [k]] X ... x [k,], and the mixture weights (probabilities) {x(X 3) [K]] =
[IP
I
1) i e K]] Each of these inputs can be computed from MixOracle.
Definition 5.3. Let be an order-m tensor whose i-th mode is indexed by values of H;, such that ) = PHH = h). That is, J is the joint probability table of H.
J(
Theorem 5.4. Suppose Assumptions 2.4 and hold. Then the correspondence Q h t> C(X, i) and the tensor J(h2, hu,..., hm)) P -hh,, h2,.... B..))) can be efficiently reconstructed from
L, I and (x (X,i))ee(K)
Observation 5.5. If Assumpttin 3. is violated, then J cannot be reconstructed uniquely. Moreover, in this case G cannot be uniquely identified.
8

---

Implementation details
The results in Section assume access to the mixture oracle 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. naive application of clustering algorithms, however, ignores the significant structure between different subsets of observed variables. Thus, we also enforee 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 estimate the number of components in a marginal distribution for a subset S of observed variables with |S| S. 3, we use K 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. order make learning more robust we observe that the assumptions on the distribution imply the following properties:
Divisibility condition: The number of components we expect observe over a set S of observed variables is divisible by number of components we observe on the subset 5" C S of observed variables (see Obs. 2.7p.
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 S' for every S' S. Hence, if we learn the mixture models over S and S' with the correct numbers of components k(S) and k(S"), we expect the projections to be close.
Example 6.1. Suppose we are confident that the number of components the mixture over X1 is in the set {6, 7, 7.8). over X2 is in {4. 5, 6} and the number of components in the mixture over {X1, X23 in the set {20, 21, 22, 23, 24, 25, 26). Using divisibility condition between X1 and {X1, X2) we may shrink the set of candidates to (21,24), Next using the divisibility condition for X2 and (X1,X2) we may determine that the number of components should be 24.
With these observations in mind, we use 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 In order 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 X, is defined and pick the closest mean in L2 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 A 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 [69] or the GES algorithm [7]. In our experiments, we use the Fast Greedy Equivalence Search [57] with the discrete BIC score, without assuming faithfulness. The final graph G is therefore obtained from T and A.
7 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 P(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 Gli in the supplement.
Data generation We start with causal DAG G generated from the Erdös-Rényi model, for different settings of m, n 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 result, it is common have highly unbalanced clusters

---

Box plots Structural Hamming Distance (SHD) and Unoriented Correct Edges (UCE)
10000 samples
15000 samples
Metric
Metric
SHD
SHD
UCE
UCE
(1.31
(2. 5)
(3.
69.
(1.
5)
13.
13.8)
14.71
(m,,
Figure 3: Average Structural Hamming distance for recovery of G. where m H and n |X]
(e.g. we may have less than 30 points one component and over 1000 in another). Figure 3
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 CPDAG instead of DAG, we also report number of correct unoriented edges the estimated DAG. The average SHD across different problems sizes ranged from zero to 1.33. The highest SHD for any single run was For context, the simulated DAGs had between and edges. Note that any emross are entirely due to estimation error in the K K-means implementation of MixOracle, which we expect can be improved significantly. In the supplement we also report on experiments with much smaller sample size N 1000 (Fig. (7). 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 (Theorem3.2) We show that these conditions are essentially necessary, and mostly amount to non- degeneracy conditions on the joint distribution. Under linear independence condition on columns of the bipartite adjacency matrix of I, we propose a polynomial time algorithm for recovering I and P(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 long-studied problem, good mixture oracle implementation is a bottleneck for scalability of our approach. We believe that 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 's NSF grant CCF 1718902. G.R. partially supported by NSF grant CCF-1816372 P.R. was supported by NSF IIS-1955532. B.A. was supported by NSF IIS- 1956309,,3, NIH RM14M144467 and the Robert H. Topel Faculty Research Fund at the University of Chicago Booth School of Business.
10

---

References
[1] E. S. Allman, C. Matias, and J. A. Rhodes. Identifiability of parameters in latent structure models with many observed variables. Annals of Statistics, pages 3099-3132, 2009.
[2] A. Anandkumar, D. Hsu, and S. Kakade. A method of moments for mixture models and hidden markov models. Journal of Machine Learning Research, 23:33.1-33.34, 2012. cited By 26.
[3] A. Anandkumar, D. Hsu, A. Javanmard, and S. Kakade. Learning linear Bayesian networks with latent variables. In Proceedings of The 30th International Conference on Machine Learning. pages 249-257, 2013.
[4] A. Anandkumar, R. Valluvan, et al. Learning loopy graphical models with latent variables: Efficient methods and guarantees. Annals of Statistics, 41(2):001-435, 2013.
[5] N. Anari, C. Daskalakis, W. Maass, C. Papadimitriou, A. Saberi, and Vempala. Smoothed analysis of discrete tensor decomposition and assemblies of neurons. Advances in Neural Information Processing Systems, 11:10677-10867, 2018.
[6] T. W. Anderson. Estimating linear statistical relationships. The Annals of Statistics, pages 1-45, 1984.
[7] B. Aragam, C. Dan, E. P. Xing, and P. Ravikumar. Identifiability of nonparametric mixture models and bayes optimal clustering. Ann. 4444) 2020. ISSN 0090-5364. doi: 10. 10.1214/1--AOSI
1xXv:1802.04397
[8] Arora, R. Ge, and A. Moitra. Learning topic models-going beyond svd. 2012 IEEE 53rd annual symposium on foundations of computer science, pages 1-10. IEEE, 2012.
[9] S. Arora, R. Ge, Y. Halpern, D. Mimno, A. Moitra, D. Sontag, Y. Wu, and M. Zhu. A practical algorithm for topic modeling with provable guarantees. In International Conference on Machine Learning, pages 280-288. PMLR, 2013.
[10] S. Bonhomme, K. Jochmans, and J.-M. Robin. Estimating multivariate latent-structure models. Annals of Statistics, 44(2):540-563, 2016.
[11] G. Bresler and R.-D. Buhai. Learning restricted boltzmann machines with sparse latent variables. Advances Neural Information Processing Systems, 33, 2020.
[12] G. Bresler, Koehler, and A. Moitra. Learning restricted boltzmann machines via influence maximization. In Proceedings of the 51st Annual ACM SIGACT Symposium Theory of Computing, pages 828- 889, 2019.
[13] K. Chalupka, P. Perona, and F. Eberhardt. Visual causal feature learning. arXiv preprint 11Xiv:1412.2309, 2014.
[14] K. Chalupka, Eberhardt, and P. Perona. Causal feature learning: an overview. Behav- iormetrika, 44(1):137-166 2017.
[15] V. Chandrasekaran, P. A. Parrilo, A. Willsky, et al. Latent variable graphical model selection via convex optimization. The Annals of Statistics, 1094) 2012.
[16] J, Chen and A. Khalili. Order selection in finite mixture models with a nonsmooth penalty. Journal of the American Statistical Association, 104(485):187-19,, 2009.
[17] D. M. Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554, 2002.
[18] D. Colombo, M. H. Maathuis, M. Kalisch, and T. S. Richardson. Learning high-dimensional directed acyclic graphs with latent and selection variables. Annals of Statistics, 40(1):294-32) 2012.
[19] D. Dacunha-Cassen Castelle, E. Gassiat, et al. The estimation of the order of a mixture model. Bernoulli, 3(3):279-299, 1997.
11

---

[20] A. D' Amour. On multi-causs causal inference with unobserved confounding; Counterexamples, impossibility, and alternatives. arXiv preprint arXiv:1902.10266 2019.
[21] M. Ding, C. Daskalakis, and S. Feizi. Gans with conditional independence graphs: On subadditivity of probability divergences. In International Conference on Artificial Intelligence and Statistics, pages 170933717, PMLR, 2021.
[22] G. Elidan, N. Lotmer, N. Friedman, and D. Koller. Discovering hidden variables: a structure- based approach. In Proceedings of the 13th International Conference Neural Information Processing Systems, pages 458-464, 2000.
[23] R. Evans. Graphs for margins of bayesian networks. Scandinavian Journal of Statistics, 43 (3):625-648, 2016.
[24] R. J. Evans and S. Richardson. Markovian acyclic directed mixed graphs for discrete data. The Annals of Statistics, pages 1452-1482, 2014.
[25] R. J. Evans, T. S. Richardson, et al. Smooth, identifiable supermodels of discrete dag models with latent variables. Bernoulli, 25(2):848 -76, 2019.
[26] R. J. Evans et al. Margins of discrete bayesian networks. The Annals of Statistics, 46(6A): 2623-2656, 2018
[27] N. Friedman al. Learning belief networks in the presence of missing values and hidden variables. In ICML, volume 97, pages 125-133, Citeseer, 1997.
[28] B. Frot, P. Nandy, and M. H. Maathuis. Robust causal structure learning with some hidden variables. arXiv preprint arXiv:/708.000 151, 2017.
[29] M. Gao, Ding, and B. Aragam. polynomial-time algorithm for learning nonparametric causal graphs. Advances in Neural Information Processing Systems, 33, 2020.
[30] E. Gassiat, A. Cleynen, and S. Robin. Finite state space parametric hidden markov models are in general identifiable. arXiv preprini 130.44730 2013.
[31] S. L. Gordon and L. J. Schulman. Hadamard extensions and the identification of mixtures of product distributions. arXiv preprint arXiv:2101.11688 2021.
[32] Grimmer, D. Knox, and M. Stewart. Nak " ive regression requires weaker assumptions than factor models to adjust for multiple cause confounding. arXiv preprint arXiv:2007. 220,:22000..2702,,, 2020.
[33] P. Hall and X.-H. Zhou. Nonparametric estimation of component distributions in multivariate mixture. Annals of Statistics, pages 201-224, 2003.
[34] R. A. Harshman. Foundations of the PARAFAC procedure: Models and conditions for an "explanatory" multimodal factor analysis. 1970.
[35] O. Hoyer, S. Shimizu, and A. Kerminen. Estimation of linear, non-gaussian causal models in the presence of confounding latent variables. arXiv preprint cs/0603038, 2006.
[36] I. Khemakhem, D. Kingma, R. Monti, and A. Hyvarinen. Variational autoencoders and nonlinear iea: A unifying framework. International Conference on Artificial Intelligence and Statistics, pages 2207-2217. PMLR, 2020.
[37] T. Kipf, E. Fetaya, K.-C. Wang, M. Welling, and R. Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning, pages 2688-2697. PMLR, 2018.
[38] M. Kocaoglu, C. Snyder, A. G. Dimakis, and S. Vishwanath. Causalgan: Learning causal implicit generative models with adversarial training. arXiv preprint arXiv: 170000202,,, 2017.
[39] V. I. Koltchinskii. Empirical geometry of multivariate data: deconvolution approach. Annals of statistics, pages 591-629, 2000.
12

---

[40] P. Larrañaga and S. Moral. Probabilistic graphical models in artificial intelligence. Applied soft computing, 11(2):511-1528, 2011.
[41] Y. Li, A. Torralba, A. Anandkumar, D. Fox, and A. Garg. Causal discovery in physical systems from videos. arXiv preprint (rxxix:000700063/1 2020.
[42] B. G. Lindsay. Mixture models: theory, geometry and applications. In NSF-CBMS regional conference series in probability and statistics, pages i-163. JSTOR, 1995.
[43] D. Lopez-Pazz R. Nishihara, S. Chintala, B. Scholkopf, and I.. Bottou. Discovering causal signals in images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6979-6987, 2017.
[44] B. Lovitz and F. Petrov. A generalization of kruskal's theorem on tensor decomposition. arXiv preprint arXiv: 103. 15633, 2021.
[45] Manole and A. Khalili. Estimating the number of components finite mixture models via the group- sort--so procedure. arXiv preprint arXiv:2005.11641, 2020.
[46] A. Markham and M. Grosse-Wentrup.
Wentrup. Measurement dependence inducing latent causal models.
In Conference on Uncertainty in Artificial Intelligence, pages 590-599. PMLR, 2020.
[47] J. Martin and K. VanLehn. Discrete factor analysis: Learning hidden variables in bayesian networks. Technical report.
[48] G. McLachlan, S. X. Lee, and S. Rathnayake. Finite mixture models. Annual review of statistics and its application, 6:355-378, 2019.
[49] A. Moitra. Algorithmic aspects of machine learning. Lecture notes, 2014.
[50] R. P. Monti, K. Zhang, and A. Hyvärinen. Causal discovery with general non-linear relationships using non-linear ica. In Uncertainty in Artificial Intelligence, pages 186-195. PMLR, 2020.
[51] E. Mossel and S. Roch. Learning nonsingular phylogenies and hidden markov models. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 366-375, 2005.
[52] A. Newell and J. Deng. Pixels to graphs by associative embedding. arXiv preprint arXiv: 07365, 2017.
[53] Pearl. Probubilistic reasoning in intelligent systems: Networks of plausible inference. Morgan Kaufmann, 1988.
[54] J. Pearl. Causality. Cambridge university press, 2009.
[55] Peters and P. Bühlmann. Identifiability of Gaussian struetural equation models with equal eтror variances. Biometrika, 101()):219-228 2013.
[56] J. Peters, J. M. Mooij, D. Janzing, and B. Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15(1):2009-205: 20553, 2014.
[57] Ramsey, M. Glymour, R. Sanchez- Rombero and C. Glymour. A million variables and more: the fast greedy equivalence search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images. International journal of data science and analytics, 3(2):121-129, 2017.
[58] T. Richardson, P. Spirtes, et al. Ancestral graph markov models. The Annals of Statistics, 30(4): 962-1030, 2002.
[59] T. S. Richardson, R. J. Evans, J. M. Robins, and I. Shpitser. Nested markov properties for acyclic directed mixed graphs. arXiv preprint 170.00667...66. 2017.
[60] A. Ritchie, R. A. Vandermeulen, and C. Scott. Consistent estimation of identifiable nonparamet- ric mixture models from grouped observations. arXiv preprint arX15v2006.07459, 2020.
13

---

[61] J. M. Robins and L. Wasserman. On the impossibility of inferring causation from association without background knowledge. Computation, causation, and discovery, 1999:305-21, 1999.
[62] M. Robins, R. Scheines, P. Spirtes, and L. Wasserman. Uniform consistency causal inference. Biometrika, 90(3):91-515, 2003,
[63] B. Schölkopf, F. Locatello, S. Bauer, N. R. Ke, N. Kalchbrenner, A. Goyal, and Y. Bengio. Toward causal representation learning. Proceedings of the IEEE, 109(5):11-6334, 2021.
[64] C. Semple and M. Steel. Phylogenetics, volume 24. Oxford University Press on Demand, 2003.
[65] X. Shen, F. Liu, H. Dong, Q. Lian, Z. Chen, and T. Zhang. Disentangled generative causal representation learning. arXiv preprint arXiv:2010.02667,, 2020.
[66] T. Shi, M. Belkin, and B. Yu. Data spectroscopy: Eigenspaces of convolution operators and clustering. Annals of Statistics, pages 3960-3984, 2009.
[67] S. Shimizu, P. O. Hoyer, A. Hyvärinen, and A. Kerminen. A linear non-Gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7:2003-20388 2006.
[68] R. Silva, R. Scheine, C. Glymour, and P. Spirtes. Learning the structure of linear latent variable models. Journal of Machine Learning Research, 7(Feh):191-246, 2006.
[69] Spirtes and C. Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, (1)x62-72, 1991.
[70] P. Spirtes and J. Zhang. A uniformly consistent estimator of causal effects under the k-triangle- faithfulness assumption. Statistical Science, pages 662-678, 2014.
[71] Spirtes, C. Glymour, and R. Scheines. Causation, prediction, and search, volume 81. The MIT Press, 2000.
[72] L. Spirtes, C. Meek, and T. S. Richardson. Causal inference in the presence of latent variables and selection bias. arXiv preprint 1rX2vv1302..44: 2013.
[73] H. Teicher. Identifiability of finite mixtures. The annals of Mathematical statistics, pages 1265-1269, 1963.
[74] H. Teicher. Identifiability of mixtures of product measures. The Annals of Mathematical Statistics, 38(4):1300-1302 1967.
[75] R. A. Vandermeulen and C. D. Scott, An operator thcoretic approach to nonparametric mixture models, 2016.
[76] A. Vijayaraghavan. Efficient tensor decomposition. Beyond the Worst-Case Analysis of Algo- rithms, page 424, 2020.
[77] C. K. Wongchokprasitti, H. Hochheiser, J. Espino, E. Maguire, Andrews, M. Davis, and C. Inskip. bd2kced/py-caussl v1.2.1, Dec. 2019.
[78] F. Xie, R. Cai, B. Huang, C. Glymour, Z. Hao, and K. Zhang. Generalized independent noise condition for estimating latent variable causal graphs. Advances in Neural Information Processing Systems, 33, 2020.
[79] S. J. Yakowitz and J. D. Spragins. On the identifiability of finite mixtures. The Annals of Mathematical Statistics, (0(1:22092244 1968.
[80] M. Yang, F. Liu, Z. Chen, X. Shen, J. Hao, and Wang. Causalvae: Disentangled representation learning via neural structural causal models. arXiv preprint arXiv:2004. 08697, 2020.
[81] K. Zhang and A. Hyvärinen. On the identifiability of the post-nonlinear causal model. In Proceedings of the twenty-fifth conference on uncertainty in artificial intelligence, pages 647- 655. AUAI Press, 2009.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] At L86-90, we discuss how our results do not contradict existing impossibility results in causal inference, which an important limitation. In several places (L293-294, L299-304), we acknowledge that learning mixture models is also hard problem. The assumptions acknowledged to be nontrivial at 19-1-123 and are placed in context.
make G
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See p.3
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See for instance Assumptions 2.2 2.3
3.1
(b) Did you include complete proofs of all theoretical results? [Yes] See supplementary materials
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL.? [Yes) See supplemen- tary materials
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See supplementary materials
(c) Did you report error bars (c.g.. with respect the random seed after running experi- ments multiple times)? [Yes] See Figure
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] See supplementary materials
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We are running experiments synthetic data
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] We are running experiments on synthetic data
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "luB5pg-TkFY", "reviewer": "Reviewer_rWbo", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n--------------\nThe task considered, estimation of a latent causal graph, has been previously studied (Silva et al., 2006, Xie et al., 2020) and is of great interest to many in the causal inference community. The method/setting is new, and this novelty is made clear throughout the paper: most other works have relied on linear models, whereas this work considers the discrete setting. Additionally, other works have had more stringent conditions on the structure of the graph relating the latent and observed variables. The prior works are adequately discussed, and I appreciate that the authors mention a few separate lines of work, including causal feature learning, interaction modeling, and computer vision. However, for completeness, the authors may wish to add the following citations when discussing the most directly related line of work, i.e., learning latent causal structure:\n- Cai et al., 2019: Triad constraints for learning causal structure of latent variables\n- Kummerfeld and Ramsey, 2016: Causal clustering for 1-factor measurement models\n\nQuality\n----------\nFor the most part, the submission is theoretically sound, however, I have only skimmed the proofs in the appendix. There was one point of confusion for me in the main text. Assumption 2.2 requires that the same distribution cannot be Markov to any DAG formed by merging a pair of hidden variables in the true DAG. However, it seems to me that this would always be possible; for example, consider the graph in Figure 1b of the paper. Merging H1 and H2 would give a new DAG which satisfies Assumption 2.1 (no twins), and the distribution over (H1, H2, X1, X2) would still be Markov with respect to this new DAG (where now we replace H1 and H2 with a single variable H=(H1, H2)). In particular, the only implied conditional independence in the new model is that X1 and X2 are conditionally independent given H, which still holds. It seems I am misunderstanding the minimality assumption, since the authors claim that the graphs in Example B.2 satisfy this assumption. Please clarify in the author feedback.\n\nThe piece of work is complete by the standards of a conference: the authors not only provide an identifiability result, but offer computational complexity results for setting where an efficient algorithm is possible. There is definitely still interesting future work on this exact setting, including improving the subroutines used for estimating the mixture oracle, and a thorough statistical analysis, along with theoretical results for how to “vote” on the number of marginal components (mentioned in Section 6 with a very helpful example).\n\nClarity\n----------\nThe submission is very clearly written, with only two points of confusion/poor wording. The first point regards Assumption 2.1, already mentioned. The second point is minor: the authors use phrases such as “little is known regarding structure learning … with latent variables”. The authors are correct when we restrict to structure learning *over* latent variables, i.e., when the interesting causal structure is mostly over the latent variables. However, structure learning *in the presence* of latent variables is a very rich field of study in causal structure learning, including work on learning maximal ancestral graphs (Richardson and Spirtes, “Ancestral Graph Markov Models”, 2002) and work on learning DAGs in the presence of pervasive confounders (Frot et al. “Robust causal structure learning with some hidden variables, 2019). The language of “with latent variables” is used in many places throughout the paper, and it would be an improvement to be more precise.\n\nSignificance\n-----------------\nThe results are an important contribution to the somewhat nascent, but widely anticipated, area of learning latent causal structure. As mentioned, the paper shows an optimistic result about how “signatures” of latent variables can be used to recover the distribution over the latent variables themselves. It is likely that in the discrete setting, the building blocks of their methods will be used in future works and the details of the method will be built upon/improved. It is also likely that some algebraic or information theoretic characterization of the observations used here in the discrete setting could carry on to general (i.e., continuous and nonlinear) settings. On the less positive side, I should note that in practice, the actual setting - discrete random variables, and conditions on the relations between observed and latent variables - is likely too restrictive for immediate use in applications such as recovering causal structure from images, where every latent variable is likely to be a parent of every observed variable (pixel).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately address the potential negative societal impact of their work (and the broader line of work on recovering latent variables) with respect to privacy. The paper takes a “white hat” perspective: it is good to know when certain latent variables can be recovered, so as to be aware of possible violations of privacy, and this line of work may offer enough insight to design systems which are provably immune to privacy attacks.\n\nIt would be beneficial to the authors to address the limitations of the work more explicitly, e.g. giving settings where their assumptions don’t hold (e.g., images as mentioned above) and where discrete random variables are a poor model. In particular, even though discretizing a continuous variable might allow the method to theoretically be applicable, the required alphabet size might make the methods too computationally expensive or statistically inefficient to be useful in practice.\n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "ba0m4QGCe_O", "reviewer": "Reviewer_1Np2", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "PROS:\n\n-Straightforward and solid idea\n\n-Solid mathematical presentation\n\nCONS:\n\n-Seems like time has run out while writing the article. I was expecting a convincing demonstration of the usefulness of the idea with some real-world data, but there was not even an attempt for such. Furthermore, the article had no Discussion/Conclusion.\n\nSUMMARY: this paper introduced a sensible idea for causal discovery in the latent space, with explicit assumptions and formal proofs of identifiability, which I liked. However, the usefulness of the idea should have been demonstrated in a realistic use-case.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "_CPN93OzYqb", "reviewer": "Reviewer_9wNn", "summary": "This is a paper that focuses on causal discovery especially focusing on the causal relation among discrete latent variables. \nThe basic idea is that by mixture oracles, one can locate the latent variables and recovery their distribution.\nThe main contribution is the model identification theory, including bipartite graph, latent distribution $P(H)$.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers a challenging problem of learning causal graphs over discrete latent variables.  The key point is how to determine the number of hidden variables and their corresponding indicators.\\\nThe authors provide a  new view for identifying a discrete latent model (recover the bipartite graph by learning the parameters of the mixture model ).\\\nThe theoretical contributions of this paper are interesting, and the experiments seem promising.\n \nSome concerns:\\\n-The algorithm's complexity is a cause for concern, especially when the graph has a large number of variables. This is because the algorithm involves the enumeration of all subsets that the cardinality is less than or equal to 3.\\\n-The algorithm is evaluated with a large sample size in your experiments. It would have been more convincing with a small sample size.  I am worried about the usefulness of the algorithm.\\\n-It would be good if you show the limitations of your method in the conclusion.\n\n-------After rebuttal-------\n\nThanks for the clarifications and for addressing my concerns. Based on the author's response and other reviews, my score remains unchanged. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "XE-D0UxR4ta", "reviewer": "Reviewer_mBxt", "summary": "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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors should present their result in light of some of the missed existing work such as pLSA or LDA. In general, the non-negative matrix factorization literature provides us with certain impossibility results which is only somewhat discussed in Section 3 (anchor words). \n\nI believe the model the authors assume here is called the measurement model - where there are no edges between the observed variables and no edges from observed variables to latents.\n\nEssentially authors only assume confounders and no latent mediators.  \n\nAdditional assumptions:\n1. no pair of distinct latents are adjacent to the same set of observed variables. \n\n2. this is a complicated assumption and is a bit hard to judge. Essentially that there is no smaller DAG with same assumptions according to which the distribution is Markov. \n\n3. strictly positive latent dist. and unique conditional distributions for every subset of target variables. \n\n4. There is a 4th hidden assumption that the mixture oracle is available. Essentially, mixture oracle does all the heavy-lifting by identifying not only the number of mixture components but also the mixed distributions and the mixture weights. \n\n5. There is a 5th assumption that appears in Section 3 which says no neighborhood of any two latent nodes have subset relation. \n\n\"This assumption is weaker than the common “anchor words\" assumption from the topic modeling literature. \"\nCould you elaborate on why this is?\n\nAuthors claim their condition for recoverability is weaker than anchor node condition. Anchor node condition is one sufficient condition for ensuring a unique NMF. Does this mean the proposed method provides a weaker condition for unique recoverability? I don't believe this is the case but I think this needs to be discussed and clarified in the main text. \n\nOn that note, I believe one can easily construct NMF examples, which correspond to mixture models, where the solution is not unique but all the required assumptions are satisfied. This relates to the uniqueness of (2). \n\nPlease comment on why the representation in (2) has to be unique. For example, I can write p(x)=[1/4,3/4] as multiple mixtures \\sum p(h)p(x|h), essentially any a, b, c, d, e would do s.t a[b,c]+(1-a)[d,e]=[1/4,3/4]. E.g. take 0.5[0,1]+0.5[1/2,1/2] or take 0.25[1,0]+0.75[0,1]. In either case, p(x|h) are distinct (condition in Assumption 2.3) whereas the other representation fits just as well. \n\nI am also not sure if Observation 2.6 is accurate. It would be great to have a more formal and rigorous proof. The above discussion and example seems to constitute against the argument in the current proof which implicitly seems to rely on uniqueness of (2).\n\nFig. 2 is a good example and it demonstrates that assumptions essentially imply each mixture component can be observed in the joint distribution of the observed variables. In that sense, I don't fully understand how it is weaker than anchor node assumption. \n\nIt is very hard to assess the validity of all the assumptions without real data experiments. \n\nUnless I am misunderstanding something, tensor decomposition is not poly time unless the number of components is a constant. But a generic poly-time claim is made in the introduction and the detailed discussion does not appear in the main text but only in the appendix. \n\nFigure 1 is not very useful since it is disconnected from the discussion. I recommend explaining in which of these graphs the assumptions hold. I believe it should hold in all of them. \n\nAfter Rebuttal: \nThank you to the authors for engaging in a very useful discussion. Authors made clear where their contribution lies and that their identifiability result heavily relies on the existence of a mixture oracle. They provided examples of such oracles in certain settings. In light of the discussions, I will increase my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. Limitations could be discussed in more detail in relation to my comments above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There has been ampled discussion between reviewers and authors. The authors are encourage to leverage the elements in this exchange to improve the paper.

In particular, a key conlcusion of the discussion between reviewers is that given the key role of a Mixture Oracle in this work, all reviewers agree that it would be really important to add a paragraph describing existing identifiability results for mixture oracles, as well as a corollary that gives an exact set of assumptions under which the algorithm is consistent.

Decision: Accept (Poster)