acceptodds
Withdrawn from ICLR 2027

COSMIC: Scalable Causal Discovery via Nyström Macro-Tier Peeling

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Recovering causal graphs from purely observational data is essential when experimental interventions are constrained by ethical or logistical barriers. However, ordering-based approaches face severe computational bottlenecks due to repeated kernel computations that scale cubically with sample size and quadratically with graph dimension. We introduce COSMIC, a highly scalable causal discovery framework for nonlinear additive noise models. Our approach integrates a low-rank Nyström Stein approximation with adaptive macro-tier peeling to eliminate batches of candidate sinks simultaneously, drastically reducing both the size and frequency of kernel computations. To combine ordering evidence across scales and inform intra-tier evidence allocation, COSMIC utilizes a Tri-Band Harmonic Stein Ensemble and evaluates leave-one-macro-tier-out parent scores with local coupling confidence. We support this framework by formally showing that terminal-block removals preserve the underlying Additive Noise Model structure. Extensive benchmarking demonstrates that COSMIC scales topological ordering and candidate parent screening to variables in minutes, a regime where existing non-parametric methods stall. In full end-to-end discovery (including non-parametric regression pruning), COSMIC completes graphs through before downstream GAM pruning reaches an empirical timeout at . Across small synthetic and biological benchmarks (–), COSMIC achieves competitive recovery accuracy while evaluating candidate edges orders of magnitude faster than continuous-DAG and non-parametric baselines.

Primary area:
causal reasoning
Keywords:
Causal Discovery, Score Matching, Additive Noise Models, Low-Rank Kernel Methods, High-Dimensional Statistics

Reviews

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

COSMIC accelerates causal ordering and parent screening through Nyström approximation and grouped removal of variables, followed by regression pruning to recover the final graph. The paper presents computational analysis, component ablations, and diagnostics of approximation and ordering errors.

Critical strengths
  1. Nyström approximation and grouped removal address distinct computational costs, and the ablations demonstrate their complementary benefits.
  2. The paper clearly documents the scope of its theoretical results and the limitations introduced by approximation and downstream pruning.
Critical weaknesses
  1. The comparison omits SciNO [1], which directly addresses the same Hessian estimation bottleneck and can replace the estimator used in CaPS. Comparisons with SciNO and representative alternatives such as DrBO [2] and observational SEA [3] are needed to establish COSMIC’s contribution relative to current approaches to efficient causal discovery.
  2. The experiments do not systematically test denser graphs such as SynER5 or vary graph depth and the proportion of linear mechanisms. These conditions are relevant to the reliability and computational benefit of grouped removal, while the existing noise and hyperparameter diagnostics provide limited evidence about complete graph recovery across such changes.
  3. Theorem 5.1 does not establish that the heuristic selects valid terminal blocks or orders connected variables correctly within each block. Moreover, assigning zero scores to relations within a group can exclude true edges during screening when other candidate parents have sufficiently positive scores, creating an accuracy risk that is not adequately characterized across graph structures.
  4. The largest experiments demonstrate scalability of ordering and screening, while GAM pruning restricts complete graph recovery to substantially smaller problems. The paper does not clearly establish the conditions under which the computational savings justify the observed costs in recovery accuracy and provide a compelling overall advantage.
  5. Sachs is the only dataset based on real measurements, while the fMRI benchmark is simulated. This leaves limited evidence that the proposed scaling strategy produces useful causal graphs on larger and more varied real datasets.

Reference

[1] Kang et al., "Score-informed Neural Operator for Enhancing Ordering-based Causal Discovery," NeurIPS, 2025.

[2] Duong et al., "Causal discovery via Bayesian optimization," ICLR, 2025.

[3] Wu et al., "Sample, estimate, aggregate: A recipe for causal discovery foundation models," TMLR, 2025.

Questions for authors
  1. How does COSMIC compare with SciNO and representative recent alternatives under matched observational settings, considering total computation and final graph accuracy, with pretraining costs reported separately where applicable?
  2. How do graph density, depth, and the number of available sinks affect the accuracy and computational benefit of grouped removal?
