Causal Discovery via Cholesky Factorization

Abstract

Discovering the causal relationship via recovering the directed acyclic graph (DAG) structure from the observed data is a challenging combinatorial problem. This paper proposes an extremely fast, easy to implement, and high-performance DAG structure recovering algorithm. The algorithm is based on the Cholesky factorization of the covariance/precision matrix. The time complexity of the algorithm is O(p^2n + p^3), where p and n are the numbers of nodes and samples, respectively. Under proper assumptions, we show that our algorithm takes O((p/)) samples to exactly recover the DAG structure with probability at least 1-. In both time and sample complexities, our algorithm is better than previous algorithms. On synthetic and real-world data sets, our algorithm is significantly faster than previous methods and achieves state-of-the-art performance.

Tasks

Reproductions