Causal Structure Recovery with Latent Variables under Milder Distributional and Graphical Assumptions

Thanks for your time and effort in reviewing our paper and your kind encouragement.

Q1: The main weakness would be the empirical evaluation.

A1: We have reported the standard derivation and added more experimental results in Appendix A. We draw 10 sample sets for each graph following previous works [1,2,3]. We haven’t included some methods in our experiments because it can be expected that these methods cannot yield correct results when none of the non-Gaussianity, purity, and two-pure-children assumption holds theoretically, and their codes have not been publicly open-sourced. Also, our main contributions are theoretical rather than empirical.

Q2: The experiments had to be deferred to the Appendix is an indication that this paper is too long already.

A2: we have moved some subsidiary theoretical results to Appendix and moved the most representative experimental results from Appendix to the main text.

Q3: It would be useful to readers to have graphical depictions for what causal graphs your algorithm does and does not allow. To further delineate from previous works, it may be useful to have depictions of graphs that previous works allow as well.

A3: Thanks for this constructive suggestion. We have already shown $\mathcal{G}_1$ and $\mathcal{G}_2$ in Figure 1 which our algorithms can handle and previous works cannot handle. Furthermore, we have also displayed $\mathcal{G}_3$~$\mathcal{G}_8$ in Figure 3. Specifically, $\mathcal{G}_3$ satisfies the three-pure-children assumption (BPC and FOFC can also yield correct results theoretically), $\mathcal{G}_4$ violates Assumption 2(a), $\mathcal{G}_5$ violates Assumption 2(b), $\mathcal{G}_6$ satisfies the non-Gaussianity, purity, two-pure-children assumptions (GIN can also yield correct results theoretically), $\mathcal{G}_7$ violates Assumption 3(a), and $\mathcal{G}_8$ violates Assumption 3(b).

Q4: Given that the assumptions required are mostly on latent variables, is it possible at all to get an indication of when these assumptions might hold given a dataset?

A4: It is well-known that testing assumptions with only observational data is quite difficult, especially when there exist latent variables. In Section 3.4, we only provide an expedient to guide the choice between Algorithm 2 and Algorithm 3, based on the difference between Assumption 2 and Assumption 3 in the requirement for non-Gaussianity. Although this is not a perfect method, it is better than most previous works that directly circumvented the problem of testing assumptions. This is really an important problem and we list it as our future work in Section 7.

Reference

[1] Silva, Ricardo, et al. "Learning the Structure of Linear Latent Variable Models." JMLR 2006.

[2] Cai, Ruichu, et al. "Triad constraints for learning causal structure of latent variables." NeruIPS 2019.

[3] Xie, Feng, et al. "Generalized independent noise condition for estimating latent variable causal graphs." NeurIPS 2020.

Q4: Algorithmic description is missing.

A4: Thanks for pointing this out. We have provided detailed versions of our algorithms in Appendix D and illustrative examples to show how each step proceeds.

Q5: Concerns about presentation.

A5: Thanks for this constructive suggestion. We have introduced all previously used assumptions (including the three-pure-children, two-pure-children, non-Gaussianity, and purity assumption) in the second paragraph of the Introduction. Besides, our proposed assumptions are formulated as Assumption 1, 2, 3 respectively.

Q6: The paper is not self-contained.

A6: We have added a paragraph at the end of Section 5 (Relation to Existing Work) to briefly describe previous methods that are involved in our framework, including the Tetrad Representation Theorem [10] (It builds a connection between the structure of underlying causal structure and the covariance of variables that can be calculated from samples), Darmois-Skitovich Theorem [11] (As long as two variables share any non-Gaussian, independent component, they cannot be statistically independent), and PC-MIMBuild [12] (an overview is shown as Algorithm 4). All of them were proposed before 2010 and serve as the cornerstones of many other works. However, other more recent results they derived cannot be directly adopted in our framework where the required assumptions are not satisfied.

Reference

[1] Kivva, Bohdan, et al. "Learning latent causal graphs via mixture oracles." NeurIPS 2021.

[2] Kong, Lingjing, et al. "Identification of Nonlinear Latent Hierarchical Models." NeurIPS 2023.

[3] Spirtes, Peter L. "Calculation of entailed rank constraints in partially non-linear and cyclic models." UAI 2013.

[4] Kaltenpoth, David, and Jilles Vreeken. "Nonlinear Causal Discovery with Latent Confounders." ICML 2023.