2 comments
AuthorsOpenReview ↗

Response to Reviewer SCEk

We thank Reviewer SCEk for the constructive review and for highlighting the value of our Nyström and grouped-removal ablations. Because end-to-end pruning scalability and heuristic macro-tier batching were raised across reviews, we address both in the general comment above and focus here on the rest.

1. SciNO, DrBO, and SEA

Matched empirical comparisons with SciNO, DrBO, and observational SEA are not yet available for this response. We are planning five-seed comparisons; here, we clarify two distinctions regarding training paradigms and scaling axes:

  • Estimator & Training Paradigms: COSMIC's Nyström Stein estimator is training-free and closed-form, with O(nm2+m3)\mathcal{O}(nm^2 + m^3) matrix-factorization cost. By contrast, SciNO trains a score-informed neural operator on the dataset and, in its CaPS adaptation, probes it at each leaf-removal step; SEA amortizes inference via cross-dataset pretraining; and DrBO uses Bayesian optimization over score evaluations.
  • Separating NN-, dd-, and Mixed Scaling: Methods such as SciNO and DAGMA also avoid exact Stein estimation's cubic kernel bottleneck in NN. Nyström estimation therefore addresses this bottleneck without establishing a scaling advantage over those alternatives. We plan to evaluate the isolated effects of rising d and N in full pipeline discovery in subsequent versions, while accounting for candidate screening and pruning costs.

2. Graph Density, Depth, Sink Availability, and Co-Batching

We ran a matched study at d=50,N=1,000d=50, N=1{,}000 (3 seeds, 50%50\% nominal linear mechanisms) comparing grouped vs. singleton (50 tiers) COSMIC (speedups are ratios of mean matched times):

  • Density (SynER1/2/5 at d=50d=50): Speedups persist with density, while batch validity and recovery deteriorate:
GraphTtiersT_{\text{tiers}}Order SpeedupE2E SpeedupF1 (Grp / Sing)SHD (Grp / Sing)
SynER112.6712.676.66×6.66\times1.71×1.71\times0.608/0.6870.608 / 0.68734.0/27.334.0 / 27.3
SynER212.0012.007.06×7.06\times1.50×1.50\times0.592/0.6000.592 / 0.60070.7/64.370.7 / 64.3
SynER512.0012.007.27×7.27\times1.53×1.53\times0.413/0.4470.413 / 0.447220.0/221.0220.0 / 221.0

The heuristic does not shrink average batch sizes as density increases: initial true sinks fall from 20.720.7 (SynER1) to 5.05.0 (SynER5), yet tier counts stay near 1212 and valid co-sink batches fall from 66.2%66.2\% to 44.4%44.4\%. Thus, speedups persist despite departures from ideal co-sink batching.

  • Depth (L∈{3,5,10}L \in \{3,5,10\} on controlled d=50d=50 graphs; 27 runs/row across 3 densities ×\times 3 sink counts ×\times 3 seeds):
Depth LLTtiersT_{\text{tiers}}Valid Co-Sink BatchesF1 (Grp / Sing)SHD (Grp / Sing)
3312.5612.5669.9%69.9\%0.613/0.6080.613 / 0.60883.4/92.383.4 / 92.3
5512.4412.4457.4%57.4\%0.544/0.5650.544 / 0.565102.8/104.6102.8 / 104.6
101012.3012.3049.3%49.3\%0.505/0.5280.505 / 0.528114.1/112.9114.1 / 112.9

