QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs

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, 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 Gπ. We introduce QWO, a novel approach that significantly enhances the efficiency of computing Gπ for a given permutation π. QWO has a speed-up of O(n2) (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.