acceptodds
Under review as a conference paper at ICLR 2027

ReSP: Relaxed Sparsest-Permutation for Causal Discovery at Scale

Abstract

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 variables with and improves recovery as the sample size increases to in weak-signal experiments. Full-feature TCGA analysis further yields greater directional agreement with validated biological regulatory knowledge than feature-partitioned approaches.

Primary area:
causal reasoning
Keywords:
Scalable causal discovery, High-dimensional structure learning, Relaxed Sparsest-permutation, Precision-support relaxation, Linear structural equation models

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_2uj5OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper provides a new approach to perform scalable causal discovery by leveraging a sparsest-permutation approach.

Critical strengths
  • Scalable causal discovery is a timely topic that still requires major research efforts.
  • The theoretical population-level guarantees of the paper are meaningful and important for the field.
  • The combination with a simple instantiation is sound and seems to yield promising results.
Critical weaknesses
  • The authors do not precisely define the notion of scalability, and that definition is essential to understand how their algorithm truly handles real-world causal systems.

  • It is not clear what assumptions are made on the structure of the DAG (if any) to make the system scalable.

  • The simulation results are confined to mostly linear use cases and the breast cancer use case does not provide major insights.

Questions for authors
  • How practical is assumption 2 in real causal systems?
  • What is your definition of scalable and how do your result support that definition?
  • Can you expand the experiments to meaningful non-linear use cases?
  • What is the value extracted out of the breast cancer use case?
3 comments

Weakness 1 & Question 2

Thank you for the opportunity to clarify scalability, a central contribution of our work. By scalability, we mean the ability to learn a graph over the full set of variables in a high-dimensional dataset within practical computational budgets. We support this notion through both computational analysis and full-dataset experiments.

ReSP makes SP computationally more accessible by relaxing the coupling between each ordering and its exact numerical Cholesky factor through an ordering-agnostic precision-support constraint. This formulation prevents ordering-dependent fill from expanding candidate support and enables efficient candidate evaluation using sparse-Cholesky techniques. Given the shared precision estimate, evaluating KK candidate orderings costs O(Kpndm2)O(Kpnd_m^2) under the stated conditions. Theorem 3.2 establishes when this relaxation preserves SP's SMR-based MEC-identification guarantee, alongside support confinement beyond the identification regime.

Empirically, SCOPE handles p=104p=10^4 variables and analyzes all 16,325 TCGA variables without feature partitioning. These runs also yield reliable structural recovery in simulations and directional information beyond random orientation in TCGA, demonstrating that the computational gains support informative graph learning at these scales. We will make this definition and its theoretical and empirical support explicit in the revised manuscript.

Weakness 2

Thank you for prompting us to clarify the assumptions underlying our scalability. Our scalability relies on both linearity and sparsity, with the latter characterized by a small maximum degree dmd_m of the graph defined by the mask. Linearity enables precision-support masking and computationally efficient linear regressions for refinement. ReSP exploits a small dmd_m to restrict candidate neighborhoods and keep the evaluation of each candidate ordering inexpensive: masked factor construction costs O(pdm2)O(pd_m^2) and local refinement costs O(pndm2)O(pnd_m^2) under the stated regression conditions. We will clarify the roles of these conditions in the revised manuscript.

Question 1

SMR is strictly weaker than restricted faithfulness, itself a relaxation of the usual faithfulness assumption [1]. By allowing MEC identification even when faithfulness does not hold, SMR broadens the potential applicability of SP, and [1] also reports higher recovery rates for SP than for PC in the finite-sample settings studied.

This ability to identify the MEC under weaker assumptions makes SP attractive for real-data analysis. Applications of SP and related permutation-based methods range from gene regulatory network inference [2] to the analysis of airfoil data [3] and clinical resting-state fMRI data [4]. To our knowledge, ReSP introduces the first precision-support relaxation of the SP formulation, complementing this flexibility in identification assumptions with computational scalability and thereby extending its practical reach.

Question 3

ReSP offers a natural extension to nonlinear settings that admit a nonparanormal representation [5], with observed variables modeled as coordinatewise invertible monotone transformations of a latent Gaussian SEM. At the population level, transforming each variable to a Gaussian marginal distribution recovers the latent variables up to scale and preserves conditional independences. The population MEC-identification guarantee in Theorem 3.2 therefore carries over to the transformed scale without further assumptions.