Deeper configurations show lower recovery for both grouped and singleton COSMIC (grouped F1 is slightly higher at L=3L=3 and lower at L=5,10L=5,10), while co-sink batch validity drops (69.9%→49.3%69.9\%\to49.3\%) and tier counts remain nearly unchanged (12.56→12.3012.56\to12.30).

  • Sink Availability: Increasing initial sinks from 11 to 1313 reduces TtiersT_{\text{tiers}} from 12.7012.70 to 12.0012.00 and raises ordering speedup from 6.36×6.36\times to 7.17×7.17\times, while grouped F1 shifts from 0.5670.567 to 0.5370.537, giving modest speedup without better recovery.

  • Intra-Group Diagnostic & Linearity Scope:

    • Definitions: Against the ground-truth graph at each peeling step, independent batches have no internal true edges, terminal blocks have no outgoing true edges to retained variables, and valid co-sink batches satisfy both. Co-sink rates include singleton and final batches, with per-run rates averaged across seeds.
    • Co-Batching Rates: At d=50d=50, co-batched true-edge fractions are 13.17%13.17\% (SynER1), 8.31%8.31\% (SynER2), and 12.50%12.50\% (SynER5), and rise across depths 3/5/103/5/10 from 9.28%9.28\% to 12.00%12.00\% to 13.50%13.50\%. These quantify exposure to intra-tier zero scoring, rather than measured screening deletions: saved outputs lack screening masks or childwise maxima. This study uses 50%50\% nominal linear mechanisms; a multi-level linearity sweep against CaPS/SCORE remains outstanding.

3. Real-World vs. Semi-Synthetic Benchmarks

Verified ground-truth DAGs for continuous observational data at d≥50d\ge50 are scarce. Contemporary ordering-based methods likewise combine real measurements with synthetic or semi-synthetic benchmarks. We originally attempted to include DREAM5, but end-to-end discovery at that scale proved infeasible under our GAM pruning bottleneck; useful recovery on larger real datasets beyond Sachs therefore remains unverified here.

We thank Reviewer SCEk for the constructive feedback, which helped us quantify the trade-offs of grouped removal and refine our evaluation.

Thank you for the detailed response and clarifications. After carefully reading the rebuttal, my overall assessment remains unchanged, so I will maintain my current score.

Reviewer_Ao6rOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary
  • COSMIC is a causal discovery framework for nonlinear additive noise models (ANMs) designed to address the cubic sample and quadratic dimensional bottlenecks of traditional kernel-based score-matching methods. The main contributions are:
  1. Using m≪nm \ll n landmark points via Farthest Point Sampling (FPS) and a Tri-Band Harmonic Stein Ensemble to lower computational complexity from O(n3)\mathcal{O}(n^3) to O(nm2+m3)\mathcal{O}(nm^2 + m^3).
  2. Removing batches of candidate sinks simultaneously and introducing Leave-One-Macro-Tier-Out (LOMTO) parent scoring with local coupling confidence (LOMTO-LC) to allocate evidence without extra Stein evaluations.
  3. showing that terminal-block removals preserve ANM structure (Theorem 5.1), and demonstrating pre-screening scaling up to d=500d=500 variables and 1,000,0001,000,000 observations.
Critical strengths
  • the authors explicitly detail their pilot certification failures, off-subspace error amplification mechanisms (η−2\eta^{-2} scaling), and the exact pipeline stage where execution stalls.
  • The coupling of Nyström landmark approximations with macro-tier peeling genuinely accelerates intermediate topological ordering and candidate score screening compared to dense baseline competitors.
Critical weaknesses
  • recent literature in continuous DAG learning (e.g., DAGMA, GOLEM) achieves end-to-end structure learning via differentiable optimization, ordering-based methods like SCORE, CaPS, and CAM decouple topological ordering from downstream pruning. COSMIC inherits this architectural split, leading to an extreme scalability wall: while pre-screening scales to d=500+d=500+, the full pipeline breaks down entirely at d=200d=200 due to non-parametric GAM pruning hitting empirical timeouts. Framing the framework as scalable while truncating the pipeline before final graph recovery misrepresents its end-to-end utility relative to continuous alternatives.
  • score-matching causal discovery typically relies on Hessian diagonal curvature to rank sinks. However, this theoretical identification strictly requires equal error variances (σj2≡σ2\sigma_j^2 \equiv \sigma^2). As the authors' controlled experiments demonstrate, severe heteroscedasticity (σi∈[0.2,2.5]\sigma_i \in [0.2, 2.5]) causes recall to collapse (0.1110.111 to 0.1940.194), and standard feature standardization fails to fix it because it rescales marginal variance rather than structural innovation variance. COSMIC does not resolve this well-known limitation of curvature-based score matching.
  • Appendix A.7 reveals that deterministic approximation bounds achieve 0.0% certification coverage across all 120 pilot runs, with theoretical error bounds exceeding measured discrepancies by orders of magnitude. The gap between kernel compression theory and finite-sample greedy combinatorial stability remains unbridged.
  • The adaptive macro-tier peeling relies on arbitrary gap thresholds (e.g., 15%15\% of dynamic range) to bundle variables. In the broader literature of greedy search algorithms (like greedy equivalence search or hierarchical clustering), heuristic batching without structural guarantees risks grouping non-sinks prematurely, violating Theorem 5.1's terminal-block conditions and introducing unobserved confounding.
