A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables

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.

Many scientific questions ask not only which things are related, but which things cause others. Learning such cause-and-effect maps from data is difficult, especially when some important factors are unobserved—for example, a hidden genetic, environmental, or social factor that influences several measured variables. Existing methods can handle hidden factors, but they often become slow because they must repeatedly check many possible relationships among all variables. In this work, we introduce DiCoLa, a divide-and-conquer framework for causal discovery with hidden variables. Instead of solving one large problem at once, DiCoLa automatically splits it into smaller pieces, learns causal information within each piece, and then carefully merges the pieces back together. We prove that, when the underlying causal discovery method is correct, this splitting and merging process preserves the final causal structure. Experiments show that DiCoLa can make several widely used causal discovery algorithms much faster while maintaining similar accuracy. This makes causal discovery more practical for complex systems in areas such as biology, medicine, and other sciences where not every relevant variable can be measured.