By simply adding a Gaussian rank transformation as Step 0, SCOPE achieves recovery close to that obtained directly from the latent Gaussian data: skeleton F1F_1 is 0.6640.664 versus 0.6630.663 at (p,n)=(200,4000)(p,n)=(200,4000), and 0.5810.581 versus 0.6000.600 at (p,n)=(2000,1600)(p,n)=(2000,1600). The extension also remains computationally practical, with recorded median runtimes of approximately one second and twelve minutes in these two settings, respectively. We will add an appendix section presenting the theoretical extension and experimental results.

References

[1] Raskutti and Uhler. “Learning directed acyclic graph models based on sparsest permutations.” Stat, 7(1), 2018.

[2] Solus, Wang, and Uhler. “Consistency guarantees for greedy permutation-based causal inference algorithms.” Biometrika, 108(4):795–814, 2021.

[3] Lam, Andrews, and Ramsey. “Greedy relaxations of the sparsest permutation algorithm.” UAI, PMLR 180:1052–1062, 2022.

[4] Andrews et al. “Fast scalable and accurate discovery of DAGs using the best order score search and grow-shrink trees.” NeurIPS, 36, 2023.

[5] Liu, Lafferty, and Wasserman. “The nonparanormal: Semiparametric estimation of high dimensional undirected graphs.” Journal of Machine Learning Research, 10:2295–2328, 2009.

Question 4

The breast cancer analysis shows that SCOPE captures relationships within biologically meaningful networks reported by [6]. The estimated edges include MCM3--MCM6, MCM5--MCM7, and RFC4--FEN1 within the DNA-replication, repair, and cell-cycle subnetworks highlighted in its luminal A analysis. SCOPE also recovers GATA3--ESR1. Experimental work has shown that GATA3 directly regulates ESR1 expression and is required for estrogen-induced cell-cycle progression in breast cancer cells, providing a biological interpretation for this connection [7]. Another recovered pair is ERBB2--GRB7, whose co-amplification and protein association have been demonstrated in breast cancer [8], connecting this finding to HER2-associated biology.

These findings illustrate the practical value of ReSP's scalability: analyzing all 16,325 genes jointly allows biologically relevant connections to be considered regardless of whether their endpoints would fall into different feature partitions. We will incorporate these biological comparisons and representative examples in the revised manuscript.

References

[6] Koh et al. “iOmicsPASS: Network-based integration of multiomics data for predictive subnetwork discovery.” npj Systems Biology and Applications, 5:22, 2019.

[7] Eeckhoute et al. “Positive cross-regulatory loop ties GATA-3 to estrogen receptor α expression in breast cancer.” Cancer Research, 67(13):6477–6483, 2007.

[8] Stein et al. “The SH2 domain protein GRB-7 is co-amplified, overexpressed and in a tight complex with HER2 in breast cancer.” The EMBO Journal, 13(6):1331–1340, 1994.

Thank you for the clarification. While these resolve some of my concerns, I will maintain my score.

Reviewer_SbfSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper targets scalable causal discovery for Gaussian linear SEMs. It proposes ReSP, a relaxation of sparsest-permutation learning: instead of requiring the exact Cholesky identity, the factor only has to match Ω_π on the precision-support mask and must be zero outside it. Two population results are given: (i) if the candidate set is "IC(0)-admissible" and contains a reverse topological ordering, every minimizer is in the true MEC under SMR; (ii) any feasible solution's edges lie in the moralized skeleton. The practical instantiation, one-pass SCOPE, runs graphical lasso + thresholding to get a mask, a single AMD ordering, masked IC(0), and OLS t-test pruning. Experiments show that masking helps a lot in high dimensions.

Critical strengths
  1. The masking ablation is convincing and practically useful. Table 2 shows that restricting the factor to precision support improves skeleton F1 a lot and cuts downstream time by more than 10×, even with an oracle ordering. This is a clean, reproducible finding that people building large-p pipelines can directly use.
  2. It's a simple pipeline that actually runs at p ≈ 16k jointly. Most competing methods can't be applied to the full TCGA feature set at all. Even if the accuracy story is mixed, a cheap, one-pass method that returns a reasonable CPDAG at this scale has practical value.
