Relaxed Sparsest-Permutation Formulation for Causal Discovery at Scale
Researchers introduce SCOPE, a sparse-Cholesky pipeline that matches accuracy of slower baselines while running significantly faster.
Researchers Sunmin Oh, Sang-Yun Oh, and Gunwoong Park have introduced SCOPE (Sparse-Cholesky pipEline), a new approach to causal structure learning that dramatically reduces computational costs while maintaining accuracy. The work, published on arXiv, revisits the sparsest-permutation learning framework for linear structural equation models and relaxes the requirement for exact Cholesky factorization. Instead, SCOPE uses a support-level relaxation that searches for sparse triangular factors over a precision-support screening graph, evaluated via masked zero-fill incomplete Cholesky factorization.
At the population level, the authors prove soundness for Markov equivalence class recovery under common assumptions, and demonstrate robustness to ordering misspecification. In experiments on synthetic and real datasets, SCOPE matches the MEC recovery accuracy of substantially slower baselines while achieving significantly reduced runtime—scaling to problems with 10,000 variables. This opens up causal discovery for high-dimensional datasets that were previously computationally prohibitive, such as genomics or large-scale sensor networks.
- SCOPE replaces exact Cholesky factorization with masked zero-fill incomplete Cholesky, enabling scalable ordering comparisons.
- Matches MEC recovery accuracy of much slower baselines while cutting runtime significantly.
- Scales to datasets with 10,000 variables, a 10x improvement over typical limits.
Why It Matters
Makes causal discovery practical for large-scale datasets, enabling insights in genomics, finance, and sensor networks.