Questions for authors
  • Given that modern continuous DAG learners (e.g., DAGMA-MLP) and score-based frameworks attempt end-to-end optimization, how can COSMIC justify claiming d=500+d=500+ scalability when its final graph recovery pipeline stalls at d=100d=100 and times out at d=200d=200 due to downstream GAM fitting?
  • Since ANM score-matching criteria are heavily sensitive to unequal error variances, and empirical feature standardization fails to correct innovation scale mismatches, what modifications to the score estimator or ranking criterion would be required to make COSMIC robust to heteroscedastic real-world data?
1 comment
AuthorsOpenReview ↗

Response to Reviewer Ao6r

We thank Reviewer Ao6r for the thoughtful review and for highlighting our transparency regarding pilot certification bounds and off-subspace η−2\eta^{-2} error amplification. Because end-to-end scalability and macro-tier batching were raised across the reviews, we address both in the general comment above and focus here on Question 2 and Weaknesses 2–3.

1. Modifying COSMIC for Robustness to Heteroscedastic Error Variances

Your diagnosis of why feature standardization fails under heteroscedastic noise (σi∈[0.2,2.5]\sigma_i \in [0.2, 2.5]) is exact: marginal standardization rescales Var⁡(Xj)=Signalj+σj2\operatorname{Var}(X_j) = \mathrm{Signal}_j + \sigma_j^2, altering score scales without equalizing conditional innovation variances σj2\sigma_j^2.

  • Why Mean-Hessian Fails: The equal-variance requirement applies to CaPS's mean-curvature criterion E[Hjj(X)]=−σj−2−∑c∈ch(j)σc−2E[(∂jfc)2]\mathbb{E}[H_{jj}(X)] = -\sigma_j^{-2} - \sum_{c \in \mathrm{ch}(j)} \sigma_c^{-2} \mathbb{E}[(\partial_j f_c)^2] rather than score matching generally. Under unequal node-specific noise variances, the offset −σj−2-\sigma_j^{-2} varies across nodes, allowing an upstream node with large σj2\sigma_j^2 to appear less negative than a sink with small σl2\sigma_l^2.
  • Swapping Mean-Hessian for Variance-Hessian on the Same Nyström Solver: Reusing the same Nyström Tri-Band Stein solver, we replace the column-mean aggregation on H^tri∈Rn×d\widehat{H}^{\mathrm{tri}} \in \mathbb{R}^{n \times d} with its column variance:
    1. Population Sink Identification (SCORE / DAS Criterion): Under independent Gaussian errors with constant, node-specific variances σl2>0\sigma_l^2 > 0, any sink ll has constant curvature Hll(X)≡−σl−2H_{ll}(X) \equiv -\sigma_l^{-2}, so Var⁡(Hll(X))=0\operatorname{Var}(H_{ll}(X)) = 0 regardless of σl2\sigma_l^2 (Rolland et al., 2022; Montagna et al., 2023). Ranking sinks by arg⁡min⁡jVar⁡^i(H^ijtri)\arg\min_j \widehat{\operatorname{Var}}_i(\widehat{H}_{ij}^{\mathrm{tri}}) removes the −σj−2-\sigma_j^{-2} offset.
    2. Scope & Trade-Off: Switching from E[Hjj]\mathbb{E}[H_{jj}] to Var⁡[Hjj]\operatorname{Var}[H_{jj}] trades linear-mechanism identifiability for robustness to unequal node-specific error variances: under twice-differentiable mechanisms nonlinear in each parent, Var⁡(Hjj(X))=0\operatorname{Var}(H_{jj}(X)) = 0 uniquely identifies sinks in population, whereas on linear mechanisms Var⁡(Hjj)≡0\operatorname{Var}(H_{jj}) \equiv 0 for all nodes. This population result does not cover parent-dependent noise scales or automatically establish finite-sample Nyström accuracy, which requires empirical evaluation and variance-specific bounds.

