Accelerating Recursive Partition-Based Causal Structure Learning

Md. Musfiqur Rahman, Ayman Rasheed, Md. Mosaddek Khan, Mohammad Ali Javidian, Pooyan Jamshidi, Md. Mamun-Or-Rashid

Causal structure discovery from observational data is fundamental to the
causal understanding of autonomous systems such as medical decision support
systems, advertising campaigns and self-driving cars. This is essential to
solve well-known causal decision making and prediction problems associated with
those real-world applications. Recently, recursive causal discovery algorithms
have gained particular attention among the research community due to their
ability to provide good results by using Conditional Independent (CI) tests in
smaller sub-problems. However, each of such algorithms needs a refinement
function to remove undesired causal relations of the discovered graphs.
Notably, with the increase of the problem size, the computation cost (i.e., the
number of CI-tests) of the refinement function makes an algorithm expensive to
deploy in practice. This paper proposes a generic causal structure refinement
strategy that can locate the undesired relations with a small number of
CI-tests, thus speeding up the algorithm for large and complex problems. We
theoretically prove the correctness of our algorithm. We then empirically
evaluate its performance against the state-of-the-art algorithms in terms of
solution quality and completion time in synthetic and real datasets.