A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables
This work addresses the computational bottleneck of constraint-based causal discovery in high-dimensional settings with latent variables, a common real-world scenario where prior divide-and-conquer methods fail.
The paper proposes DiCoLa, a recursive decomposition framework that extends divide-and-conquer causal discovery to settings with latent variables, achieving significant computational efficiency gains across multiple algorithms while maintaining theoretical soundness.
Constraint-based causal discovery is widely used for learning causal structures, but heavy reliance on conditional independence (CI) testing makes it computationally expensive in high-dimensional settings. To mitigate this limitation, many divide-and-conquer frameworks have been proposed, but most assume causal sufficiency, i.e., no latent variables. In this paper, we show that divide-and-conquer strategies can be theoretically generalized beyond causal sufficiency to settings with latent variables. Specifically, we propose a recursive decomposition framework, termed DiCoLa, that enables divide-and-conquer causal discovery in the presence of latent variables. It recursively decomposes the global learning task into smaller subproblems and integrates their solutions through a principled reconstruction step to recover the global structure. We theoretically establish the soundness and completeness of the proposed framework. Extensive experiments on synthetic data demonstrate that our approach significantly improves computational efficiency across a range of causal discovery algorithms, while experiments on a real-world dataset further illustrate its practical effectiveness.