2. Why Appendix A.7 Certification Is 0.0% and Routes Toward Sharper Guarantees

In Appendix A.7, deterministic certification is 0.0%0.0\% across our pilot runs because Proposition A.3 requires the raw L∞L_\infty curvature discrepancy e=∥h~−hˉ∥∞e = \|\tilde{h} - \bar{h}\|_\infty to simultaneously clear all four adaptive batch-selection and node-separation margins. In the pilot, initial boundary gaps are <1< 1, whereas measured discrepancies (3.77×102–7.08×1053.77 \times 10^2\text{--}7.08 \times 10^5) and worst-case spectral bounds (1.04×1013–2.32×10191.04 \times 10^{13}\text{--}2.32 \times 10^{19}) are orders of magnitude larger, even though initial tier sets still match the dense reference in 18/12018/120 runs. Our diagnostics point to three promising routes for narrowing this gap:

  1. Subspace Projection: In the unprojected Woodbury solve, off-subspace quadrature terms in null⁡(C⊤)\operatorname{null}(C^\top) are amplified by η−1\eta^{-1} in the score and η−2\eta^{-2} when squared in the Hessian. In Appendix A.6, thin-SVD projection onto col⁡(Knm)\operatorname{col}(K_{nm}) reduced normalized derivative errors by 4–6 orders of magnitude, though it did not reduce edge-order violations on the chain benchmark and was not adopted in production.
  2. Affine-Aligned Perturbation Analysis: Because argmax is invariant to positive rescaling and shifts (h↦ah+b,a>0h \mapsto a h + b, a > 0), raw ∥h~−hˉ∥∞\|\tilde{h} - \bar{h}\|_\infty penalizes shared scale inflation even when relative rankings are partially preserved. Formulating stability via affine-aligned discrepancies (modulo the range guard) is a natural theoretical direction, though finite-sample certification and extension to variance ranking remain open.
  3. Single-Sink Margin Conditions via k=dk=d: Stepping back from adaptive batching to singleton peeling (b∗=1b^* = 1) removes the competing-gap and relative-range cutoff conditions from Proposition A.3, reducing step-wise reference agreement to the single top-sink gap Δˉ1>2e\bar{\Delta}_1 > 2e.

We would once again like to thank Reviewer Ao6r for the constructive feedback and incisive questions, which directly helped us clarify the theoretical scope of our certification bounds and motivate the redesign of our ranking criterion.

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

COSMIC accelerates score-based causal discovery through Nyström kernel approximation, tri-band estimation, batched variable removal, and grouped parent scoring, followed by GAM pruning. The paper provides conditional guarantees for terminal-block removal and evaluates recovery accuracy, runtime, and component contributions on synthetic data, Sachs, and simulated fMRI. The results demonstrate substantial front end acceleration, alongside accuracy losses and a persistent end-to-end pruning bottleneck.

Critical strengths
  1. Substantial acceleration of ordering and candidate screening. COSMIC achieves significant front end process acceleration over CaPS at 100 variables and processes substantially larger datasets. This is a useful computational contribution to stages that are expensive in existing kernel-based methods.
  2. Extensive component-level evaluation. The paper includes ablations of kernel approximation, grouped omission, and bandwidth choices, together with stage-specific timing and approximation diagnostics. These analyses help identify which components reduce computation and where accuracy and scalability limitations arise.
