ReSP: Relaxed Sparsest-Permutation for Causal Discovery at Scale

Despite the growing availability of large datasets, causal discovery remains computationally prohibitive at scale. We introduce Relaxed Sparsest-Permutation (ReSP), a support-constrained formulation for linear structural equation models (SEMs) that retains the number of edges in the induced directed acyclic graph (DAG) as the selection criterion while relaxing exact all-entry Cholesky evaluation. ReSP requires the factorization equality only within a precision-support mask, and the ordering-dependent lower-triangular factor must be zero outside it, preventing fill outside the screened graph during candidate ordering evaluation. We establish two population-level guarantees for Gaussian linear SEMs under no-cancellation and sparsest Markov representation assumptions using the true precision-support mask. With a suitable candidate ordering set, every ReSP minimizer induces a DAG in the true Markov equivalence class; even without such candidates, all feasible solutions induce edge sets within the moralized skeleton. We demonstrate ReSP's practical potential through a simple instantiation using a single approximate minimum degree ordering and local refinement. Ablation studies show that masking improves structural accuracy and reduces downstream computational cost. This instantiation scales to $10^4$ variables with $n<p$ and improves recovery as the sample size increases to $10^6$ in weak-signal experiments. Full-feature TCGA analysis further yields greater directional agreement with validated biological regulatory knowledge than feature-partitioned approaches.