Critical weaknesses
  1. The core idea is not new. Using the precision matrix to find the moral graph and then searching for a DAG inside it is the framework of [1], and restricting the search to this conditional-independence graph is what ARGES does [2]. Neither is discussed as prior method work: [1] is cited only for an assumption, and [2] isn't cited at all.
  2. It seems that the theory adds little beyond existing results. The recovery guarantee only kicks in under an extra condition that makes the relaxed factorization identical to the exact one, at which point it is just the original sparsest-permutation result [5]. The "support confinement" guarantee holds by construction. On top of that, the algorithm actually used tries only one heuristic ordering, and nothing guarantees that ordering is the right one, so the theory doesn't really cover the method being evaluated.
  3. In practice, the relaxed factorization doesn't seem to drive the result. With real data, the factor entries inside the mask are basically never exactly zero, so the "sparsity criterion" can't tell orderings apart, and the final graph is decided by simple regression-based pruning. Put together, the method looks like a re-description of a known screen-then-regress pipeline [1, 3, 4].
  4. The scalability claims depend on uneven timing. SCOPE's runtime excludes the precision-matrix estimation step, which by the paper's own complexity analysis is the most expensive part, while baselines are timed end-to-end under a fixed cap. Wherever baselines do finish, SCOPE is clearly less accurate. 5.Methods that use the same precision screen [1, 2, 6] aren't compared, so it's unclear what ReSP adds over "any search inside the screened graph." The tuning parameter in the weak-signal setting is fixed in a way that isn't explained. FROSTY's near-zero scores look like a broken setup. And in the TCGA analysis, baselines are run on random disjoint gene subsets, which by design can't find edges across subsets.

[1] High-Dimensional Learning of Linear Causal Networks via Inverse Covariance Estimation.

[2] High-Dimensional Consistency in Score-Based and Hybrid Structure Learning.

[3] FROSTY: A High-Dimensional Scale-Free Bayesian Network Learning Method.

[4] Efficient Permutation Discovery in Causal DAGs.

[5] Learning Directed Acyclic Graph Models Based on Sparsest Permutations.

[6] Learning Linear Structural Equation Models in Polynomial Time and Sample Complexity.

Questions for authors
  1. What is the end-to-end runtime of SCOPE including graphical lasso (SQUIC) at p = 5,000, 10^4 and 16,325? Do the timeout conclusions change if all methods are timed the same way?
  2. In finite samples, is ‖L̂_π‖_0 (before REFITTEST) ever smaller than |M̂|? If not, please confirm that structure selection comes only from the t-test pruning.
  3. Beyond π_0, when is a candidate set IC(0)-admissible? Is π_AMD admissible in any of your simulated graphs?
  4. How were the fixed λ values in the low-dim and weak-signal sweeps "reference-calibrated"? Was ground truth used?
  5. How does SCOPE compare with GES/BOSS restricted to the same mask M̂ (RGES-CIG/ARGES [2]) and with [1]? This is the comparison that would isolate ReSP's contribution.
  6. TCGA: what forward/reverse ratio does a random orientation of SCOPE's own skeleton give? And how do PC/GES do when run on SCOPE's mask rather than on random partitions?
5 comments

Weakness 1 - novelty

Thank you for these references. Indeed, using precision- and conditional-independence-based screening has been studied previously, and we will make these methodological connections explicit in our revision. [1] infers the moral graph from precision support under a no-cancellation condition and searches for a DAG within it, establishing DAG identification with suitable noise-variance information. ARGES [2] makes an important contribution by showing how adaptive relaxation of a masked search space preserves GES consistency under faithfulness and the requisite regularity conditions.

In comparison, our novelty lies in incorporating this restriction into the optimization formulation of SP [3]. ReSP evaluates candidate orderings proposed using prior knowledge, local search, or heuristics under a common support constraint that can also encode prior knowledge about possible adjacencies. Incorporating this constraint into SP is nontrivial because exact SP ties each ordering to its numerical Cholesky factor, whose support can extend beyond the specified mask. ReSP relaxes this coupling through masked factor equality while retaining SP's sparsity objective. To our knowledge, this is the first SP formulation combining these constraints with an SMR-based MEC-identification guarantee under explicit conditions.

In this paper, the shared structural constraint is instantiated by precision support. This choice offers both theoretical and computational benefits. Under no-cancellation, the off-diagonal support of the population precision matrix equals the skeleton of the moral graph, providing an ordering-independent superstructure that contains all true parent--child adjacencies. Computationally, the common precision-support constraint limits the size of candidate factors and subsequent regression neighborhoods, substantially reducing the cost of evaluating each candidate ordering.

