Learning linear acyclic causal model including Gaussian noise using ancestral relationships
This work addresses a computational bottleneck in causal discovery for researchers and practitioners, but it is incremental as it builds on prior hybrid methods like PC-LiNGAM.
The paper tackles the problem of learning causal directed acyclic graphs (DAGs) from data, specifically for linear models with Gaussian noise, by proposing a new algorithm that reduces the factorial time complexity of the existing PC-LiNGAM method to a lower complexity, improving computational efficiency.
This paper discusses algorithms for learning causal DAGs. The PC algorithm makes no assumptions other than the faithfulness to the causal model and can identify only up to the Markov equivalence class. LiNGAM assumes linearity and continuous non-Gaussian disturbances for the causal model, and the causal DAG defining LiNGAM is shown to be fully identifiable. The PC-LiNGAM, a hybrid of the PC algorithm and LiNGAM, can identify up to the distribution-equivalence pattern of a linear causal model, even in the presence of Gaussian disturbances. However, in the worst case, the PC-LiNGAM has factorial time complexity for the number of variables. In this paper, we propose an algorithm for learning the distribution-equivalence patterns of a linear causal model with a lower time complexity than PC-LiNGAM, using the causal ancestor finding algorithm in Maeda and Shimizu, which is generalized to account for Gaussian disturbances.