- 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
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.
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 K candidate orderings costs O(Kpndm2) 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=104 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 dm of the graph defined by the mask. Linearity enables precision-support masking and computationally efficient linear regressions for refinement. ReSP exploits a small dm to restrict candidate neighborhoods and keep the evaluation of each candidate ordering inexpensive: masked factor construction costs O(pdm2) and local refinement costs O(pndm2) 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 F1 is 0.664 versus 0.663 at (p,n)=(200,4000), and 0.581 versus 0.600 at (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.