QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs
This work addresses scalability issues for researchers and practitioners in scientific domains using causal discovery, though it is incremental as it improves efficiency within an existing framework.
The paper tackles the high computational complexity of permutation-based causal discovery in Linear Gaussian Acyclic Models (LiGAMs) by introducing QWO, which speeds up the computation of the best DAG for a given permutation with an O(n^2) speed-up compared to the state-of-the-art BIC-based method, making it highly scalable.
Causal discovery is essential for understanding relationships among variables of interest in many scientific domains. In this paper, we focus on permutation-based methods for learning causal graphs in Linear Gaussian Acyclic Models (LiGAMs), where the permutation encodes a causal ordering of the variables. Existing methods in this setting are not scalable due to their high computational complexity. These methods are comprised of two main components: (i) constructing a specific DAG, $\mathcal{G}^π$, for a given permutation $π$, which represents the best structure that can be learned from the available data while adhering to $π$, and (ii) searching over the space of permutations (i.e., causal orders) to minimize the number of edges in $\mathcal{G}^π$. We introduce QWO, a novel approach that significantly enhances the efficiency of computing $\mathcal{G}^π$ for a given permutation $π$. QWO has a speed-up of $O(n^2)$ ($n$ is the number of variables) compared to the state-of-the-art BIC-based method, making it highly scalable. We show that our method is theoretically sound and can be integrated into existing search strategies such as GRASP and hill-climbing-based methods to improve their performance.