Weakness 2 - Admissibility and its role in MEC recovery

As discussed in our response to W1, our aim is to make SP's identification principle more computationally accessible through a common support constraints, rather than to introduce a stronger identification principle. For precision-support instantiation, the theoretical contribution is to establish when the precision-support relaxation preserves SP's MEC-identification guarantee over a user-specified candidate-ordering set. Here, The candidate set may encode prior knowledge, local-search proposals, or ordering heuristics, whereas the common precision-support constraint governs how each candidate is evaluated. Theorem~3.2 establishes sufficient conditions for this preservation, while our complexity analysis and SCOPE experiments assess the computational value of ReSP.

As you note, the recovery argument relies on the exact factorization restored under admissibility. However, admissibility provides a concrete bridge between SP and sparse-Cholesky methods by identifying candidate orderings for which the relaxed evaluation restores the exact SP comparison. Fill-reducing techniques such as minimum degree ordering [4] and its approximate variant, AMD [5], can therefore be used to seek such candidates.

Weakness 2 - The value of support confinement

Thank you for prompting us to clarify the role of support confinement. Although imposed by construction, its value lies in its computational and statistical consequences. By preventing fill outside the mask, ReSP limits candidate-factor supports and subsequent regression neighborhoods without requiring a correct ordering. In finite samples, refinement only removes edges from the estimated mask, so the number of selected adjacencies outside the true moralized skeleton cannot exceed the number of false-positive mask adjacencies. Existing results on false-positive control in precision-support estimation (e.g., [6]) can thus be used to control these errors.

References

[1] Loh and Bühlmann. “High-dimensional learning of linear causal networks via inverse covariance estimation.” Journal of Machine Learning Research, 15:3065–3105, 2014.

[2] Nandy, Hauser, and Maathuis. “High-dimensional consistency in score-based and hybrid structure learning.” The Annals of Statistics, 46(6A):3151–3183, 2018.

[3] Raskutti and Uhler. “Learning directed acyclic graph models based on sparsest permutations.” Stat, 7(1), 2018.

[4] Scott and Tůma. Algorithms for Sparse Linear Systems. Springer, 2023.

[5] Amestoy, Davis, and Duff. “An approximate minimum degree ordering algorithm.” SIAM Journal on Matrix Analysis and Applications, 17(4):886–905, 1996.

[6] Tran, Cisneros-Velarde, Oh, and Petersen. “Family-wise error rate control in Gaussian graphical model selection via distributionally robust optimization.” Stat, 11(1), 2022.

Weakness 2 - Candidate orderings in theory and experiments

ReSP permits multiple candidate orderings, and SCOPE compares them through refined sparsity; the reported experiments use a one-pass singleton candidate set containing only the AMD ordering. This choice serves two complementary purposes. First, it demonstrates that support-constrained SP evaluation remains practical at the large scales targeted by ReSP, including full-variable real-data analysis, without relying on an expensive ordering search. Second, because AMD is an inexpensive non-oracle heuristic and may be misspecified, it examines whether the shared support constraint can still control ordering-dependent fill, candidate supports, and downstream refinement costs. This singleton choice is not a restriction of the formulation: after the shared precision estimate is computed, any supplied candidate set can be evaluated, with the evaluation cost growing linearly in its size.

As you correctly noted, Theorem 3.2 does not guarantee MEC recovery from the singleton AMD candidate; for the theorem to apply directly, the AMD ordering would have to be both IC(0)-admissible and reverse topological. The robustness result instead provides population-level support confinement for arbitrary candidates, while the single-AMD experiments examine the corresponding structural and computational protection in finite samples. Finally, the oracle-ordering ablation separates candidate quality from support-constrained evaluation: the AMD--π0\pi_0 gap reflects the value of better ordering information, whereas the masked--unmasked comparison under each ordering isolates the benefit of the ReSP constraint.

Question 3

Beyond π0\pi_0, any ordering whose masked IC(0) factor creates no product fill outside the mask is admissible, and any candidate set consisting of such orderings is IC(0)-admissible. For maximum in-degree one, the population moral graph is a forest, on which minimum-degree elimination produces no fill [4,5]. This supplies admissible candidates beyond a particular reverse topological ordering. Using the population precision, AMD was IC(0)-admissible throughout the evaluated d=1d=1 simulations, whereas it was not admissible in the evaluated d=5d=5 simulations. Appendix E.1 additionally reports stronger skeleton recovery in the d=1d=1 experiments than in the denser d=5d=5 setting.