Critical weaknesses
  1. The theoretical guarantee does not cover the implemented batch-selection rule. Theorem 5.1 assumes that the removed variables form a terminal block, but COSMIC’s mean-curvature gap heuristic does not guarantee this condition. Consequently, the theorem does not establish correctness of the proposed ordering procedure, and the paper does not resolve it. Since batch removal is a central contribution, this substantially weakens the method’s theoretical justification.
  2. The front end speedup does not yield a convincing end-to-end advantage. In the full pipeline, COSMIC takes around 1,537 seconds with F1 0.404 at 100 variables, whereas SCORE takes about 137 seconds with F1 0.484: COSMIC is over ten times slower and less accurate. Relative to CaPS, end-to-end speedups at 10–50 variables are approximately 2–3 times, with absolute F1 losses of 0.12–0.18. These results weaken the practical contribution to scalable graph recovery, despite substantial acceleration of intermediate computations.
Questions for authors

Consider the linear Gaussian chain A→B→C→D→EA\to B\to C\to D\to E, with respective edge coefficients (0.1,2,2,2)(0.1,2,2,2) and mutually independent standard Gaussian noises. Assuming access to exact population mean diagonal Hessians at every step, could the authors work through the default adaptive batch-selection rule and verify whether the first selected batch is a terminal block and the resulting ordering is valid? Please use the implemented gap threshold, batch-size cap, and fallback rule. This would clarify whether removing estimation error suffices for correct ordering, or whether additional structural conditions are needed beyond those stated in Theorem 5.1.

1 comment
AuthorsOpenReview ↗

Response to Reviewer zWUF: 5-Node Chain Analysis

We thank Reviewer zWUF for the review and the five-node example. We agree that it exposes a population-level failure of our implemented adaptive batching rule. For brevity, we will address the second weakness in a general comment since the end-to-end discrepancy has been raised by all reviewers.

For A→0.1B→2C→2D→2EA\xrightarrow{0.1}B\xrightarrow{2}C\xrightarrow{2}D\xrightarrow{2}E with mutually independent unit Gaussian noises, log⁡p(a,b,c,d,e)=−12[a2+(b−0.1a)2+(c−2b)2+(d−2c)2+(e−2d)2]+const.\log p(a,b,c,d,e)=-\tfrac12\left[a^2+(b-0.1a)^2+(c-2b)^2+(d-2c)^2+(e-2d)^2\right]+\mathrm{const}. Consequently, the population diagonal Hessian is constant and, in (A,B,C,D,E)(A,B,C,D,E) order, equals Hˉ=(−1.01,−5,−5,−5,−1).\bar H=(-1.01,-5,-5,-5,-1).

Implemented first selection. The code sorts scores increasingly and searches for the largest adjacent gap in the upper half. For five nodes, an ascending order is (B,C,D,A,E)(B,C,D,A,E), with scores (−5,−5,−5,−1.01,−1)(-5,-5,-5,-1.01,-1) and gaps (0,0,3.99,0.01)(0,0,3.99,0.01). It considers zero-based gap indices 2,32,3, so the maximum eligible gap is 3.993.99. The range is 4>10−64>10^{-6}, and 3.99/4=0.9975≥0.153.99/4=0.9975\ge0.15. The resulting candidate batch size is two, which equals the cap ⌈0.4⋅5⌉=2\lceil0.4\cdot5\rceil=2. The fallback ⌈5/4⌉=2\lceil5/4\rceil=2 is not invoked. Thus the first batch is S1={E,A}S_1=\{E,A\}, appended in removal order (E,A)(E,A).

This batch is not terminal: A→BA\to B points from S1={E,A}S_1=\{E,A\} into the retained set {B,C,D}\{B,C,D\}, violating Theorem 5.1's premise. Recomputing the marginal diagonal Hessians on the remaining nodes peels DD, then CC, then BB, yielding the removal sequence (E,A,D,C,B)(E,A,D,C,B) and final topological order π^=(B,C,D,A,E),\widehat\pi=(B,C,D,A,E), which inverts A→BA\to B and places AA after three of its descendants. Since there is no way to fix an ordering mistake, this remains a huge issue for the causal discovery algorithm.

