LAUSR

Abstract Recovering causal relationships from observed data is crucial to a variety of applications. Due to the curse of dimensionality, general causal discovery methods such as constraint-based methods and functional model based methods are not quite effective and efficient for large and high-dimensional data sets. Thus, some causal partitioning methods have been proposed to handle this problem. However, existing causal partitioning methods rely on high-order conditional independent (CI) tests, which makes them inefficient in handling dense causal graphs. Therefore, high-dimensionality is still a big challenge to these methods. In this work, we propose a new split-and-merge strategy to enable effective and scalable causality discovery. Different from the existing methods, our method uses only low-order CI tests, can get more accurate results and is applicable to various scenarios. We provide both theoretic analysis and empirical evaluation on the proposed method. Experiments on various real-world causal graphs show that the proposed method outperforms the stat-of-the-art method in terms of accuracy, efficiency and scalability. For high-dimensional cases, our method is much faster than the counterpart by one to three orders of magnitudes.