Weakness 3

As correctly pointed out, the factor entries inside the bask are basically never exactly zero; HOWEVER, the magnitude of the non-zeros depends on given ordering. In turn, the t-test in REFITTEST determines whether these small non-zeros should actually be zeros. In comparison, SP uses conditional-independence tests [3]; greedy SP admits BIC-based and partial-correlation-thresholding formulations [7], and BOSS uses BIC for model selection [8]. These methods assess sparsity through statistically selected supports or models, rather than literal nonzeros in an unthresholded estimate.

SCOPE likewise uses statistical support selection to evaluate its sparsity criterion, rather than merely applying a screen-then-regress pipeline. REFITTEST supplies the retained support for each candidate ordering, and Algorithm 1 minimizes the number of retained off-diagonal entries in L~π\widetilde L_\pi to select the refined factor and its associated ordering.

Question 2

We appreciate your question that motivate us to clarify an important distinction between L^\widehat L and L~\widetilde L. SCOPE considers L^\widehat L as an intermediate result and its cardinality is not used. Thus, even when ∥L^π∥0=∣M^∣\lVert \widehat{L}_{\pi} \rVert_{0} = |\widehat{M}| in finite samples, this does not mean that the entire structure is selected by the tt-tests. As discussed above, different orderings induce different candidate-parent regressions, tt-test results, and retained supports L~\widetilde L. For each candidate ordering π\pi, SCOPE evaluates its sparsity criterion by counting the retained off-diagonal entries in the refined factor L~π\widetilde L_\pi.

References

[3] Raskutti and Uhler. “Learning directed acyclic graph models based on sparsest permutations.” Stat, 7(1), 2018.

[4] Scott and Tůma. Algorithms for Sparse Linear Systems. Springer, 2023.

[5] Amestoy, Davis, and Duff. “An approximate minimum degree ordering algorithm.” SIAM Journal on Matrix Analysis and Applications, 17(4):886–905, 1996.

[6] Tran, Cisneros-Velarde, Oh, and Petersen. “Family-wise error rate control in Gaussian graphical model selection via distributionally robust optimization.” Stat, 11(1), 2022.

[7] Solus, Wang, and Uhler. “Consistency guarantees for greedy permutation-based causal inference algorithms.” Biometrika, 108(4):795–814, 2021.

[8] Andrews et al. “Fast scalable and accurate discovery of DAGs using the best order score search and grow-shrink trees.” NeurIPS, 36, 2023.

Weakness 4 & Question 1

Thank you for this important point. We originally reported downstream runtimes for two reasons. First, using a common precision estimate allowed us to isolate ReSP's formulation-level contribution: evaluating SP under a supplied support constraint. Second, for the precision-support specialization, the cost of constructing the precision-support mask depends on the estimator and its implementation. We chose graphical lasso, implemented with SQUIC, as a representative approach. ReSP can also use precision support estimated by scalable alternatives such as HP-ACCORD [9] and HP-CONCORD [10].

The precision-support mask and its connection to the moralized skeleton under no-cancellation are central to our analysis. We therefore agree that an end-to-end comparison should include the cost of constructing this mask, and we now report both downstream runtimes and runtimes including SQUIC. Including SQUIC, SCOPE takes approximately 1.3 hours in the p=5000p=5000 comparison and 2.1--4.2 hours in the recorded p=104p=10^4 runs. For TCGA (p=16,325p=16{,}325), the recorded runtime is approximately 0.07 hours.

We therefore use two- and six-hour comparison budgets at p=5000p=5000 and p=104p=10^4, respectively, leaving headroom above these times. Even under the expanded budgets, the timeout conclusions for the original baselines remain unchanged. At p=5000p=5000, none of GES, BOSS, GSP, NOTEARS, GOLEM, PC, or RFD returned a graph within two hours. We will incorporate the precision-inclusive runtime comparison in the revised manuscript.

