Learning Discrete Latent Variable Structures with Tensor Rank Conditions

Summary

This study develops new methods for identifying causal structures in discrete latent variable models using rank constrain. By leveraging this nontrivial algebraic property, the authors propose criteria and algorithms for discovering hidden causal relationships. They validate their approach through simulations.

Strengths

1. As far as I know, the tensor rank condition is a novel contribution. Unlike previous on rank deficiency, this method can handle non linear relations. 2. The experiments are done on both simulated and real-world dataset.

Weaknesses

I wonder if some assumptions are a bit strong such as the faithfulness assumption and the three pure child assumption and I wonder how they play into practical scenarios.

Questions

1. How does this paper compare to works like [1] where rank constraint is also used in a non-linear setting? [1] Kong, Lingjing, et al. "Learning Discrete Concepts in Latent Hierarchical Models." *arXiv preprint arXiv:2406.00519* (2024).

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

See weakness.

Summary

This paper aims to learn latent causal models with discrete random variables. To this end, a tensor rank condition on contingency tables of observed variables is used. Specifically, the paper establishes connections between the d-separation of the observed variables and the “tensor rank” of the said random variables. Subsequently, this property is leveraged to construct an algorithm that learns (i) the measurement model, that is the connections from the latent variables to observed variables, and (ii) the structure model (the edges between the latent variables) up to Markov equivalence class. The main structural assumptions for the results are purity (no edges between the observed variables) and three observed children per latent node, and other standard causal assumptions, e.g., faithfulness, are adopted in the paper.

Strengths

The literature mostly focuses on learning linear latent models. Instead, this paper aims to address discrete latent models for which the existing work is scarce (the paper outlines that they are limited to very restrictive structures, e.g., trees). The whole paper builds on making a nice observation: the tensor rank of the contingency tables of the joint dist. of the observed variables are connected to the support of the variables that d-separate them. This observation is substantiated in the main result Theorem 3.3. All the subsequent results (mainly the algorithms) build on this main observation, which leads to rather simple proofs. I find this simplicity as a strength. The practical implementation of the proposed method is also clearly explained using existing techniques to test the tensor rank.

Weaknesses

- *Structural limitations are quite restrictive*. Specifically, the purity assumption that there are no edges between the observed variables is a serious limitation. On one hand, this is understandable as the existing works usually have similar or stronger restrictions. On the other hand, having partial results for the cases where this assumption is violated would have made the paper significantly stronger. I see that the paper touches on this via an example and leaves it as future work, nevertheless, it’s a big limitation of the current paper. - On a related note, the assumptions are not convincingly justified. For instance, three-pure children assumption is just taken for granted without proper discussion (I acknowledge the reference to similar work, please see the questions section). - This is relatively a minor concern: I enjoyed the flow of the paper, but the writing could be improved for sure. I elaborate on this in questions.

Questions

