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.

通过从观测数据中恢复有向无环图（DAG）结构来发现因果关系是一个众所周知的挑战性组合问题。本文首先提出了一种基于观测数据协方差矩阵的 Cholesky 分解的 DAG 结构恢复算法，该算法快速易实现且具有精确恢复的理论保证。在合成和真实数据集上，该算法比先前的方法明显更快，并达到了最先进的性能。此外，在等误差方差假设下，我们将优化过程纳入基于 Cholesky 分解的算法中以处理带有潜在变量的 DAG 恢复问题。数值模拟表明，修改后的 “Cholesky + 优化” 算法能够在大多数情况下恢复出真实图，并且优于现有算法。