While some baselines achieve higher accuracy in particular settings, SCOPE uniquely combines meaningful structural recovery with computational feasibility across the full sweeps of all three regimes in our reported comparison. Its skeleton F1F_1 remains between 0.610.61 and 0.670.67 across the low-dimensional sweep, reaches 0.910.91 as the sample size increases in the weak-signal regime, and ranges from 0.580.58 to 0.670.67 in the high-dimensional regime through p=104p=10^4. These results are particularly encouraging because SCOPE is a simple instantiation of ReSP using a single AMD ordering. They demonstrate the promise of ReSP's formulation and motivate more effective algorithms that retain its computational advantages.

Weakness 5 & Question 5

Thank you for suggesting comparisons using the same precision mask M^\widehat M. The results clarify ReSP's contribution by demonstrating how support restriction can improve structural recovery and computational feasibility across different algorithms.

Masking improves structural recovery in several comparisons. At p=200,n=4000p=200,n=4000, restricting GES to the mask (RGES-CIG) improves nSHD (2.34→0.7302.34 \rightarrow 0.730). PC also achieves lower nSHD with masking: 0.823→0.6650.823 \rightarrow 0.665 at p=200,n=4000p=200,n=4000, and 0.862→0.7140.862 \rightarrow 0.714 at p=2000,n=1600p=2000,n=1600. The benefit depends on the method, with BOSS providing an exception in the low-dimensional comparison.

Masking also expands computational feasibility. At p=2000,n=40000p=2000,n=40000, unrestricted GES does not finish within one hour, whereas RGES-CIG completes every trial within that downstream computation budget. PC likewise shows a substantial reduction in downstream runtime at p=2000,n=1600p=2000,n=1600. At p=5000p=5000, RGES-CIG and masked PC return graphs for all valid trials, with most remaining within the two-hour total budget even after including SQUIC.

Against alternatives using the same mask, SCOPE combines meaningful structural recovery with inexpensive computation. In the weak-signal setting at n=106n=10^6, SCOPE achieves nSHD 0.5240.524, compared with 0.5620.562 for RGES-CIG and 0.5590.559 for ARGES-CIG, while RGES-CIG and masked PC are more accurate at p=5000p=5000. At that scale, their median downstream runtimes are approximately 49 and 40 minutes, respectively, compared with 3.5 seconds for SCOPE, which remains within the SQUIC-inclusive budget in every valid trial. Restricted BOSS and ARGES-CIG still fail to finish within the comparison budgets at p=2000p=2000, while SCOPE completes. These results illustrate the computational value of SCOPE's simple implementation using a single AMD ordering.

We also evaluated the other precision-based approaches. [11] attains nSHD 0.2970.297 at p=200p=200 but exceeds the 1,800-second budget at p=800p=800. Our subset-DP implementation based on [1] times out in the smaller-scale comparisons.

Together, the demonstrated benefits of masking and the performance of SCOPE motivate further development of algorithms that directly optimize ReSP while retaining its computational advantages. Appendix G, Tables 8--9, reports the detailed F1F_1, nSHD, and runtime comparisons.

Reviewer_9D5HOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes ReSP, which evaluates variable orderings using a Cholesky factor restricted to the estimated precision-matrix support. Its SCOPE implementation then uses graphical lasso, one approximate minimum-degree ordering, masked incomplete Cholesky factorization, and local edge pruning. Experiments are conducted over large scale of nodes and data points to show the scalability and tolerance to high-dimensionality (where regular faithfulness assumptions are likely to be violated).

Critical strengths
  • The study on sparsest Markov representation (SMR) assumption, which is weaker than faithfulness, is important especially for real-world data.
  • The precision-support masking and the associated Cholesky decomposition are interesting and practical ideas with a clear motivation.
  • The experiments look good. E.g., at p=10^4, adding the mask to the refined AMD pipeline improves skeleton F1 from 0.213 to 0.582 and cuts the reported downstream time from 222.4 to 15.5 seconds. It seems that the masking method can be a useful plug-in for many other pipelines.
Critical weaknesses
  • About the theoretical contribution, the identification result seems narrower than the paper’s framing suggests.

    • Theorem 3.2 requires an IC(0)-admissible candidate set containing a reverse topological order.
    • Under admissibility, Lemma C.1 restores exact factorization, so the MEC argument does not explain why the relaxed factor or the single AMD ordering should recover the true class.
    • The unrestricted guarantee only constrains edges to the moralized skeleton, which can contain noncausal edges.
  • On scalability, the headline runtimes for precision-based methods start with the precision estimate already given; graphical lasso is part of the proposed pipeline and may dominate total cost.

Questions for authors

see weaknesses.

2 comments

