# Relaxed Sparsest-Permutation Formulation for Causal Discovery at Scale

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 61 references that are in the map.
- First posted on arXiv 7 May 2026.

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

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [On the Role of Sparsity and DAG Constraints for Learning Linear DAGs](https://mlsanity.com/paper/2006.10201/) (2020)
- [High-dimensional learning of linear causal networks via inverse covariance estimation](https://mlsanity.com/paper/1311.3492/) (2013)
- [Permutation-Based Causal Structure Learning with Unknown Intervention Targets](https://mlsanity.com/paper/1910.09007/) (2019)
- [Greedy Relaxations of the Sparsest Permutation Algorithm](https://mlsanity.com/paper/2206.05421/) (2022)
- [gCastle: A Python Toolbox for Causal Discovery](https://mlsanity.com/paper/2111.15155/) (2021)
- [Causal Structure Learning Supervised by Large Language Model](https://mlsanity.com/paper/2311.11689/) (2023)
- [Causal Structure Discovery between Clusters of Nodes Induced by Latent Factors](https://mlsanity.com/paper/2207.01237/) (2022)
- [Optimizing regularized Cholesky score for order-based learning of Bayesian networks](https://mlsanity.com/paper/1904.12360/) (2019)
- [Distributionally Robust Formulation and Model Selection for the Graphical Lasso](https://mlsanity.com/paper/1905.08975/) (2019)
- [Efficient Permutation Discovery in Causal DAGs](https://mlsanity.com/paper/2011.03610/) (2020)
- [Causal Discovery in Linear Structural Causal Models with Deterministic Relations](https://mlsanity.com/paper/2111.00341/) (2021)
- [Family-wise error rate control in Gaussian graphical model selection via Distributionally Robust Optimization](https://mlsanity.com/paper/2201.12441/) (2022)

## Abstract (arXiv)

Despite the growing availability of large datasets, causal structure learning remains computationally prohibitive at scale. We revisit sparsest-permutation learning for linear structural equation models and show that exact Cholesky factorization is unnecessary for structure recovery. This observation motivates a support-level relaxation that searches for sparse triangular factors over a precision-support screening graph. The relaxed formulation can be efficiently evaluated via masked zero-fill incomplete Cholesky factorization, enabling scalable comparison of candidate orderings. At the population level, we establish soundness for Markov equivalence class (MEC) recovery under no-cancellation and sparsest Markov representation assumptions, as well as robustness to ordering misspecification. Motivated by these guarantees, we introduce SCOPE, a sparse-Cholesky pipeline that provides a scalable implementation of the relaxed formulation. Experiments on synthetic and real datasets demonstrate that SCOPE matches the MEC recovery accuracy of substantially slower baselines, while achieving significantly reduced runtime and scaling to 10k variables.