LayeredLiNGAM: A Practical and Fast Method for Learning a Linear Non-Gaussian Structural Equation Model

Abstract

Structural equation models (SEMs) have been widely used to analyze causal relationships between variables via graphs. Linear non-Gaussian acyclic model (LiNGAM) is a type of SEM mainly assuming that the graph is a directed acyclic graph (DAG), the relationships are linear, and the noises follow non-Gaussian distributions. DirectLiNGAM is a popular LiNGAM learning method with applications in various fields. However, DirectLiNGAM has computational difficulty on large-scale data with many variables. In this study, we point out that the bottleneck of DirectLiNGAM is in estimating a causal order of variables. We also propose an algorithm that improves the computational complexity of estimating a causal order. The main idea is to construct a DAG from multiple layers , and we name the algorithm LayeredLiNGAM . As a result, the computational complexity of estimating a causal order is reduced from $O(Cd^3)$ O ( C d 3 ) to $O((C+d)Td^2)$ O ( ( C + d ) T d 2 ) . We here denote the number of variables by d and the number of detected layers by T . Furthermore, C is the computational complexity required to compute independence between two variables. Experimental results show that LayeredLiNGAM is faster than DirectLiNGAM without quality degradation of learned DAGs on synthetic and real-world datasets.