[5] Harris, Naftali, and Mathias Drton. "PC algorithm for nonparanormal graphical models." JMLR 2013.

[6] Zheng, Yujia, Ignavier Ng, and Kun Zhang. "On the identifiability of nonlinear ica: Sparsity and beyond." NeurIPS 2022.

[7] Anandkumar, Animashree, et al. "Learning linear bayesian networks with latent variables." ICML 2013.

[8] Brouillard, Philippe, et al. "Differentiable causal discovery from interventional data." NeruIPS 2020.

[9] Mian, Osman A., Alexander Marx, and Jilles Vreeken. "Discovering fully oriented causal networks." AAAI 2021.

[10] Spirtes, Peter, Clark N. Glymour, and Richard Scheines. Causation, prediction, and search. MIT press, 2000.

[11] Kagan, A. M. "New classes of dependent random variables and a generalization of the Darmois–Skitovich theorem to several forms." Theory of Probability & Its Applications, 1989.

[12] Silva, Ricardo, et al. "Learning the Structure of Linear Latent Variable Models." JMLR 2006.

We are very grateful for your time and effort in reviewing our paper and your constructive comments. We hope the following new clarifications can address your concerns. Please let us know if there is any unclearness requiring further clarification.

Q1: Concerns about the linear causal relations.

A1:We have added some explanations about this point after the definition of the linear latent variable model (Definition 1) in Section 2.

First, most existing works about latent causal structure learning focused on the linear case. Although few works can avoid this assumption, they typically have other significant limitations. For instance, [1] allows non-linearity, but it requires that all latent variables are discrete; a contemporaneous work [2] allows non-linearity, but it forbids causal edges between any two variables that share at least one common parent.

Second, some theoretical results in our paper can actually generalize to two specific non-linear cases. We provided a detailed discussion in Appendix C.1. Roughly speaking, thanks to the Extended Trek Separation Theorem [3], all results in Section 3.1 and Section 3.2 are still valid as long as all causal relations involving generalized pure children (pure children and variables in a pseudo-pure pair) are still linear. Besides, if the underlying causal model follows a specific post-nonlinear model [4], we find that observed variables follow a nonparanormal distribution [5] and all theoretical results in Section 3.1 and Section 3.2 can still hold.

Finally, we agree that nonlinear is common in the real world and we list the problem of causal discovery for nonlinear cases as our future work.

Q2; Concerns about generalized pure pairs.

A2: Considering that many previous works mentioned in our paper assume that each variable has at least two or three pure children, we politely disagree that our requirement for a generalized pure pair is very strong since two pure children are exactly a special case of a generalized pure pair. In other words, our requirement for a generalized pure pair is much weaker compared to previous requirement for pure children. Pure children are believed to exist because sparsity of causal edges holds in many fields such as biology and physics [6].

In fact, testing assumptions about the structure of the underlying causal model is a quite difficult problem, especially those involving latent variables. For instance, even the casually sufficiency assumption that there exists no latent variable cannot be tested in most cases, let alone more complicated assumptions about pure children or generalized pure pairs. It may be possible to test this assumption with some auxiliary information (such as interventional data), but this problem is out of our current scope, we will leave it to future work.

By the way, there really exists some works that can recover the latent causal structure without pure children or generalized pure pairs, but they require other potentially stronger assumptions. An example is [7], whose assumption implies that latent variables have a sufficient number of observed children, the difference between latent variables in the number of observed children is small enough, any two latent variables do not share too many common observed variables, etc.

Q3: Concerns about experimental results.

A3: We have moved the most representative experimental results to the main text as Section 6, which indicates that our algorithms outperform others when none of the non-Gaussianity, purity, and two-pure-children holds. Generally, SID and SHD are used in the case where there exists no latent variable [8,9]. In Section 6, since only our algorithms can recover the whole causal structure involving both latent and observed variables while others can only recover the latent causal structure, we only report the SHD of our algorithms, the average of which is 3.9 and 5.5 on $\mathcal{G}_1$ and $\mathcal{G}_2$ with sample size $N=2000$. In fact, the evaluation metrics used in our paper can sufficiently demonstrate the superiority of our algorithms. Our algorithms achieve 0% and 20% error rate on $\mathcal{G}_1$ and $\mathcal{G}_2$ while others always achieve 100% error rate. This means that in an ideal case where PC-MIMBuild makes no mistake, our algorithms can recover the correct latent causal structure in all cases for $\mathcal{G}_1$ and in 80% cases for $\mathcal{G}_2$ while other algorithms always return wrong results. In Appendix A.1, we have provided extensive experimental results on many other causal graphs. In particular, we also consider the scenario where there exists no latent variable. We are not sure what "synthetic datasets with known latent nodes" means, could you please provide more explanations? Last but not least, please note that the main contributions of our paper lie in our exhaustive theoretical analyses rather than empirical results.