What is needed to solve this? For Gaussian ANMs with integrable derivatives, Hˉj=−σj−2−Dj\bar H_j=-\sigma_j^{-2}-D_j where Dj=∑c∈ch(j)σc−2E[(∂jfc)2]D_j=\sum_{c\in\mathrm{ch}(j)}\sigma_c^{-2}\mathbb E[(\partial_jf_c)^2]. Under equal noise variances, preventing the adaptive gap rule from co-batching a non-sink with sinks requires the sink–non-sink boundary gap (Dmin⁡D_{\min}) to be the largest eligible gap in the upper half of sorted curvatures and to clear the 15%15\% range threshold (Dmin⁡≥0.15Dmax⁡D_{\min} \ge 0.15 D_{\max})—or, more strongly, strict edgewise score separation Hˉj>Hˉi\bar H_j > \bar H_i along every active edge i→ji \to j at every stage. Because Theorem 5.1 does not guarantee these gap conditions when mechanism strengths vary widely across the graph, we address this directly via a two-part design that decouples our low-rank Nyström Stein estimator from heuristic batching:

  1. Resolving batch-induced failures via sequential 1-by-1 Nyström peeling (k=dk=d): Setting k=dk=d (bt≡1b_t \equiv 1) removes (E,D,C,B,A)(E,D,C,B,A) one node at a time and recovers the exact order (A,B,C,D,E)(A,B,C,D,E) in the population limit whenever non-sinks have positive child derivative energy under equal noise variances (requiring finite-sample estimation error below half the minimum sink–non-sink margin, here 0.0050.005). Each pass retains the O(nm2+m3)\mathcal O(nm^2+m^3) Nyström matrix-factorization speedup over O(n3)\mathcal O(n^3) dense kernel solves.
  2. Resolving unequal error variances via Variance-Hessian (Var⁡[Hjj]\operatorname{Var}[H_{jj}]): When the concern is heteroscedastic noise (σj2≠σk2\sigma_j^2 \neq \sigma_k^2), we aggregate the same Nyström diagonal Hessian matrix H^tri∈Rn×d\widehat{H}^{\mathrm{tri}} \in \mathbb{R}^{n \times d} by its column variance Var⁡n(H^⋅,jtri)\operatorname{Var}_n(\widehat{H}_{\cdot, j}^{\mathrm{tri}}) instead of its column mean, following SCORE (Rolland et al., 2022) and DAS (Montagna et al., 2023). Because Hjj(X)≡−σj−2H_{jj}(X) \equiv -\sigma_j^{-2} is constant for any Gaussian-ANM sink, Var⁡(Hjj(X))=0\operatorname{Var}(H_{jj}(X)) = 0 for every σj2>0\sigma_j^2 > 0. This gives COSMIC two complementary operating modes on the same Nyström solver: Mean-Hessian (E[Hjj]\mathbb{E}[H_{jj}]) for linear/mixed mechanisms under homoscedastic noise, and Variance-Hessian (Var⁡[Hjj]\operatorname{Var}[H_{jj}]) for heteroscedastic noise under nonlinear mechanisms (at the expense of linear mechanisms, where Var⁡[Hjj]≡0\operatorname{Var}[H_{jj}] \equiv 0).

We would once again like to thank Reviewer zWUF for the constructive feedback and the insightful counterexample, which directly helped us sharpen both the theoretical scope and the algorithmic design of our framework.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to the Reviewers

We thank the Area Chair and reviewers for their careful assessment and constructive feedback. The reviews identify two shared concerns: whether the front-end computational gains translate into efficient complete graph recovery, and whether heuristic macro-tier selection satisfies the structural conditions of our theorem. Below, we address these concerns and outline the changes they have motivated.

1. Front-End Speedup vs. End-to-End Runtime and Accuracy

