A causal discovery algorithm based on the prior selection of leaf nodes

In recent years, Linear Non-Gaussian Acyclic Model (LiNGAM) has been widely used for the discovery of causal network. However, solutions based on LiNGAM usually yield high computational complexity as well as unsatisfied accuracy when the data is high-dimensional or the sample size is too small. Such complexity or accuracy problems here are often originated from their prior selection of root nodes when estimating a causal ordering. Thus, a causal discovery algorithm termed as GPL algorithm (the LiNGAM algorithm of Giving Priority to Leaf-nodes) under a mild assumption is proposed in this paper. It assigns priority to leaf nodes other than root nodes. Since leaf nodes do not affect others in a structure, we can directly estimate a causal ordering in a bottom-up way without performing additional operations like data updating process. Corresponding proofs for both feasibility and superiority are offered based on the properties of leaf nodes. Aside from theoretical analyses, practical experiments are conducted on both synthetic and real-world data, which confirm that GPL algorithm outperforms the other two state-of-the-art algorithms in computational complexity and accuracy, especially when dealing with high-dimensional data (up to 200) or small sample size (down to 100 for the dimension of 70).