Recovering Linear Causal Models with Latent Variables via Cholesky Factorization of Covariance Matrix
This work addresses the incremental improvement of causal discovery methods for researchers in statistics and machine learning, specifically enhancing efficiency and accuracy in DAG recovery with latent variables.
The paper tackles the problem of recovering directed acyclic graph (DAG) structures from observed data, which is challenging especially with latent variables, by proposing a fast algorithm based on Cholesky factorization of the covariance matrix; it achieves state-of-the-art performance on synthetic and real-world datasets and, with an added optimization step under equal error variances, recovers the ground truth graph in most cases, outperforming existing methods.
Discovering the causal relationship via recovering the directed acyclic graph (DAG) structure from the observed data is a well-known challenging combinatorial problem. When there are latent variables, the problem becomes even more difficult. In this paper, we first propose a DAG structure recovering algorithm, which is based on the Cholesky factorization of the covariance matrix of the observed data. The algorithm is fast and easy to implement and has theoretical grantees for exact recovery. On synthetic and real-world datasets, the algorithm is significantly faster than previous methods and achieves the state-of-the-art performance. Furthermore, under the equal error variances assumption, we incorporate an optimization procedure into the Cholesky factorization based algorithm to handle the DAG recovering problem with latent variables. Numerical simulations show that the modified "Cholesky + optimization" algorithm is able to recover the ground truth graph in most cases and outperforms existing algorithms.