**Critical points on assumptions** - *Allowing edges between observed variables*: It seems like extending the results to impure structures would require a different approach. Because the propositions -- the backbone of finding the measurement model -- are very specific to the purity assumption. In the discussion section, an example is provided and the extension is left for future work. I think you can be more open about it, e.g., what are the challenges, what are the missing pieces? For instance, in the example in Section 7, are you also able to determine the lack of edges between any $(X_i,X_j)$ pair except $(X_4,X_5)$? - *Structural constraints in the literature*: I think you need to be more direct and provide exact requirements/structural constraints and results. For instance, if I recall correctly, Cai et al. and Xie et al. require 2 pure children per latent whereas this paper requires 3 pure children (I am aware that those papers are for linear latent models). Can you elaborate on the similarities and differences between the roles of these assumptions? On key difference from related work, L89 says that the are no constraints on the latent structure. Is this difference w.r.t. binary latent variable case (Gu and Dunson (2023) and Gu (2022)) or all the previous work including the linear latent variable models? - In Appendix D, the full rank assumption (Assumption 2.4) discussion is informative and reasonable. However, a similar discussion for the other assumptions is missing. For instance, in the example in Section 7, the possibility of working on an impure structure is explained but failure cases (and why they happen) are not explained. I think it’s equally important to explain those cases. On a related note, the role of 3 pure children assumption is not discussed in the paper (please point out if I missed it). - *Support of latent variables*: The paper says that *”For simplicity, we focus on the case where all latent variables have the same number of categories, with extensions provided in Appendix F”*. Some clarification can be helpful. I skimmed through Appendix F, and it seems like the extension to “latent variables with different numbers of categories” is immediate without extra assumptions. If this is indeed the case, then I suggest the authors explicitly state it in the main paper. If the extensions require more assumptions and/or more sophisticated techniques, again, be more clear about it so the reader can understand if it’s a limitation or not. **Experiments related**: - I see that the definitions of metrics are in Appendix I (which should be referred to in L288 to help the reader). It would have been nicer to squeeze them into the main paper. - Adding a small section for real data applications (Section 6) without sufficient details does not add much value. I think it can be safely moved to the appendix, where the details are given, which would also open space for a more self-contained simulation section. - I think your method should be able to handle an arbitrary number of children as long as there are at least 3. So, you could have tested different sizes for different latent variables instead of a fixed number of 3 or 4. For instance, each latent variable can have at least 3, at most 6 observed variables, which could have allowed you to evaluate whether there is a difference between the performance in learning measurement and structure models. - For such sparse and small graphs, 50k samples are a bit too aggressive. Perhaps starting from 1k would show the limits of the approach and help us to understand the performance better. For instance, at “mismeasurements” metrics, even 5k sample seem to work well, it would have been interesting to see what is the limit. **Relatively minor notes**: - *Definition 2.1 (Discrete LSM)*: Is this a proper name? I don’t like calling the specified model “discrete LSM” simply because it is too general. Assumptions are clearly stated in the definition, but calling the model just discrete LSM, especially under the purity and three-pure child assumptions is not great, especially when we think about the potential future work and positioning of this paper in the literature. - *Theorem 4.7*: Please be careful when using $p$ in notations, $\mathbf{X}_p$ and $\mathbf{L}_p$ notations are a bit confusing. At first reading, $p$ reads as a set, e.g., in Example 4.8, $\mathbf{X}_p$ implies $p=\\{1,10,4,5,7,8\\}$, but $\mathbf{L}_p=\\{L_2,L_3\\}$, so it is not a set notation. - *Conclusion Section 8*: Overall, I liked this conclusion. That being said, being more direct and recalling the main structural assumptions would have been good. For instance, the limitations paragraph in Appendix K is very clean — I appreciate it. Since it’s just 2.5 lines, I’d suggest to include in the main paper **Typos etc.**: - Prop 4.3: I think Rule 2 statement is missing “if”. Also, why $L_i$ instead of $L$? - Theorem 4.7: varaible - Theorem 4.9: TESNOR - L177: missing period - L800: TENSKR - CP decomposition: please spell out at the first appearance - Figure 8: make the markers larger, please.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Limitations are mostly addressed. I suggest the authors to see my comments on questions to further clarify them.

Summary

This paper studies the problem of learning causal structures among latent variables from discrete observational data. The author presents a tool, termed the tensor rank condition, to establish the connection between rank constraints of the probability tensor and d-separation relations in the causal graph. The proposed tool appears simple and effective. Based on the tensor rank condition, the author proposes a two-stage algorithm that first learns the causal clusters to identify latent variables and then tests the conditional relations among latent variables using their measured variables. The proposed algorithm extends the identification bound of discrete latent variable models, and the experimental results demonstrate the efficiency of the proposed methods.

Strengths

1. The paper is clearly written and well-organized. 2. The proposed tensor rank condition establishes the connection between algebraic constraints and d-separation relations in discrete causal models. This tool has the potential to explore more causal discovery problems in discrete causal models 3. Compared to traditional methods of the linear latent variable model, such as rank constraints of the covariance matrix, the tensor rank condition takes a meaningful step in latent variable modeling in more general cases. 4. The proposed algorithm looks simple but effective, addressing the identification of discrete latent variable models.

Weaknesses

1. For the sufficient observation assumption, it seems that the cardinality of the observed variable support can be equal to the cardinality of the latent support, as discussed in Remark F.4. Could you clarify this? 2. Why is the Three-Pure Child Variable Assumption required? In my opinion, the tensor rank condition can test the d-separation relations between only two observed variables, as shown in Figure 1. Thus, one can learn the causal cluster from a two-pure child variable assumption. Please correct me if I am wrong. If this assumption does not hold, what happens to the output of your algorithm? 3. In Proposition F.3, $r$ is easily confused with the concept of the cardinality of the support of a single latent variable. It is recommended to change the expression like $\tilde{r}$.

