Recovery of Causal Graph Involving Latent Variables via Homologous Surrogates

Authors: Xiu-Chuan Li, Jun Wang, Tongliang Liu
Primary area: causal reasoning
Keywords: causal discovery, latent variables

Abstract:
Causal discovery with latent variables is an important and challenging problem. To identify latent variables and infer their causal relations, most existing works rely on the assumption that latent variables have pure children. Considering that this assumption is potentially restrictive in practice and not strictly necessary in theory, in this paper, by introducing the concept of homologous surrogate, we eliminate the need for pure children in the context of causal discovery with latent variables. The homologous surrogate fundamentally differs from the pure child in the sense that the latter is characterized by having strictly restricted parents while the former allows for much more flexible parents. We formulate two assumptions involving homologous surrogates and develop theoretical results under each assumption. Under the weaker assumption, our theoretical results imply that we can determine each variable's ancestors, that is, partially recover the causal graph. The stronger assumption further enables us to determine each variable's parents exactly, that is, fully recover the causal graph. Building on these theoretical results, we derive an algorithm that fully leverages the properties of homologous surrogates for causal graph recovery. Also, we validate its efficacy through experiments. Our work broadens the applicability of causal discovery. Our code is available at: https://github.com/XiuchuanLi/ICLR2025-CDHS

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1729491097840

thread_type:
official_review

<thread_object>
creator: reviewer_b7br

<content>
summary:
The paper proposes the use of homologous surrogates to identify latent variables and recover the causal graph. The main contribution of this work is that, unlike pure child variables, homologous surrogates allow for the presence of other parents. Based on this concept, the paper develops corresponding theoretical support and applies it to an algorithm.

strengths:
The innovation of this paper is quite novel, as it uses homologous surrogates to identify latent variables and then recover the causal graph. The supporting theories are also rich, and the corresponding proofs are complete. The theories and propositions applied in the algorithm section are clearly explained, along with examples. These theories are crucial for the implementation of the algorithm. The method proposed in this paper offers a new perspective for discovering latent variables.

weaknesses:
In the third chapter, PARTIAL RECOVERY, the explanation of the algorithm and theoretical part is not very clear in terms of formatting. The formulas and theoretical support needed for the preceding theories and hypotheses are instead explained afterward, which increases the difficulty of reading and affects the logical flow. For example, in "Identifying Observed Root Variables.", in the "Intuition" section, Theorems 1 and 2 are mentioned, so they should be placed before the "Intuition" section. The theories used in the proof should appear before the proof itself, rather than afterwards.

questions:
1. In Algorithm 1, the font of "Thm.1" in line 3 is different from the "Thm.1" in other parts of the pseudocode, which needs attention.
2. For Algorithm 1 and Algorithm 2, the authors use Figure 2 and Figure 3 for explanation, but the tracking example is placed in the figure captions, and the corresponding steps are not explained in detail. It is recommended to add more detailed explanations in the main text to guide readers in understanding the example presented in the figures.
3. Please add your source code link to the paper.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730617159359

thread_type:
official_review

<thread_object>
creator: reviewer_bthh

<content>
summary:
This paper proposes a causal discovery method with latent variables. Instead of assuming that each latent variable has multiple pure children, they assume that each latent variable has at least one homologous surrogate. They define homologous surrogates and develop identifiability analysis under the homologous-surrogate assumptions. Experiments show the efficacy of their proposed algorithm.

strengths:
1)	The authors tackle a significant but challenging causal discovery problem, that is, identifying latent variables and recovering causal relations between all latent and observed variables.

2)	They introduce two assumptions about the defined homologous surrogates, based on which they develop partial and full identifiability theories. They also propose an algorithm to uncover the causal relationships between latent and observed variables.

weaknesses:
1. The algorithm’s complexity is high, i.e., $O(|O|^4)$ and $O(|O|^2 |L|^2)$ for Algorithms 1 and 2, respectively, which could limit its real-world application. It might be better to give empirical complexity analysis in the experiments, compared with other baselines.

2. Regarding the simulated causal graphs in Figure 5 for the experiments, I think the networks are all small. It could help to investigate the performances when there are more latent variables and when the causal relations between latent variables are sparse.

3. It might be better to give simple descriptions and basic conclusions of the experiment on the real-world dataset Holzinger and Swineford, in the main paper. BTW, from Appendix C, the performances on such a real-world dataset look not satisfactory.

4. It is good to give examples for the definitions. But I think giving examples for the theorems also matters since it is hard to catch the main idea or intuitions for the basic theorems.

