# QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs

arXiv: https://arxiv.org/abs/2410.23155 · HTML: https://mlsanity.com/paper/2410.23155/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 49 references that are in the map.
- First posted on arXiv 30 Oct 2024.

## Builds on (most cited first, 15 of 15)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/1906.04477/) (2019)
- [Causal-learn: Causal Discovery in Python](https://mlsanity.com/paper/2307.16405/) (2023)
- [Optimal whitening and decorrelation](https://mlsanity.com/paper/1512.00809/) (2015)
- [Diffusion Models for Causal Discovery via Topological Ordering](https://mlsanity.com/paper/2210.06201/) (2022)
- [Greedy Relaxations of the Sparsest Permutation Algorithm](https://mlsanity.com/paper/2206.05421/) (2022)
- [Structural Agnostic Modeling: Adversarial Learning of Causal Graphs](https://mlsanity.com/paper/1803.04929/) (2018)
- [Fast Scalable and Accurate Discovery of DAGs Using the Best Order Score Search and Grow-Shrink Trees](https://mlsanity.com/paper/2310.17679/) (2023)
- [Theory Refinement on Bayesian Networks](https://mlsanity.com/paper/1303.5709/) (2013)
- [Ordering-Based Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/1910.09014/) (2019)
- [A Recursive Markov Boundary-Based Approach to Causal Structure Learning](https://mlsanity.com/paper/2010.04992/) (2020)
- [Learning Bayesian Networks in the Presence of Structural Side Information](https://mlsanity.com/paper/2112.10884/) (2021)
- [Recursive Causal Discovery](https://mlsanity.com/paper/2403.09300/) (2024)
- [Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables](https://mlsanity.com/paper/2208.06935/) (2022)
- [Learning Large Causal Structures from Inverse Covariance Matrix via Sparse Matrix Decomposition](https://mlsanity.com/paper/2211.14221/) (2022)

## Built on by (most cited first, 1 of 1)

- [Graph Learning Is Suboptimal in Causal Bandits](https://mlsanity.com/paper/2510.16811/) (2025)

## Abstract (arXiv)

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.