High-dimensional causal discovery based on heuristic causal partitioning

Causal discovery is one of the most important research directions in the field of machine learning, aiming to discover the underlying causal relationships in the observed data. In practice, the time complexity of causal discovery will grow exponentially with increasing variables. To alleviate this problem, many methods based on divide-and-conquer strategies have been proposed. Existing methods usually partition the variables heuristically using scattered variables to achieve the dividing process, which makes it difficult to minimize vertex cut-set C and then leads to diminished causal discovery performance. In this work, we design an elaborated causal partition strategy called Causal Partition Base Graph (CPBG) to solve this problem. CPBG uses a set of low-order conditional independence (CI) tests to construct a rough skeleton S corresponding to the observed data and takes a heuristic method to search S for the optimal vertex cut-set C. Then the observed data can be partitioned into multiple variable subsets. We therefore can run a causal discovery method on each part and finally obtain the complete causal structure by merging the partial results. The proposed method is evaluated by various real-world causal datasets. Experimental results show that the CPBG method outperforms its existing counterparts, which proves that the method can support more effective and efficient causal discovery. The source code of the proposed method and all experimental results are available at https://github.com/DreamEdm/Causal.