questions:
1.	In Equation (7), how are the parents $O_j$ of $O_i$ identified? $O_j$ here might be observed ancestors of $O_i$? It is not clear which step aims to find the parents. Since $M_O^O$ is derived from Algorithm 1, which could contain some spurious edges.

2.	As illustrated by the authors, their algorithms suffer from cases with small sample sizes but could achieve ideal performances when assumptions are met and the sample sizes are large enough. For example, in ideal Case 2 of the experiments, how many samples are needed to achieve the ideal results?

3.	If the number of latent variables is not estimated correctly, what would happen? Did it greatly impact the final results?

4)	The following paper [1] tackles the same problem and also allows non-pure children. Hence I suggest discussing the differences and connections with it.

[1] Xie F, Huang B, Chen Z, et al. Generalized independent noise condition for estimating causal structure with latent variables[J]. Journal of Machine Learning Research, 2024, 25: 1-61.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730681074294

thread_type:
official_review

<thread_object>
creator: reviewer_au92

<content>
summary:
This paper proposes a method for causal discovery with latent variables while relaxing the common assumption that requires the existence of pure children. Instead, the method relies on the condition of homologous surrogates, which can have multiple parents. The proposed algorithms are validated on synthetic data.

strengths:
1. The theoretical results are clearly stated with all definitions introduced clearly.

2. The figures are helpful in understanding the method.

3. Experiments in various settings validate the effectiveness of the algorithm.

4. The limitations have been discussed explicitly.

weaknesses:
1. Since "homologous surrogate" is a newly introduced term, it would be helpful to provide a concrete example immediately when it is first mentioned in the manuscript. This would aid readers in understanding the concept more intuitively.

2. Some of the most closely related works have not been mentioned in the introduction. For example, [Dong et al., 2024] consider almost the same problem with a very similar motivation, i.e., relaxing the structural assumptions among latent and observed variables. That work also allows the existence of children for observed variables. Currently, the discussion was only in the remark and related work at the end of the manuscript, but not in the introduction.

3. In line 82, it states that the considered setting is new in causal discovery. However, it might not be accurate since causally-related latent variables have been considered before, even in the presence of observed variables' children. I understand that omitting works such as [Dong et al. 2024] in the introduction would make the story clearer, but it might introduce confusion for readers less familiar with the field.

4. In line 45, it seems to state that [Jin et al. 2024] make the pure children assumption, which might also not be true.

questions:
Please refer to the comments above. Some statements in the current manuscript are not precise, and the overlooking of some closely related work in the introduction may introduce confusion about the unique contributions of this work.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730737664629

thread_type:
official_review

<thread_object>
creator: reviewer_uc12

<content>
summary:
This paper introduces the concept of homologous surrogates to address the challenges associated with causal discovery involving latent variables. It formulates two assumptions regarding homologous surrogates and develops theoretical results based on each assumption. Under the weaker assumption, the authors demonstrate the feasibility of partially recovering the causal graph by identifying the ancestors of each variable. The stronger assumption facilitates the exact identification of each variable's parents, enabling full recovery of the causal graph. Additionally, the paper proposes an algorithm that effectively leverages the properties of homologous surrogates for causal graph recovery and validates its effectiveness through experimental results.

strengths:
1. This paper deals with a causal structure learning problem involving latent variables, which is significant for the field of causal discovery.

2. The authors proposes a method for identify the causal structure via the homologous surrogates under mild assumptions.

weaknesses:
1. The representation needs refinement, as the content of the paper lacks logical flow and coherence, which makes it difficult for readers to follow the main points.

2. The technical contributions appear to be somewhat constrained. This paper draws upon two established methodologies, pseudo-residuals and causal effect estimation via cumulants. It introduces the concept of homologous children, which is fundamentally equivalent to the notion of pure children.

3. The authors mentioned that their work expands the applicability of causal discovery methods, and that homologous surrogates aid in causal discovery with latent variables. However, in the experimental results involving real-world data, their proposed method performs poorly. The authors believe this is due to a limited sample size. So, are there more suitable real-world datasets available to validate the method proposed in this paper?

questions:
See the weaknesses above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732499342402

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We sincerely thank all reviewers for their insightful and valuable feedback on our manuscript. Their constructive comments have helped us significantly improve the quality of our work. We have carefully addressed each concern raised and made substantial improvements to the manuscript. The major revisions are summarized below.

We have substantially refined the presentation of our manuscript, especially in Sections 1, 3, and 4, to improve logical flow and coherence. An an example, we discuss this improvement in detail in our response to Q1 of Reviewer uc12