Dear Reviewer 7d8K:

Thanks again for your efforts in reviewing. We are looking forward to your reply. Would you mind checking our response and confirming if there are unclear explanations?

Best, Authors

Dear Reviewer 7d8K:

Thanks again for your time and labor in reviewing our paper. We have tried our best to address your concerns, including but not limited to more theoretical analyses (e.g., Appendix C.1), more experimental results (e.g., Section 6 in the main text, Appendix A.1), and more detailed explanations (e.g., Section 5 in the main text, Appendix D). Benefiting from your suggestions, we believe that our paper is self-contained enough. As the deadline for rolling discussion (Nov 22nd) approaches, we would be happy to take this opportunity to have more discussions. If our rebuttal has addressed your concerns, we would be grateful if you could re-evaluate our paper. Thanks!

Best, Authors

Dear reviewer 7d8K,

Thanks very much for your kind reply. We are glad that our rebuttal has addressed most of your concerns, and we are also happy to give more discussion on nonlinear relations between observed variables.

We agree that many causal discovery approaches (with sufficiency assumptions) don't rely on the linearity assumption. However, please note that recovering the whole causal structure involving both latent and observed variables is much more challenging than causal discovery without latent variables. Besides, most previous works about latent causal structure learning [2,3,4,5,6] directly employed the purity assumption that there is no causal relation between observed variables, and some studies avoiding the purity assumption [1,7] also assumed linear causal relations between observed variables.

Nonetheless, we still delve deeper into non-linearity and provide more discussions in Appendix C.1. Here we present two important conclusions.

1. If only causal relations between $O_1$ and $O_2$ are nonlinear where {$O_1,O_2$} $\subset \mathbf{O}$ is not a pseudo-pure pair, then all theoretical results in Section 3.1, 3.2, and 3.3 still hold.

2. If all causal relations are nonlinear but follow a special post-nonlinear model defined as Equation (28), then all theoretical results in Section 3.1 and 3.2 still hold.

We hope the above results can address your concerns, at least partially. Finally, please note that the main focus of our work still lies in the "linear latent variable models". After all, even the linear problems with latent variables have not been completely solved. Therefore, non-linearity is somewhat out of our scope, and we list it as our future work. Anyway, thanks again for your constructive suggestions and kind feedback!

Reference

[1] Silva, Ricardo, et al. "Learning the Structure of Linear Latent Variable Models." JMLR 2006.

[2] Cai, Ruichu, et al. "Triad constraints for learning causal structure of latent variables." NeurIPS 2019.

[3] Xie, Feng, et al. "Generalized independent noise condition for estimating latent variable causal graphs." NeurIPS 2020.

[4] Xie, Feng, et al. "Identification of linear non-gaussian latent hierarchical structure." ICML 2022.

[5] Huang, Biwei, et al. "Latent hierarchical causal structure discovery with rank constraints." NeurIPS 2022.

[6] Chen, Zhengming, et al. "Some General Identification Results for Linear Latent Hierarchical Causal Structure." IJCAI 2023.

[7] Xie, Feng, et al. "Causal discovery of 1-factor measurement models in linear latent variable models with arbitrary noise distributions." Neurocomputing 2023.

We are very grateful for your time and effort in reviewing our paper and your kind encouragement.

Q1: Careful proofreading would improve the paper further

A1: We have tried our best to avoid typos in the proof and also invited some colleagues to check the proof. We will continually improve the proof before submitting the camera ready.

Q2: Lack of a more systematic understanding of the right identifiability conditions.

A2: Thanks for this constructive suggestion. We have provided some explanations in the first paragraph of Section 3.4. Specifically, we formulate two cases where none of the non-Gaussianity, purity, and two-pure-children assumption holds. The two cases both allow causal edges between observed variables but make different trade-offs between graphical and distributional assumptions. On the one hand, Case I which allows completely arbitrary distribution is more general than Case II requires partial non-Gaussianity. On the other hand, Case II which requires no pure child is more general than Case I which requires one pure child per latent variable.