We agree with the reviewers that the reported end-to-end comparison at d=100,n=1000d=100, n=1000 does not show an end-to-end runtime advantage over SCORE or continuous DAG learners: across the 10 matched runs in Section 6.4 (Figure 4), COSMIC averages 1537.69s1537.69\text{s} (F1=0.4041\text{F1} = 0.4041) versus SCORE's 137.26s137.26\text{s} (F1=0.4841\text{F1} = 0.4841), and non-parametric/continuous methods time out at d=200d=200 (1800s1800\text{s} limit).

Stage-wise instrumentation of those same 10 runs shows that COSMIC's Nyström ordering (0.76s0.76\text{s}), LOMTO-LC parent scoring (2.09s2.09\text{s}), and screening (0.001s0.001\text{s}) total only 2.85s2.85\text{s}, whereas serial R mgcv::gam spline pruning consumes 1534.83s1534.83\text{s} (99.8%99.8\% of total wall-clock time). We originally retained the R GCV pruner to maintain a controlled comparison with CaPS, but we recognize that accelerating Phases 1–2 alone does not resolve high-dimensional end-to-end scaling without bounding candidate parent sets or replacing serial GAM pruning.

2. Heuristic Macro-Tier Gap Thresholds vs. Nyström-Accelerated Sequential Peeling (k=dk=d)

We also agree that fixed relative-gap thresholds (15% of dynamic range) cannot guarantee terminal-block validity when mechanism derivative energies vary widely across the graph. While combining macro-tier batching (LOMTO) with Nyström landmarks reduces single-band ordering and parent-scoring time at d=100,n=1000d=100, n=1000 from 5.82s5.82\text{s} to 2.13s2.13\text{s} (2.73×2.73\times), our factorial ablation in Section 6.5 (Figure 5) shows that Nyström landmarks alone already deliver a 7.9×7.9\times speedup over exact variable-wise peeling, reducing single-band ordering and LOO scoring time from 45.95s45.95\text{s} (Exact LOO) to 5.82s5.82\text{s} (Nyström LOO) by replacing O(n3)\mathcal{O}(n^3) dense solves with O(nm2+m3)\mathcal{O}(nm^2 + m^3) low-rank matrix factorizations. Stepping back to k=dk=d sequential peeling therefore retains the primary Nyström sample-size acceleration while eliminating batch-induced nonterminality and intra-tier zero-masking (with valid sink selection then governed by single-node ranking margins at each step).

3. Planned Screening, Pruning, and Ordering Redesign

Our next iteration targets complete graph recovery, with coordinated changes across the pipeline:

  • Screening: We plan to evaluate bounded candidate parent sets and individual-edge scoring, including low-rank derivative-based screening, to reduce the regression workload while measuring the true-parent recall lost at screening. Candidate caps will be evaluated as an accuracy–runtime trade-off rather than assumed to preserve all true parents.
  • Pruning: We are testing alternative regression-based pruners to replace the serial GAM bottleneck, including spline-based model selection, alongside opportunities to reuse basis computations and parallelize independent nodewise fits. Earlier B-spline/BIC and parallel-GAM trials did not meet our acceptance criteria, so these remain development directions rather than established improvements.
  • Replacing Macro-Tier Peeling: We plan to replace heuristic macro-tier peeling with new ordering and screening procedures built on the Nyström estimator, using sequential peeling as the reference. The aim is to reduce redundant estimation and regression work while retaining individual-variable ordering and edge evidence, without relying on unverified batches or assigning zero scores solely because variables were co-batched.

The reviewers' feedback has clarified the changes needed to turn our estimator-level speedups into reliable end-to-end causal discovery. We intend to withdraw this submission from ICLR 2027 after the discussion period passes and develop a substantially revised method, evaluating its runtime and final-graph accuracy under matched settings and tracing errors to their originating stages. We will keep the submission open for discussion before withdrawal and welcome further feedback. We thank the Area Chair and reviewers for helping shape this direction.

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

Related papers

Discussion (0)

Sign in to comment.