Questions

typo: In Figure 2(b), LVM should be LSM.

Rating

8

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

see weakness

Summary

This paper studies the problem of learning latent variable structure in the discrete LSM measurement model. My understanding is that the paper operates under the following assumptions: 1) All latent variables are discrete 2) There are no connections between observed variables (i.e. observed variables are independent when conditioned on latent variables 3) In the unknown causal structure graph, each observed variable has exactly one latent variable parent. 4) The joint probability distribution of observed variables is fully known, and there is no noise in the measurement. 5) Each latent variable has at least three pure variables as children. 6) Other technical assumptions. The authors show that under such assumptions the unknown causal structure can be recovered from an algorithm that studies tensor rank conditions on contingency tables for an observed variable set.

Strengths

The problem studied in this paper covers an important case in causal structure learning literature. The measurement model with discrete latent variables is an important special case of causal structure models observed in practice, hence identifiability results and structure learning algorithms are important for this problem. The paper is well-written, and the claims are sound. Theoretical results are supported by experiments.

Weaknesses

I am a bit concerned about the novelty of the proposed results and methodology. In particular, [1] seems to obtain a stronger result under similar, if not weaker, assumptions, and this paper does not cite [1]. [1] proposes a structure learning algorithm for measurement model with discrete latent variables, under what seems to be a weaker set of assumptions. In particular [1] does not require each latent variable to have at least three pure children and does not require that each observed variable has only one latent parent. Those assumptions seem quite strong. The technique used in [1] to identify causal structure is also similar in flavor, and also relies on studying the rank of joint probability tensor (through numbers k(S)). Considering that [1] operates under a significantly more general setup while relying on similar techniques and ideas, could the authors please clarify what is the main novelty of this paper compared to [1]? [1] Learning latent causal graphs via mixture oracles B Kivva, G Rajendran, P Ravikumar, B Aragam - Advances in Neural Information Processing Systems, 2021

Questions

see above ----- During rebuttal score was increased 3 --> 4

Rating

4

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

na

Thanks for the clarification in helping us algining this issues

Thanks for the clarification in helping us algining this issues. It seems that you treat the $Pa(X_i|Pa(X_i))$ as the basis, thereby the tensor $P(S|Pa(S))$ can be recovered. However, we want to argue that without knowing the structure information we will have different basis when we probe at different triples and we do not know which one is the "correct" basis (here $Pa(X_i|Pa(X_i))$) we are looking for. For example, when there exists a minimum rank decomposition for $X_i, X_j, X_k$, the basic can be equal to $Pa(X_j|L_i) \neq Pa(X_j|Pa(X_j))$ (see the example in the previous response). In this case, we do not know if $Pa(X_j|L_i)$ is $Pa(X_j|Pa(X_j))$. Moreover, we want to show that, without the structure information, $Pa(X_i|Pa(X_i))$ may not be identifiable due to violation of the unique decomposition condition. For example, consider a structure with three observed variables $X_i, X_j, X_k$ and $L_1, L_2, L_3$ are their latent parent, respectively. To obtain the minimum rank decompositions of $X_i, X_j, X_k$ for estimating $Pa(X_i|Pa(X_i))$, it must satisfy the Kruskal's condition, that is, $Rk(P(X_i|L))+Rk(P(X_j|L))+Rk(P(X_k|L)) >= 2r+2$, where $r$ is the cardinality of latent support L, where $L = \[{Pa(X_i), Pa(X_j), Pa(X_k)\}]$. However, when the cardinality of the latent and observed support both are $d$, one can see that $Rk(P(X_i|L))+Rk(P(X_j|L))+Rk(P(X_k|L)) = 3d < 2d^{3}+2$. Therefore, $Pa(X_i|Pa(X_i))$ cannot be recovered due to a violation of the Kruskal condition. And it also violate the condition of 2K-1 strongly separate variables in [2], a sufficient and necessary condition for identifying the parameters of a discrete mixture model. We are very grateful for your patient response. Please feel free to reach out if you have any further questions.