Q3: Can the conditions be tested?

A3: We have proposed an expedient in the second paragraph of Section 3.4. Roughly speaking, Assumption 2 allows arbitrary distribution while Assumption 3 requires partial non-Gaussianity, we test whether some specific variables are all non-Gaussian. If they are, we choose Algorithm 1+3, otherwise, we choose Algorithm 1+2. Although this expedient is not a perfect method, it is better than most previous works that directly circumvented this problem. In fact, testing assumptions is a quite hard problem with only observation data, especially when there exist latent variables. On the other hand, this is really an important problem and we list it as our future work in Section 7.

Q4: The graphical conditions are still quite restrictive (but probably unavoidable) ……

A4: We agree that some causal questions can be answered without full identification of the causal graph. This is really an interesting research problem and we list it as our future work.

Q5: Part of Section 3 was not very helpful for me because the results are not established at this point.

A5: To solve this problem, we have moved some subsidiary theoretical results to Appendix.

Q6: The definition of the set \mathbb{S} seems to be missing.

A6: Thanks for pointing this out, we define it after Definition 5 (definition of generalized pure pair) in the revised manuscript.

Q7: I could not follow Assumption 2. Maybe this can be clarified.

A7: We are sorry that this causes confusion. We have clarified it in the new manuscript. Assumption 2 means that if a latent variable L has exactly one latent parent L’, three observed children $O_1$, $O_2$, $O_3$, and two of which (without loss of generality, $O_1$ and $O_2$) are its pure children, then the neighbors of $O_3$ are required not to be exactly $L$ and $L’$.

Q8: Why does each variable need a latent parent? It would be nice to generalize the case without latent variables.

A8: Thanks for this constructive suggestion. This inspires us to relax assumptions further, allowing some observed variables to have no latent parent. We introduce a new concept “candidate variable” as Definition 6 to prove that all our theoretical results still hold. Besides, we also provide some experimental results in Appendix A for this point, which shows that if there exists no latent variable in the underlying causal model, our algorithms return no latent variable while others may falsely introduce a latent variable.

Q9: Did you normalize the data?

A9: Yes, following most previous works, we normalize each variable to let them have zero mean.

We are glad that we have addressed your concerns. We have further revised the explanations about the necessity of our assumptions. In fact, to completely understand why assumptions are necessary, readers should be familiar with some concepts (such as trek and choke point) and theorems (such as the Tetrad Representation Theorem) that we defer to the Appendix due to the space limit of the main text. We only provide some high-level explanations in the main text, if you want to completely understand why assumptions are required, please refer to the proofs in the Appendix. By the way, Reviewer nXRg also agreed that "fitting everything into the page limit was a challenge". Besides, we have standardized all variables when performing experiments. Anyway, thanks for maintaining your positive score!

Q6: Concerns about the assumption that no observed variable can be a parent of a latent one.

A6: Since proposed by the seminal work, this assumption (called measurement assumption by some researchers) has almost become a standard assumption for latent causal structure learning. All related works mentioned in our paper made this assumption except [1], which has other significant limitations in that their algorithms are only theoretically sound but computationally intractable. This assumption is believed to hold because generally, observed variables are low-level, concrete objects while latent variables are high-level, abstract concepts [2]. In most cases, the former influence the latter but not vice versa. On the other hand, it is also possible that this assumption is not satisfied, so in Section 7, we have listed it as our future work.

Q7: What does “latent commission” mean?

A7: We are sorry that this term causes confusion. We have removed it from the main text except for Section 6 (Experimental Results), where “latent commission” serves as an evaluation metric that is the redundant latent variables divided by the total number of latent variables in the ground truth graph.

Q8: Is there any guidance for how to choose which algorithm/set of assumptions to go with?

A8: We have proposed an expedient for choosing different algorithms in Section 3.4 of the revised manuscript. Roughly speaking, Assumption 2 allows arbitrary distribution while Assumption 3 requires partial non-Gaussianity, we test whether some specific variables are all non-Gaussian. If they are, we choose Algorithm 1+3, otherwise, we choose Algorithm 1+2. Although this expedient is not a perfect method, it is better than most previous works that directly circumvented this problem. In fact, testing assumptions is a quite hard problem with only observational data, especially when there exist latent variables. On the other hand, this is really an important problem and we also list it as our future work in Section 7.

