Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Originality
--------------
The 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:
- Cai et al., 2019: Triad constraints for learning causal structure of latent variables
- Kummerfeld and Ramsey, 2016: Causal clustering for 1-factor measurement models

Quality
----------
For 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.

The 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).

Clarity
----------
The 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.

Significance
-----------------
The 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).
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.

It 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.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 

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). 

I 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.

Essentially authors only assume confounders and no latent mediators.  

Additional assumptions:
1. no pair of distinct latents are adjacent to the same set of observed variables. 

2. 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. 

3. strictly positive latent dist. and unique conditional distributions for every subset of target variables. 

4. 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. 

5. There is a 5th assumption that appears in Section 3 which says no neighborhood of any two latent nodes have subset relation. 

"This assumption is weaker than the common “anchor words" assumption from the topic modeling literature. "
Could you elaborate on why this is?

Authors 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. 

On 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). 

Please 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. 

I 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).

Fig. 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. 

It is very hard to assess the validity of all the assumptions without real data experiments. 

Unless 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. 

Figure 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. 

After Rebuttal: 
Thank 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. 
limitations_and_societal_impact: No. Limitations could be discussed in more detail in relation to my comments above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This is a paper that focuses on causal discovery especially focusing on the causal relation among discrete latent variables. 
The basic idea is that by mixture oracles, one can locate the latent variables and recovery their distribution.
The main contribution is the model identification theory, including bipartite graph, latent distribution $P(H)$.
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.\
The authors provide a  new view for identifying a discrete latent model (recover the bipartite graph by learning the parameters of the mixture model ).\
The theoretical contributions of this paper are interesting, and the experiments seem promising.
 
Some concerns:\
-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.\
-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.\
-It would be good if you show the limitations of your method in the conclusion.

-------After rebuttal-------

Thanks for the clarifications and for addressing my concerns. Based on the author's response and other reviews, my score remains unchanged. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: PROS:

-Straightforward and solid idea

-Solid mathematical presentation

CONS:

-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.

SUMMARY: 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.

limitations_and_societal_impact: Yes.
review_title: null

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)