We have provided more detailed discussions on the connections and differences between our work and previous research in Introduction. As an example, we discuss this improvement in detail in our response to Reviewer AU92.

We have provided intuitive explanations and illustrative examples for key theorems. Besides, we have also added more detailed explanations for the illustrative examples of our proposed algorithm. As examples, we discuss this improvement in detail in our response to Q4 of Reviewer BthH and Q3 of Reviewer B7bR.

We have provided more detailed experimental results on more complex causal graphs. As examples, we discuss this improvement in detail in our response to Q1 and Q2 of Reviewer BthH.

We have open-sourced our code following the suggestion of Reviewer B7bR. https://anonymous.4open.science/r/f15G8O29BB

Thank you again for your time and expertise in reviewing our work.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733183144438

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Rebuttal Summary

comment:
Dear reviewers, AC, and SAC:

We sincerely thank all reviewers for taking their valuable time to read our paper, provide constructive suggestions, and actively engage in discussions. We are also very grateful to AC and SAC for organizing high-quality review process. In the last couple of weeks, we have tried our best to address each concern of all reviewers and integrated these changes into our revised manuscript. The main revisions are summarized as follows.

1. To help readers better understand the position of our work in the field of causal discovery, we have added the following content to the Introduction section: a well-structured review of previous research on causal discovery with latent variables, along with a comprehensive analysis comparing our work with closely related studies that rely on the pure children assumption.

2. To help readers better comprehend our theoretical result, we provide both intuitive explanations and illustrative examples for the key theoretical results such as Theorems 1, 2, 3.

3. To help readers better follow our algorithm, we have provided more detailed explanations at the end of Sections 3 and 4 for the running examples presented in Figures 3 and 4. Besides, we have provided more comprehensive experimental results shown as Table 1 on more complex causal graphs shown as Figure 5. Finally, we have released our source code through an anonymous link (https://anonymous.4open.science/r/f15G8O29BB).

We believe these revisions have substantially improved our paper, and we will continue to refine our paper in the future. Also, we would like to highlight the main contributions of our paper below.

1. We propose a new concept called homologous surrogate, which fundamentally differs from the conventional pure children in the sense that the latter is characterized by having strictly restricted parents while the former allows for much more flexible parents.

2. We formulate two assumptions involving homologous surrogates and develop novel theoretical results under each assumption. These theoretical results imply that the causal graph can be partially/fully recovered under the weaker/stronger assumption.

3. Building on our theoretical results, we derive a systematic and innovative algorithm which fully leverages the properties of homologous surrogates for causal graph recovery.

We sincerely hope our work could contribute to the community and advance the development of causal discovery. Thanks again for your efforts.

Sincerely,\
Submission 217 Authors.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces the concept of homologous surrogates to address the challenges associated with causal discovery involving latent variables. The paper has developed new theoretical results regarding this new concept, which establish that the causal graph can be partially or fully recovered under some reasonable assumptions regarding the homologous surrogates. Building on the established theoretical results, the paper derives a principled and effective algorithm for causal graph recovery.

Following the rebuttal, all reviewers lean towards accepting this paper. Overall, the rebuttal has been effective in addressing key concerns raised by the reviewers, as summarized below.

Reviewer uc12 raised concerns regarding the presentation of the technical narratives as well as several clarification questions regarding the novelty of the introduced concept and limitation of the proposed methods in some experiment settings with limited sample sizes. The authors have revised the paper substantially to address concerns regarding clarity. The rebuttal has also acknowledged the limitation of the proposed method in experiments with limited sample sizes. But, this limitation clearly does not negate the contribution here. 

Reviewer AU92 raised concerns regarding the lack of examples, discussion of related work, and clarification of the novelty of the newly introduced concepts. The rebuttal has satisfactorily addressed these concern and the reviewer has adjusted the rating accordingly.

Reviewer B7br raised concerns regarding the paper organizations, explanations for the examples, and source code releases. The rebuttal has addressed these points sufficiently, retaining the reviewer's acceptance rating.

Reviewer BthH raised concerns regarding the complexity of the proposed algorithm, lack of experiments with larger network sizes, and lack of simple examples for definitions. The rebuttal has provided extra experiment results and provided empirical complexity analysis. The reviewer has not responded to the authors' follow-up messages but the rating remains positive. I also think the detailed rebuttal has addressed the raised concerns sufficiently.

Given the consensus, I recommend that this paper be accepted for publication.