Reference

[1] Adams, Jeffrey, Niels Hansen, and Kun Zhang. "Identification of partially observed linear causal models: Graphical conditions for the non-gaussian and heterogeneous cases." NeurIPS 2021.

[2] Schölkopf, Bernhard, et al. "Toward causal representation learning." Proceedings of the IEEE 2021.

Thanks for your time and effort in reviewing our paper, you have provided constructive suggestions which are really helpful to improve our manuscript.

Q1: Throughout, this paper has an issue with referencing terms and concepts extensively before actually defining them.

A1: In the revised Introduction, we have explained all previously used assumptions when referring to them. Besides, we have also provided an intuition of the term “pure children” and avoided mentioning “pseudo-pure children” in the Introduction. Following your suggestion, we have demonstrated our motivation at a higher level in the fourth paragraph of the Introduction and provided more discussion at the end of Section 2 (Preliminaries), after defining the “pseudo-pure pair” formally. We agree that these modifications lead to easier readability.

Q2: This pattern persists, on a much smaller scale, throughout Section 3.

A2: Following your constructive suggestion, we have reorganized some paragraphs of Section 3. We first present our theoretical results, and then explain how they are used to identify latent variables afterwards.

Q3: Section 3 is high on technical detail and low on intuition.

A3: In the revised manuscript, we have provided more intuitive explanations about our assumptions. There indeed exists a strong motivation behind these assumptions, since without them, the soundness of our theoretical results is not guaranteed. For each assumption, besides clarifying “when it holds” after formulating it, we also explain “why we need it" at a high level after the theoretical results whose soundness heavily relies on it. For instance, we explain why we require Assumption 2(b), i.e., |Nei(L)| >= 4 after Lemma 2 and Corollary 1. We suggest that without Assumption 2(b), Lemma 2 may not hold, and take Figure 2 as an example to show this. We only provide some rough explanations in the main text. To completely understand why assumptions are necessary, readers should be familiar with some concepts (such as trek and choke point) and theorems (such as the Tetrad Representation Theorem) that we defer to Appendix due to the space limit of the main text. Therefore, if you want to get more insights, please read our proofs rather than only the main text.

Q4: Lack of experimental results.

A4: First, we have moved the most representative experimental results to the main text as Section 6, which indicates that our algorithms outperform others when none of the non-Gaussianity, purity, and two-pure-children holds. Moreover, following your suggestion, we have performed comparisons in many other cases including but not limited to $\mathcal{G}_3$: the three-pure-children assumption holds (BPC and FOFC can also yield correct results theoretically); $\mathcal{G}_4$: Assumption 2(a) is violated; $\mathcal{G}_5$: Assumption 2(b) is violated; $\mathcal{G}_6$: the non-Gaussianity, purity, two-pure-children assumptions all hold (GIN can also yield correct results theoretically); $\mathcal{G}_7$: Assumption 3(a) is violated; $\mathcal{G}_8$: Assumption 3(b) is violated. BPC, FOFC, and our algorithms can all achieve low error rates on $\mathcal{G}_3$, GIN and our algorithms can achieve low error rates on $\mathcal{G}_6$ and ours is more robust than GIN, all algorithms cannot yield correct results on other graphs. The detailed experimental results are provided in Appendix A, and we also analyze why our algorithms yield such results.

Q5: The usage of “relatively milder”.

A5: We use this phrase because Assumption 2 is strictly milder than the three-pure-children assumption required, and Assumption 3 is strictly milder than a combination of the non-Gaussianity and two-pure-children assumption. Following you suggestion, we have reduced the frequency of its usage.

Dear Reviewer nXRg:

Thanks a lot for your time and efforts in reviewing this paper. We have tried our best to address the mentioned concerns. Are there unclear explanations and descriptions here? We could further clarify them.

Best, Authors

Dear Reviewer nXRg:

Thanks again for your constructive suggestions. We have tried our best to address your concerns. For instance, we have reorganized our paper to improve the presentation and also provided more extensive experimental results in not only the main text but also the appendix. We believe that these modifications improve our manuscript significantly. As the deadline for rolling discussion (Nov 22nd) approaches, we would be happy to take this opportunity to have more discussions. If our rebuttal has addressed your concerns, we would be grateful if you could re-evaluate our paper. Thanks!

Best, Authors