Efficient and Trustworthy Causal Discovery with Latent Variables and Complex Relations

Xiu-Chuan Li, Tongliang LiuICLR 2025 · OpenReview

Causal discovery aims to uncover cause-and-effect relationships purely from observational data. However, most traditional methods rely on a glaringly unrealistic assumption: that we observe all relevant variables in a system. In the real world, unobserved (latent) variables are ubiquitous, and failing to account for them can lead to entirely incorrect causal conclusions.

While newer methods attempt to model these latent variables, they typically enforce strict, unrealistic rules to keep the mathematics tractable. For example, they might assume that observed variables cannot cause latent ones, or that observed variables cannot cause each other. This paper introduces a breakthrough polynomial-time algorithm capable of handling both latent variables and complex causal relations without these restrictive assumptions. Crucially, the algorithm is mathematically proven to be "trustworthy": if its underlying structural assumptions are violated by the data, it raises an explicit error rather than silently outputting a flawed causal graph.

The Challenge: Latent Variables and Complex Relations

Handling complex relations—where observed and latent variables interact freely—is notoriously difficult.

An example of complex causal relations where observed variables ($O$) and latent variables ($L$) interact freely.

In scenarios like the one illustrated above, observed variables might act as causes for latent variables, and latent variables might act as confounders for multiple observed variables simultaneously. The few existing methods that allow for this level of complexity are either computationally intractable (requiring exponential time) or require researchers to know the exact number of hidden variables in advance. This paper bridges this gap by providing a method that is both computationally efficient and highly reliable.

The Proposed Method: A Two-Stage Approach

The authors build their approach on the Linear Non-Gaussian Acyclic Model (LiNGAM) and rely on a "pure children" assumption. This assumption dictates that latent variables leave enough distinct footprints in the observed data—specifically, that they have at least two "pure children" (descendants that do not share other hidden confounders).

To solve the causal discovery problem efficiently, the authors propose a decoupled, two-stage algorithm:

  1. Stage 1 (Bottom-Up Identification): The algorithm sequentially identifies latent variables by locating their "pure children," progressing from the leaves of the causal graph up to the roots. It achieves this using statistical tools like pseudo-residuals—which allow the algorithm to test for conditional independencies even when the conditioning variable is unobserved—and quintuple constraints to group observed variables and infer their hidden parents.
  2. Stage 2 (Top-Down Inference): Once all latent variables are identified, the algorithm infers the causal relationships between all variables, progressing from the roots down to the leaves.

By decoupling the problem into variable identification and relation inference, the algorithm avoids the exponential time complexity of previous state-of-the-art methods, running instead in cubic time $\mathcal{O}(N^3)$.

The "Trustworthiness" Guarantee

In high-stakes fields like medicine or finance, a plausible but incorrect causal graph is far more dangerous than no graph at all. The most novel contribution of this paper is its built-in fail-safe mechanism.

The authors mathematically prove that if the data violates the "pure children" assumption, Stage 1 will leave behind an unresolved structural flaw. Consequently, when Stage 2 attempts to find a valid root variable to begin its top-down inference, it will mathematically fail. This triggers an explicit error signal, preventing the algorithm from confidently outputting a false conclusion.

Experimental Results

The researchers tested their algorithm on both synthetic datasets (generated using linear non-Gaussian acyclic models across various graph structures) and real-world data (a multitasking behavior model dataset).

  • Speed: The proposed method achieved massive speedups compared to PO-LiNGAM, the closest baseline capable of handling complex relations. On synthetic datasets, the new algorithm took roughly 2–5 seconds, while PO-LiNGAM took 36–89 seconds.
  • Accuracy: On datasets satisfying the pure children assumption, the algorithm achieved near-perfect F1-scores (~1.00), matching or beating baselines that completely fail when complex relations are introduced.
  • Trustworthiness in Action: On graphs explicitly designed to violate the pure children assumption, the algorithm successfully raised an error signal (e.g., 7 to 8 times out of 10 runs on synthetic cases). In contrast, all baseline methods confidently outputted incorrect causal structures.

Limitations and Future Directions

While the "pure children" assumption is significantly weaker than the assumptions used in older literature, it remains a restriction. There are real-world systems where latent variables simply do not leave enough "pure" footprints to satisfy this requirement. Additionally, the current model assumes stationary data and acyclic graphs (no feedback loops).

Future work will focus on relaxing the pure children assumption further without sacrificing polynomial-time efficiency, as well as extending the framework to handle non-stationary and cyclic causal relations. Nonetheless, this paper represents a major step forward in making causal discovery both efficient and safe for complex, real-world applications.

Summary updated

Abstract

Most traditional causal discovery methods assume that all task-relevant variables are observed, an assumption often violated in practice. Although some recent works allow the presence of latent variables, they typically assume the absence of certain special causal relations to ensure a degree of simplicity, which might also be invalid in real-world scenarios. This paper tackles a challenging and important setting where latent and observed variables are interconnected through complex causal relations. Under a pure children assumption ensuring that latent variables leave adequate footprints in observed variables, we develop novel theoretical results, leading to an efficient causal discovery algorithm which is the first one capable of handling the setting with both latent variables and complex relations within polynomial time. Our algorithm first sequentially identifies latent variables from leaves to roots and then sequentially infers causal relations from roots to leaves. Moreover, we prove trustworthiness of our algorithm, meaning that when the assumption is invalid, it can raise an error signal rather than draw an incorrect causal conclusion, thus preventing potential damage to downstream tasks. We demonstrate the efficacy of our algorithm through experiments. Our work significantly enhances efficiency and reliability of causal discovery in complex systems. Our code is available at: https://github.com/XiuchuanLi/ICLR2025-ETCD
BibTeX
@inproceedings{li2025efficient,
  author = {Xiu-Chuan Li and Tongliang Liu},
  title = {{Efficient and Trustworthy Causal Discovery with Latent Variables and Complex Relations}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=BZYIEw4mcY},
}
Figure