Scalable Causal Discovery via Vertical Partitioning of Data Features

Causal discovery (CD) methods often incur exponential time complexity in the number of variables which is not scalable. To cope with this problem, recent research has proposed to leverage divide-and-conquer strategies to boost the scalability of a wide variety of existing CD algorithms. However, these strategies require significant overhead to either divide the original problem into sub-problems or aggregate the conquered local solutions into a global solution. Furthermore, failing to assert locally statistical properties such as correctness-and-completeness often impairs the performance of many algorithms. In this paper, we present a novel divide-and-conquer framework that provably performs both problem decomposition and solution aggregation in quadratic time complexity. Furthermore, our framework theoretically guarantees that the local solutions are consistent with the global solution. Finally, extensive evaluation on a wide variety of benchmark datasets show that our framework consistently and significantly and consistently improves the scalability and performance of various CD algorithms.