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