Heteroscedastic Causal Structure Learning
Bao Duong Thin Nguyen
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.