Weakness 1

Thank you for prompting us to clarify the conditions and implications of our theoretical results. ReSP combines precision-support masking with the sparsest-permutation objective, preserving its SMR-based MEC-identification principle. SMR is strictly weaker than restricted faithfulness, itself a relaxation of the usual faithfulness assumption, and hence SP has been shown to achieve higher finite-sample recovery rates than PC in the settings studied in [1]. Nevertheless, incorporating this mask into SP is nontrivial: exact SP ties each ordering to its numerical Cholesky factor and potentially enlarged support. To our knowledge, ReSP is the first to relax this coupling through masked factor equality and an ordering-agnostic support constraint, enabling computationally restricted candidate evaluation.

Theorem 3.2 identifies sufficient conditions under which this relaxation retains SP's MEC-identification guarantee: under no-cancellation and SMR, an IC(0)-admissible candidate set containing a reverse topological ordering suffices. As you note, the MEC-identification argument relies on the exact factorization recovered under admissibility. However, admissibility provides a bridge between SP and sparse Cholesky methods: fill-reducing ordering techniques can be used to seek admissible candidates, since an ordering that creates no fill outside the mask is admissible. For example, maximum in-degree one yields a forest, on which minimum-degree elimination, including AMD, produces no fill [2, 3].

As you correctly point out that in (iii) that ReSP abides by the moralized skeleton. Although imposed by construction, its value lies in its computational and statistical consequences. By preventing fill outside the mask, ReSP limits candidate-factor supports and subsequent regression neighborhoods without requiring a correct ordering. In finite samples, refinement only removes edges from the estimated mask, so the number of selected adjacencies outside the true moralized skeleton cannot exceed the number of false-positive mask adjacencies. Existing results on false-positive control in precision-support estimation (e.g., [4]) can thus be used to control these errors.

In the revised manuscript, we will clarify the connection between admissibility and sparse Cholesky methods and the value of support confinement beyond the identification regime.

Weakness 2

We agree that graphical-lasso estimation should be included in the scalability analysis. The original downstream timings were reported under a common precision input to compare the post-estimation stages of the precision-based methods; we now additionally report end-to-end runtimes. Including SQUIC, SCOPE takes approximately 1.3 hours in the p=5000p=5000 comparison and 2.1–4.2 hours in the recorded p=104p=10^4 runs. In the remaining settings, most recorded SCOPE trials remain within the original time budgets even after including graphical-lasso estimation.

We therefore use two- and six-hour comparison budgets at p=5000p=5000 and p=104p=10^4, respectively, leaving headroom above these times. The broader observed scalability pattern remains unchanged: in the p=5000p=5000, GES, BOSS, GSP, NOTEARS, GOLEM, and PC still time out under the expanded two-hour budget. We will incorporate the precision-inclusive runtime comparison in the revised manuscript.

Although our experiments use graphical lasso, implemented with SQUIC, as a representative approach, ReSP is not tied to this choice of precision estimator. Scalable alternatives for estimating precision support, including HP-ACCORD [5] and HP-CONCORD [6], provide promising directions for further reducing the precision estimation cost.

References

[1] Raskutti and Uhler. “Learning directed acyclic graph models based on sparsest permutations.” Stat, 7(1), 2018.

[2] Scott and Tůma. Algorithms for Sparse Linear Systems. Springer, 2023.

[3] Amestoy, Davis, and Duff. “An approximate minimum degree ordering algorithm.” SIAM Journal on Matrix Analysis and Applications, 17(4):886–905, 1996.

[4] Tran, Cisneros-Velarde, Oh, and Petersen. “Family-wise error rate control in Gaussian graphical model selection via distributionally robust optimization.” Stat, 11(1), 2022.

[5] Lee et al. “Learning massive-scale partial correlation networks in clinical multiomics studies with HP-ACCORD.” The Annals of Applied Statistics, 19(4):2759–2781, 2025.

[6] Koanantakool et al. “Communication-avoiding optimization methods for distributed massive-scale sparse inverse covariance estimation.” AISTATS, PMLR 84:1376–1386, 2018.

I thank the authors for the clear response. I keep my positive score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Follow-up on our responses

Thank you again for your time and thoughtful feedback. We appreciate the follow-up feedback received so far. As the discussion period is nearing its end, we would be grateful if the other reviewers could also take a look at our responses. We would be happy to clarify any remaining questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.