Heretofore, learning the directed acyclic graphs (DAGs) that encode the cause-effect relationships embedded in observational data is a computationally challenging problem. A recent trend of studies has shown that it is possible to recover the DAGs with polynomial time complexity under the equal variances assumption. However, this prohibits the heteroscedasticity of the noise, which allows for more flexible modeling capabilities, but at the same time is substantially more challenging to handle. In this study, we tackle the heteroscedastic causal structure learning problem under Gaussian noises. By exploiting the normality of the causal mechanisms, we can recover a valid causal ordering, which can uniquely identify the causal DAG using a series of conditional independence tests. The result is HOST (Heteroscedastic causal STructure learning), a simple yet effective causal structure learning algorithm that scales polynomially in both sample size and dimensionality. In addition, via extensive empirical evaluations on a wide range of both controlled and real datasets, we show that the proposed HOST method is competitive with state-of-the-art approaches in both the causal order learning and structure learning problems.

本研究旨在解决具有异方差噪声的因果结构学习问题。通过利用因果机制的正态性，我们可以恢复一个有效的因果排序，并使用一系列条件独立性检验唯一地识别因果有向无环图。结果是HOST（异方差因果结构学习），一种简单而有效的因果结构学习算法，可以在样本大小和维度上呈多项式规模扩展。通过广泛的实证评估，我们展示了HOST方法在因果顺序学习和结构学习问题上与最先进的方法相比具有竞争力。