acceptodds
Under review as a conference paper at ICLR 2027

Local Fisher Information Enables Sparse Causal Discovery

Abstract

Sparse causal discovery calls for methods that exploit graph structure without estimating high-dimensional densities. We introduce Fisher Information Completion Search (FiCS), a source-first algorithm for additive noise models that uses one local Fisher score for both ordering and parent selection. Under regularity and nonconstant-parent conditions, we prove that a node's local Fisher information equals the noise Fisher information exactly when the conditioning set contains all parents, provided that it contains no descendants. This Fisher parent completion identifies the parent set as the unique minimal Fisher completion. With a maximum conditioning set size at least the maximum indegree , population FiCS queries marginals of at most variables and recovers the true directed acyclic graph under a positive ordering margin. Bounded conditioning also has a population advantage: reducing toward cannot decrease, and can strictly increase, the ordering margin. A growing non-Gaussian family separates local Fisher selection from conditional-variance and leaf-first Fisher ordering. For the regularized kernel Stein estimator, we establish high-dimensional DAG consistency under , uniform Fisher separation, local approximation, and compatible ridge and parent penalty parameters. Experiments show the strongest gains when is small relative to , quantify the effect of the conditioning size, and demonstrate competitive reference-graph recovery on three real-data benchmarks.

Primary area:
causal reasoning
Keywords:
Causal Discovery, Additive Noise Models, Fisher Information, Causal Identifiability, Sparse Graphical Models

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_EHghOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Fisher Information Completion Search. The key idea is to use local Fisher information to identify parent sets and recover causal orderings without esimating high-dimensional densities. The authors establish theoretical guarantees for DAG recovery. Experiments on sythetic and real-world datasets demonstrate competitive performance.

Critical strengths

The paper introduces an interesting Fisher-information-based framework for sparse causal discovery, with theoretical recovery guarantees. The use of low-dimensional local information is particularly appealing for high-dimensional settings.

Critical weaknesses

Although FiCS demonstrates impressive performance in high-dimensional setting, the experimetns rely heavily on highly sparse DAGs with small maximus indegrees. Its nearly identical F1 scores accross different dimensions, together with its sensitivity to nonlinear mechanisms, raise concerns about whether the reported advantages generalize to more complex and realistic causal structures.

Questions for authors
  1. In Figure2, FiCS achieves remarkably similar F1 scores for p=50,100,200, even when p>n, while competing methods deteriorate substantially. Could the authors explain this phenomenon and provide addtional evidence supporting such dimensional robustness?
  2. The synthetic experimetns restrict the maximum indegree to two, matching the conditioning size q=2. How does FiCS perform on more complex DAGs with larger maximum indegrees?
  3. Appendix G.2 shows that FiCS peforms substantially better on linear mechanisms than on fully nonlinear causall discovery. Could the authors clarify the source of this sensitivity and its implications for nonlinear causal discovery?
4 comments
AuthorsOpenReview ↗

Response to Reviewer EHgh [1/2]

We appreciate the reviewer's questions on how FiCS behaves in more complex settings. They helped us test FiCS in higher dimensions and on graphs with maximum indegree four, and the question on fully nonlinear mechanisms led us to relate the lower accuracy on such data to a smaller ordering margin.

Weakness 1. Sensitivity to graph density and dimension

Although FiCS demonstrates impressive performance in high-dimensional setting, the experimetns rely heavily on highly sparse DAGs with small maximus indegrees. Its nearly identical F1 scores accross different dimensions, together with its sensitivity to nonlinear mechanisms, raise concerns about whether the reported advantages generalize to more complex and realistic causal structures.

We thank the reviewer for recognizing the performance of FiCS in high-dimensional settings. We tested FiCS on denser ER5 and scale-free graphs with maximum indegree four at p=50p=50.

With the matching cap q=4q=4, FiCS led the four baselines on both F1 and SHD in seven of eight settings. The full comparison appears in our answer to Q2 and in Table 7 (Appendix G.1 of the revised manuscript).

Theorem 2 in Section 3.2 requires the cap qq to be at least the maximum indegree for both graph families. At maximum indegree two, its mean F1 is similar on ER3 and scale-free graphs (.784.784 and .782.782 in Figure 4, Appendix G.1).

We explain the similar F1 across dimensions in our answer to Q1 and the sensitivity to nonlinear mechanisms in our answer to Q3.

Question 1. Accuracy as pp grows

In Figure2, FiCS achieves remarkably similar F1 scores for p=50,100,200p=50,100,200, even when p>np>n, while competing methods deteriorate substantially. Could the authors explain this phenomenon and provide addtional evidence supporting such dimensional robustness?

We appreciate that the reviewer noticed FiCS keeping its F1 even when p>np>n, which is the main benefit of its local scores. The reason is that each local score of FiCS uses at most q+1q+1 variables regardless of pp. More specifically, the score error in Theorem 4 (Section 5.2 of the revised manuscript) depends on the number of local queries only through L=q{log⁡(ep/q)}+log⁡pL=q\{\log(\mathrm ep/q)\}+\log p, which grows with the fixed cap qq but only logarithmically in pp. SCORE and NoGAM instead estimate density derivatives jointly over all pp variables, and at p=200p=200 and n=100n=100 they attain mean F1 of .055.055 and .066.066, against .574.574 for FiCS (Figure 2 in Section 6.1).

Appendix F.4 reports two additional experiments that support this explanation. At n=100n=100, the mean F1 of FiCS decreases only slowly as pp grows to 10001000.

pp502005001000
FiCS F1.640.574.515.483

Changing only the conditioning size for ordering from two to all predecessors lowers mean F1 at every pp from 50 to 200, as shown in Figure 3 (Section 6.2). The loss grows with pp because conditioning on all predecessors estimates each score over more variables, and at p=200p=200 it lowered F1 on every one of the 30 graphs.

ppConditioning size twoAll predecessors
50.640.616
100.605.570
150.580.518
200.574.450
AuthorsOpenReview ↗

Response to Reviewer EHgh [2/2]

Question 2. Graphs with larger maximum indegree

The synthetic experimetns restrict the maximum indegree to two, matching the conditioning size q=2q=2. How does FiCS perform on more complex DAGs with larger maximum indegrees?

We thank the reviewer for this important question, which motivated us to test FiCS on graphs with maximum indegree four at p=50p=50. Increasing the maximum indegree makes FiCS statistically and computationally more demanding because the conditioning limit qq must be large enough to accommodate the true parent sets. Nevertheless, the effect was not prohibitive in the tested extension from maximum indegree two to four.

We conducted the experiment reported in Table 7 (Appendix G.1 of the revised manuscript) on ER graphs with an expected mean total degree of five (ER5) and scale-free (SF) graphs, both having a maximum indegree of up to four. FiCS with q=4q=4 improved both F1 and SHD over q=2q=2 in every setting and achieved the best results on both metrics among the baselines in seven of eight settings. These results extend the empirical support for FiCS to DAGs with greater maximum indegree and highlight the benefit of increasing qq to accommodate larger parent sets.

GraphnnFiCS q=2q=2 (F1 / SHD)FiCS q=3q=3 (F1 / SHD)FiCS q=4q=4 (F1 / SHD)Best baseline F1Best baseline SHD
ER550.303 / 106.50.407 / 102.61.460 / 100.64.230 (NoGAM)151.29 (NoGAM)
Scale-free50.289 / 109.17.395 / 105.21.449 / 105.21.200 (NoGAM)176.69 (NoGAM)
ER5100.443 / 84.07.558 / 74.17.617 / 68.43.459 (CaPS)87.83 (NoGAM)
Scale-free100.434 / 86.13.566 / 74.20.619 / 69.70.438 (CaPS)86.80 (NoGAM)
ER5200.524 / 71.83.638 / 59.23.686 / 53.43.646 (CaPS)58.37 (SCORE)
Scale-free200.531 / 70.90.645 / 58.80.695 / 52.57.644 (SCORE)58.43 (SCORE)
ER5500.575 / 64.93.672 / 53.37.722 / 46.90.746 (CaPS)45.60 (CaPS)
Scale-free500.576 / 64.90.687 / 51.63.744 / 43.70.732 (CaPS)48.23 (SCORE)

At n=50n=50, all methods are compared on the 28 ER5 and 29 SF inputs for which CaPS returned a DAG. Each other row uses all 30 inputs.

Question 3. Linear versus fully nonlinear mechanisms

Appendix G.2 shows that FiCS peforms substantially better on linear mechanisms than on fully nonlinear causall discovery. Could the authors clarify the source of this sensitivity and its implications for nonlinear causal discovery?

Thank you for asking about this sensitivity. On the graphs from the mechanism-proportion experiment (Figure 5 in Appendix G.2 of the revised manuscript), all-GP mechanisms have a smaller first-step population Fisher gap and lower ordering accuracy than all-linear mechanisms. Giving FiCS a true topological order raises all-GP F1 from .608.608 to .678.678. All-linear F1 with the true order is .938.938, so a difference remains at the parent-selection stage.

On each of the same 30 DAGs, we rescaled the linear coefficients to match the GP model's first-step population Fisher gap, the score difference between the best source and the best nonsource. We computed the linear gaps from the model covariances and estimated the GP gaps numerically. The mean gap was about .0588.0588 in both settings. With the true order supplied, the rescaled linear and all-GP mechanisms had similar F1 (.665.665 and .678.678). Their estimated-order F1 and ordering accuracy still differed. Rescaling also changes the parent scores. Theorem 3 (Section 5.1) applies to nonlinear mechanisms and relates recovery to the ordering and parent-omission margins, score estimation error, and the parent penalty.

MechanismFirst-step population Fisher gapAtopA_{\mathrm{top}}Estimated order F1True order F1
All linear.2374.995.940.938
Rescaled all linear.0588.777.535.665
All GP.0588.862.608.678

Means over the same 30 DAGs (p=50,n=200,q=2p=50,n=200,q=2). AtopA_{\mathrm{top}} uses the estimated order.

Thanks for authors' detailed responses, which have addressed most of my concerns. Although some limitations remain, I will raise my score to 3.

We sincerely thank the reviewer for the careful reading of our responses and for raising the score. The reviewer's questions led us to evaluate FiCS in more complex settings, which strengthened the empirical support of the manuscript.

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

This paper proposes FiCS for sparse causal discovery in additive noise models. The main result shows that when the conditioning set contains no descendants, a node’s local Fisher information equals its noise Fisher information if and only if all parents are included. FiCS uses this principle for source-first ordering and parent selection.

The paper establishes population recovery under an ordering-margin condition and derives finite-sample error bounds and high-dimensional consistency. It also shows that bounded conditioning can improve the population ordering margin. Experiments on synthetic and real datasets demonstrate promising results.

Critical strengths

The Fisher parent completion result provides a common statistical basis for both stages of the algorithm. It applies to nonlinear structural functions, including interactions among parents, and permits non-Gaussian noise under the stated conditions. This is a meaningful extension of local conditional-variance approaches.

Critical weaknesses

1 The experiments omit the most direct comparison needed to establish the benefit of the Fisher criterion. In the Gaussian setting, FiCS ordering reduces to bounded-subset conditional-variance ordering. However, the main experiments do not include LearnDAG or a conditional-variance method with a matched conditioning-size bound. LearnDAG already combines local subset search with ordering and parent recovery.

2 There is a gap between the theoretical guarantees and the experimental implementation. The main estimation theorem assumes deterministic kernels and specific conditions on the regularization parameters. The experiments use an empirical median bandwidth and a ridge-selection rule that are not directly covered by this analysis. The Gaussian sample-complexity result also uses a covariance plug-in estimator rather than the kernel Stein estimator used in the experiments.

Questions for authors

1 How does FiCS compare with LearnDAG on linear Gaussian data and with a conditional-variance method using the same conditioning-size bound on mixed-mechanism data? Comparisons of graph accuracy and runtime would affect my evaluation of the empirical contribution.

2 In the equal-variance linear Gaussian setting, how does the sample-complexity bound in Corollary 3 compare with existing guarantees under comparable assumptions? Please make the dependence on maximum indegree, signal strength, and covariance spectral bounds explicit, including the dependence hidden in the recovery tolerance ϵalg\epsilon_{\mathrm{alg}}. If the bound is weaker, does this reflect a limitation of the analysis or of the parent-selection rule? Please also clarify whether the comparison applies only to the Gaussian plug-in estimator or extends to the kernel Stein estimator used in the experiments.

6 comments
AuthorsOpenReview ↗

Response to Reviewer EvBv [1/4]

We appreciate the reviewer's questions on conditional-variance methods and on the gap between the analysis and the implementation. In response, we compared FiCS with LearnDAG and local conditional variance and stated its Gaussian sample complexity against existing guarantees. The question on the bandwidth and ridge rule also led us to revise Theorem 4 (Section 5.2 of the revised manuscript) so that it covers a ridge given explicitly in terms of nn and pp, and to rerun the experiments with it.

Weakness 1 and Question 1. Comparison with LearnDAG and conditional variance

Weakness 1. The experiments omit the most direct comparison needed to establish the benefit of the Fisher criterion. In the Gaussian setting, FiCS ordering reduces to bounded-subset conditional-variance ordering. However, the main experiments do not include LearnDAG or a conditional-variance method with a matched conditioning-size bound. LearnDAG already combines local subset search with ordering and parent recovery.

Question 1. How does FiCS compare with LearnDAG on linear Gaussian data and with a conditional-variance method using the same conditioning-size bound on mixed-mechanism data? Comparisons of graph accuracy and runtime would affect my evaluation of the empirical contribution.

Thank you for pointing out the need for a direct comparison. Section 2 (Related Work) of the submitted manuscript discussed the connection to LearnDAG through bounded-subset conditional-variance ordering for jointly Gaussian variables. We now compare FiCS with LearnDAG and a matched covariance control. The control scores each candidate using the negative inverse of the ordinary least-squares (OLS) residual variance and uses the same search, cap q=2q=2, and parent penalty as FiCS (Appendix C of the revised manuscript). FiCS is comparable to LearnDAG at small nn and more accurate as nn grows, with more computation time. Against local conditional variance, FiCS becomes more accurate on mixed data as nn grows, which shows the advantage of the Fisher score.

(i) FiCS versus LearnDAG on linear Gaussian data. At p=50p=50, FiCS and LearnDAG are comparable at n=50,100n=50,100, and FiCS is more accurate from n=200n=200 on, at a higher computational cost. Local conditional variance is the most accurate and the fastest, because on linear data with Gaussian errors the two scores target the same population quantity, which a linear model can estimate with fewer observations. We use the authors' R implementation of LearnDAG (Gao et al., 2022) with q=2q=2 in both stages. Its parent-selection routine uses BIC. Algorithm 1 in Gao et al. (2022) describes backward pruning with a threshold.

nnFiCSLocal conditional varianceLearnDAG
50.656 / 40.77 / 1.97.870 / 13.00 / 0.0454.665 / 38.63 / 0.27
100.849 / 18.60 / 3.32.974 / 2.33 / 0.0453.842 / 18.23 / 0.30
200.940 / 6.63 / 9.21.996 / 0.33 / 0.0443.911 / 10.37 / 0.37
500.999 / 0.07 / 61.531.000 / 0.00 / 0.0475.950 / 5.77 / 0.59
10001.000 / 0.00 / 313.091.000 / 0.00 / 0.0452.965 / 4.00 / 1.19

(ii) FiCS versus local conditional variance on mixed data. At p=50p=50, local conditional variance is more accurate only at n=50,100n=50,100, because its linear model needs fewer observations, and FiCS is more accurate from n=200n=200 on. With q=2q=2 fixed for both methods, this comparison isolates the Fisher score, and a local linear fit can miss part of a nonlinear parent's effect. LearnDAG is also less accurate than FiCS from n=100n=100 on.

nnFiCSLocal conditional varianceLearnDAG
50.425 / 61.60 / 1.97.569 / 36.10 / 0.0456.426 / 67.47 / 0.28
100.640 / 36.33 / 3.31.661 / 27.77 / 0.0453.571 / 48.00 / 0.31
200.784 / 20.13 / 9.18.715 / 23.90 / 0.0441.669 / 35.07 / 0.38
500.895 / 9.77 / 57.21.743 / 22.00 / 0.0473.776 / 23.13 / 0.60
1000.924 / 7.03 / 309.61.764 / 20.53 / 0.0450.801 / 19.87 / 0.87

Each entry gives F1 / SHD / fit CPU time (s), and Table 4 in Appendix F.3 of the revised manuscript gives the all-GP results as well. Figure 2 (Section 6.1) also compares FiCS with local conditional variance on mixed-mechanism data at p=100p=100 and p=200p=200.

AuthorsOpenReview ↗

Response to Reviewer EvBv [2/4]

Weakness 2-1. Bandwidth and ridge rule in the experiments

There is a gap between the theoretical guarantees and the experimental implementation. The main estimation theorem assumes deterministic kernels and specific conditions on the regularization parameters.

The experiments use an empirical median bandwidth and a ridge-selection rule that are not directly covered by this analysis.

We appreciate this point, which led us to revise Theorem 4 (Section 5.2 of the revised manuscript) so that it covers deterministic kernels with a ridge given explicitly in terms of nn and pp, and we reran the experiments in Figure 2 (Section 6.1) with this choice. The submitted experiments instead used an empirical median bandwidth, as in SCORE (Rolland et al., 2022) and CaPS (Xu et al., 2024), and a ridge-selection rule scaled to each kernel matrix, so both depended on the observations used to fit each local score. With the revised configuration, F1 at p=50p=50 is higher at all five sample sizes, and SHD is lower from n=200n=200 on.

nnSubmitted configurationRevised configuration
50.350 / 43.40.425 / 61.60
100.633 / 28.97.640 / 36.33
200.736 / 22.43.784 / 20.13
500.851 / 13.57.895 / 9.77
1000.918 / 7.67.924 / 7.03

Mean F1 / SHD on the same 30 mixed-mechanism inputs per row (p=50p=50, q=2q=2).

The revised configuration fixes the bandwidths and kernel amplitudes by marginal size and uses the ridge nρn\rho with ρ=.005(L/n)1/4\rho=.005(L/n)^{1/4} and L=qlog⁡(ep/q)+log⁡pL=q\log(\mathrm e p/q)+\log p, both chosen on calibration DAGs separate from the test data (Appendices E.1 and E.3). The parent penalty also changed, from the square-root rule to a calibrated logarithmic rule, so the accuracy change reflects the whole configuration.

Weakness 2-2. Covariance plug-in versus kernel Stein estimator

The Gaussian sample-complexity result also uses a covariance plug-in estimator rather than the kernel Stein estimator used in the experiments.

Your observation was helpful to clarify the purpose and scope of the Gaussian comparison. Corollary 3 and Table 2 in Appendix C of the revised manuscript use a covariance plug-in estimator to compare sample complexity with existing linear Gaussian SEM algorithms. In this setting, the local Fisher score is Ji(T)=−1/Var⁡(Xi∣XT)J_i(T)=-1/\operatorname{Var}(X_i\mid X_T), so covariance estimation provides a direct parametric estimator of the same FiCS population criterion.

We separately analyze the kernel Stein estimator in Appendix D.5, including a recovery bound for the fourth-root ridge and logarithmic penalty used in Figure 2 (Section 6.1). This analysis assumes unit error variance, fixed qq, fixed Gaussian kernels, and local covariance eigenvalues bounded above and away from zero.

AuthorsOpenReview ↗

Response to Reviewer EvBv [3/4]

Question 2. Sample complexity against existing guarantees

We thank the reviewer for providing extra insight into our sample complexity and motivating us to reanalyze the submitted bound and separate the contributions of graph complexity, signal strength, and tuning more explicitly. This refinement enabled a direct comparison with existing algorithms and clarified how the covariance plug-in and kernel Stein estimators differ in sample complexity.

Question 2-1.

In the equal-variance linear Gaussian setting, how does the sample-complexity bound in Corollary 3 compare with existing guarantees under comparable assumptions? Please make the dependence on maximum indegree, signal strength, and covariance spectral bounds explicit, including the dependence hidden in the recovery tolerance ϵalg\epsilon_{\mathrm{alg}}.

Under comparable equal-variance Gaussian assumptions, the covariance plug-in version of FiCS matches the ordering rate of Daskalakis et al. (2025, Theorem 2.1). Given a correct order, their sufficient parent-recovery sample size scales as Hδτbmin⁡−2H_\delta\tau b_{\min}^{-2}. At fixed confidence, the parent-recovery rates agree for maximum indegree d≤p1−γd\le p^{1-\gamma} with fixed γ>0\gamma>0. The FiCS bound can be larger at higher indegrees.

Normalize the common error variance to one and assume 1≤q=d≤p/21\le q=d\le p/2 and 0<bmin⁡≤10<b_{\min}\le1, where bmin⁡b_{\min} is the smallest absolute edge coefficient. Write τ=1+max⁡j∑i:j→ibji2\tau=1+\max_j\sum_{i:j\to i}b_{ji}^2 and g=bmin⁡2/(bmin⁡2+τ)g=b_{\min}^2/(b_{\min}^2+\tau). The ordering margin is at least bmin⁡2/(1+bmin⁡2)b_{\min}^2/(1+b_{\min}^2), and omitting a parent raises the population score by at least gg. For a common parent penalty satisfying 0<dλ<g0<d\lambda<g, Theorem 3 (Section 5.1) therefore guarantees exact recovery when every local score error is strictly below

ϵalg=12min⁡(bmin⁡21+bmin⁡2,λ,g−dλ).\epsilon_{\mathrm{alg}} = \frac{1}{2}\min\left(\frac{b_{\min}^{2}}{1+b_{\min}^{2}}, \lambda, g-d\lambda\right).

For the parent-recovery bound in Table 2 of the revised manuscript (Appendix C), the proof in Appendix D.5 compares each candidate set with the true parent set on the same observations. Using the regression on their union as a common reference lets us control the difference between their scores directly. With Hδ=dlog⁡(ep/d)+log⁡(p/δ)H_\delta=d\log(\mathrm e p/d)+\log(p/\delta) and the parent penalty λ=Cλlog⁡(p/δ)/n\lambda=C_\lambda\log(p/\delta)/n for a sufficiently large constant CλC_\lambda, the revised analysis gives the following sufficient sample sizes at confidence 1−δ1-\delta.

  • Ordering: n≳Hδbmin⁡−4n\gtrsim H_\delta b_{\min}^{-4}.
  • Parent recovery from a correct order: n≳Hδ+dτbmin⁡−2log⁡(p/δ)n\gtrsim H_\delta+d\tau b_{\min}^{-2}\log(p/\delta).

Both guarantees are free of covariance eigenvalue bounds.

Question 2-2.

If the bound is weaker, does this reflect a limitation of the analysis or of the parent-selection rule?

We compare our sample-complexity bounds with Daskalakis et al. (2025), who study the same equal-variance linear Gaussian SEM setting and derive sharp guarantees without covariance condition-number assumptions. Their results provide a direct benchmark for comparing the dependence on maximum indegree and minimum edge strength. The ordering bounds coincide. The table below reproduces the comparison in Table 2 of the revised manuscript (Appendix C).

MethodOrderingParents given a correct order
FiCS (covariance plug-in)Hδbmin⁡−4H_\delta b_{\min}^{-4}Hδ+dτbmin⁡−2log⁡(p/δ)H_\delta+d\tau b_{\min}^{-2}\log(p/\delta)
Daskalakis et al. (2025)Hδbmin⁡−4H_\delta b_{\min}^{-4}Hδτbmin⁡−2H_\delta\tau b_{\min}^{-2}

Parent-selection rule. The common cardinality penalty leads to the term dτbmin⁡−2log⁡(p/δ)d\tau b_{\min}^{-2}\log(p/\delta) in our sufficient parent-recovery bound. Retaining a true parent set requires controlling its total penalty, which can be as large as dλd\lambda. Combining the sufficient retention condition dλ≲bmin⁡2/(bmin⁡2+τ)d\lambda\lesssim b_{\min}^2/(b_{\min}^2+\tau) with λ≳log⁡(p/δ)/n\lambda\gtrsim\log(p/\delta)/n gives this term.

Conflict across nodes. A common penalty can face incompatible requirements across nodes: to retain a large true parent set, it must be small enough; to reject spurious edges elsewhere, it must be large enough. The paragraph "An actual conflict between common penalties" in Appendix D.5 gives a Gaussian example, where one predecessor can act as a proxy for all dd true parents of a node. At n=⌊dlog⁡d⌋n=\lfloor d\log d\rfloor, with probability tending to one, the covariance plug-in rule fails to recover the DAG for every common penalty, even with a correct order. On the same graph family, the bound of Daskalakis et al. is O(d)O(d) at confidence 1−d−21-d^{-2}.

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

The paper studies causal discovery in nonlinear additive noise models when the graph is sparse. Under the stated assumptions, the key result (Thm 1) is that, for a node ii and a set TT of nondescendants, the Fisher information of XiX_i given XTX_T equals the noise Fisher information exactly when TT contains all parents. Based on this property, the parent set is identified as the smallest set of nondescendants for which this equality holds. Their proposed algorithm, FiCS, uses the same local Fisher score for both stages: source-first ordering over conditioning sets of size up to qq, followed by penalized parent selection. Each query therefore involves at most q+1q+1 variables. The theory gives population recovery when q≥dq\ge d and the ordering margin is positive (Thm 2), shows that reducing qq while keeping q≥dq\ge d can improve that margin (Prop 1), and establishes high-dimensional consistency under additional regularity, separation, and tuning conditions (Thm 3–4, Cor 1). Experiments on ER graphs with mixed linear/GP mechanisms show the largest gains when samples are few relative to variables, plus a qq ablation and three real benchmarks.

Critical strengths

The theory seems correct and cleanly layered. Thm 1 makes the parent set identifiable through an exact equality condition on local Fisher information. Thm 3 allows the kernel estimator to be replaced by a computationally cheaper alternative, provided it satisfies the required uniform bound on local-score estimation error.

The paper also establishes that locality matters beyond computation. Prop 1 tells that reducing qq, while keeping q≥dq\ge d, cannot decrease and can strictly increase the population ordering margin, which strengthens the rationale for FiCS. Figure 3 provides complementary empirical evidence for the benefits of locality.

Critical weaknesses

First, the experiments don't separate the value of Fisher information from the value of local subset search. The main generator uses N(0,1)N(0,1) noise at every node, which is a favorable case of Cor 2 and a regime where bounded-subset conditional variance already works at the population level. The score-based baselines estimate scores over all remaining variables, so their collapse at p>np>n may reflect the difficulty of high-dimensional estimation. A natural control in the linear Gaussian setting, FiCS with the App C covariance score and everything else fixed, is missing, and FiCS drops sharply under the tested unequal noise scales (App G.1). So the evidence currently supports "local search works when nn is small" more than "local Fisher information is the reason".

Second, the method depends on units, and the real-data configuration is unexplained. Scores scale as ai−2a_i^{-2} when XiX_i is rescaled by aia_i. With X1=ε1X_1=\varepsilon_1 and X2=X1+ε2X_2=X_1+\varepsilon_2, where ε1,ε2∼iidN(0,1)\varepsilon_1,\varepsilon_2\overset{\mathrm{iid}}{\sim}N(0,1), exact scores pick the root, but halving X2X_2 makes them pick the child first. This is not a counterexample to Thm 2, since the margin fails, but it shows that whether the margin holds depends on units. The real data are used in raw units (App F.7), and FiCS uses c=0.0003c=0.0003 there instead of the calibrated 0.8, with no explanation of how it, uu or rr were chosen. The results depend on these choices: changing uu or rr drops Sachs F1 from 0.538 to between 0.417 and 0.500, no better than CaPS.

Questions for authors
  1. Can you report F1, SHD and runtime for FiCS with the App C covariance score (same search, qq and penalty) on linear, mixed and all-GP settings, and add a bounded-subset conditional-variance baseline to Fig 2?

  2. How were the real-data values of (u,r,c)(u,r,c) chosen, and were the reference graphs used to select or tune them?

  3. What AtopA_{top} do VarSort and R2Sort get on the three real datasets in raw units, and how does FiCS do after standardizing each variable?

  4. App E.1 states that the implemented bandwidth-and-ridge rule is not directly analyzed. Can you report a run using bandwidth and ridge choices compatible with Thm 4?

As suggestions only:

  1. Briefly summarize the key caveats from G.1, G.2, G.4, and E.1 in the main text.

  2. Report the CaPS success counts from App F.5 alongside Fig 2 (only 2 of 30 fits succeeded at p=200p=200, n=50n=50).

8 comments
AuthorsOpenReview ↗

Response to Reviewer RNLR [1/4]

We appreciate the reviewer's suggestions of controls and the questions on how the theory covers the experiments. They helped us separate the contributions of the Fisher score and the local search and compare FiCS with VarSort and R2R^2Sort on real data. More importantly, the request for a run compatible with Theorem 4 led us to revise the theorem (Section 5.2 of the revised manuscript) so that it covers a ridge given explicitly in terms of nn and pp, and to rerun the experiments with it.

Weakness 1-1 and Question 1. Fisher score versus local search

Weakness 1-1. First, the experiments don't separate the value of Fisher information from the value of local subset search. The main generator uses N(0,1)N(0,1) noise at every node, which is a favorable case of Cor 2 and a regime where bounded-subset conditional variance already works at the population level. The score-based baselines estimate scores over all remaining variables, so their collapse at p>np>n may reflect the difficulty of high-dimensional estimation. A natural control in the linear Gaussian setting, FiCS with the App C covariance score and everything else fixed, is missing […]. So the evidence currently supports "local search works when nn is small" more than "local Fisher information is the reason".

Question 1. Can you report F1, SHD and runtime for FiCS with the App C covariance score (same search, qq and penalty) on linear, mixed and all-GP settings, and add a bounded-subset conditional-variance baseline to Fig 2?

We thank the reviewer for asking which component drives the accuracy of FiCS. To separate the effect of the Fisher score from that of the local search, we changed one component at a time and found that both contribute. The Fisher score improves accuracy on nonlinear data as nn grows. The gain from the local search grows as pp grows relative to nn.

(i) Changing only the score. We replaced only the Fisher score in FiCS by the local conditional variance, with the same search, cap q=2q=2, and parent penalty, and the table reports mean F1, SHD, and fit CPU time over the same 30 inputs per row at p=50p=50.

MechanismnnFiCS F1FiCS SHDFiCS Fit CPU time (s)Local conditional variance F1Local conditional variance SHDLocal conditional variance Fit CPU time (s)
All linear50.65640.771.97.87013.000.0454
100.84918.603.32.9742.330.0453
200.9406.639.21.9960.330.0443
500.9990.0761.531.0000.000.0475
10001.0000.00313.091.0000.000.0452
Mixed linear–GP50.42561.601.97.56936.100.0456
100.64036.333.31.66127.770.0453
200.78420.139.18.71523.900.0441
500.8959.7757.21.74322.000.0473
1000.9247.03309.61.76420.530.0450
All GP50.20579.131.97.20354.770.0454
100.38751.473.32.28646.500.0453
200.60831.209.19.34743.500.0440
500.73621.4754.31.41440.370.0475
1000.80516.53267.07.44739.030.0450

At small nn, local conditional variance is more accurate even on mixed data, because its linear model has few parameters and needs fewer observations, whereas the kernel Stein estimate of the Fisher score gains only once nn is large enough. With more observations, a local linear fit can miss part of a nonlinear parent's effect, which the Fisher score captures because it makes no linearity assumption. Figure 2 (Section 6.1 of the revised manuscript) shows the same pattern at p=50,100,200p=50,100,200. See Table 4 in Appendix F.3 for the comparisons across mechanisms and sample sizes.

(ii) Changing only the conditioning size. We changed only the conditioning size for ordering from two to all predecessors, which lowers mean F1 at n=100n=100 by .024.024 at p=50p=50 and by .124.124 at p=200p=200, as shown in Figure 3 (Section 6.2). The gain from the local search therefore grows with pp, which is consistent with the reviewer's point that the full-score baselines decline at p>np>n because they estimate scores over all remaining variables.

AuthorsOpenReview ↗

Response to Reviewer RNLR [2/4]

Weakness 1-2. Unequal noise scales

[…] FiCS drops sharply under the tested unequal noise scales (App G.1).

Thank you for highlighting the sensitivity to unequal noise scales. On mixed linear–GP data at n=1000n=1000, both methods lose accuracy as the noise range widens. With the search and parent penalty held fixed, FiCS has higher mean directed F1 and lower mean SHD than local conditional variance at every tested scale.

Corollary 2 (Appendix A.2 of the revised manuscript) gives a sufficient ordering condition that allows unequal scales when noise Fisher information is nonincreasing along directed paths. Independently drawn scales can violate this condition. The s=1s=1 row uses the 30 mixed linear–GP inputs from Weakness 1-1 at n=1000n=1000 (Table 4 in Appendix F.3). We hold the DAGs, mechanisms, and base Gaussian noise draws fixed and multiply each node's noise by sZjs^{Z_j}. We draw ZjZ_j independently from Uniform[−1,1]\mathrm{Uniform}[-1,1] once per node and reuse it at every scale. Appendix G.1 reports the comparison under "Unequal Gaussian noise at a larger sample size."

ssFiCSLocal conditional variance
1.924 / 7.03.764 / 20.53
1.2.824 / 13.87.701 / 24.47
1.4.688 / 23.07.624 / 29.50
1.6.603 / 29.13.554 / 33.93
1.8.547 / 32.80.517 / 36.30
2.490 / 36.63.470 / 39.30

Mean directed F1 / SHD over 30 matched inputs per row (p=50p=50, n=1000n=1000, q=2q=2).

Mean ordering accuracy AtopA_{\mathrm{top}} falls from .972.972 to .704.704 for FiCS and from .944.944 to .692.692 for the control as ss increases from 11 to 22.

Weakness 2-1. Dependence on measurement units

Second, the method depends on units […]. Scores scale as ai−2a_i^{-2} when XiX_i is rescaled by aia_i. […] it shows that whether the margin holds depends on units.

We thank the reviewer for pointing out that the FiCS ordering margin depends on measurement units. This is a central open problem in causal discovery, since the same dependence holds for ordering-based methods, from linear Gaussian SEMs ([1]; Chen et al., 2019; Gao et al., 2022) to ANMs that include the linear Gaussian case (Park, 2020; CaPS, Xu et al., 2024). Section 8 (Discussion) of the revised manuscript now states this sensitivity to coordinate scaling as a limitation of FiCS.

A common rescaling multiplies all population ordering scores by the same positive factor, preserving their ranking. Coordinatewise rescaling preserves the population parent-completion property in Theorem 1 (Section 3.1). The ordering guarantee in Theorem 2 (Section 3.2) requires a positive margin in the units used. Beyond existing score-based methods for linear and nonlinear ANMs, such as CaPS, FiCS orders source-first with local scores, which keeps it accurate when pp exceeds nn.

References

[1] Peters, J. and Bühlmann, P. (2014). Identifiability of Gaussian structural equation models with equal error variances. Biometrika, 101(1):219–228.

Weakness 2-2 and Question 2. Choice of real-data hyperparameters

Weakness 2-2. The real data are used in raw units (App F.7), and FiCS uses c=0.0003c=0.0003 there instead of the calibrated 0.8, with no explanation of how it, uu or rr were chosen. […]

Question 2. How were the real-data values of (u,r,c)(u, r, c) chosen, and were the reference graphs used to select or tune them?

Thank you for asking how these settings were chosen. We initially used a common candidate grid and selected a configuration separately for each dataset by minimizing BIC on the observed data. During the subsequent sensitivity analysis, we reported a single configuration, (u,r,c)=(0.5,1,0.0003)(u,r,c)=(0.5,1,0.0003), to present all three benchmarks under the same settings. Relative to the initial BIC selections, the common setting raised directed F1 on Sachs and Danube and lowered it on CausalRivers. We recognize that this reporting choice could have favored FiCS in individual comparisons.

In the revision, we report the results of BIC selection for each input, including each CausalRivers subnetwork. The common grid includes the four simulation configurations in Table 3 (Appendix E.3). We also cross bandwidth triples 16j(0.65,0.75,0.85)16^j(0.65,0.75,0.85) for j=0,1,2j=0,1,2 with amplitudes (1,1,1)(1,1,1) and (3,6,10)(3,6,10), ridge multipliers {0.025,0.05,0.125,0.25}\{0.025,0.05,0.125,0.25\}, and parent-penalty multipliers 10−410^{-4}, 10−310^{-3}, 10−210^{-2}, 0.20.2, and 0.80.8. We compute BIC from the observed data and the fitted candidate DAGs and use the reference graphs only to evaluate the selected DAGs. FiCS has the highest directed F1 among the methods in Table 1 (Section 7 of the revised manuscript) on all three benchmarks.

BenchmarkFiCS directed F1Best Table 1 baseline
Sachs.516.500 (CaPS)
Danube.452.400 (SCORE)
CausalRivers.475.416 (NoGAM)

Appendix G.3 of the revised manuscript lists the candidate grid, the BIC scoring rule, and the tie-breaking order. Tables 8 and 9 in that appendix report the sensitivity analyses around the BIC-selected configurations.

AuthorsOpenReview ↗

Response to Reviewer RNLR [3/4]

Question 3-1. VarSort and R2R^2Sort on real data

What AtopA_{\mathrm{top}} do VarSort and R2Sort get on the three real datasets in raw units, […]

We appreciate the reviewer's question about sortability on real data. In raw units, FiCS has the highest directed F1 among the three methods on Sachs and Danube. VarSort leads on both AtopA_{\mathrm{top}} and directed F1 on CausalRivers.

Both sorters attain higher AtopA_{\mathrm{top}} than FiCS on Sachs. On Danube, every reference edge points forward in all three estimated orders, so the F1 difference reflects which edges the methods select. For AtopA_{\mathrm{top}}, CaPS, SCORE, and NoGAM in Table 1 (Section 7 of the revised manuscript) all tie FiCS on Sachs (.529.529), and SCORE also ties FiCS on Danube (1.0001.000). FiCS leads these three baselines on CausalRivers.

In the separate synthetic comparison in Table 12 (Appendix G.4), FiCS has the highest AtopA_{\mathrm{top}} in five of six regimes at n=100n=100. In the UUMC population comparison, R2R^2Sort attains .492.492 and FiCS .465.465.

BenchmarkMethodAtopA_{\mathrm{top}}F1SHD
SachsVarSort.588.38513
R2R^2Sort.706.46211
FiCS.529.51613
DanubeVarSort1.000.37936
R2R^2Sort1.000.36738
FiCS1.000.45217
CausalRiversVarSort.958.5335.07
R2R^2Sort.625.3716.33
FiCS.892.4755.27

Both sorting baselines select edges by sparse regression on predecessors [1, 2]. Section 7 of the revised manuscript now points to the comparison in Table 10 (Appendix G.3).

References

[1] Reisach, A., Seiler, C., and Weichwald, S. (2021). Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy to Game. Advances in Neural Information Processing Systems, 34, 27772–27784.

[2] Reisach, A., Tami, M., Seiler, C., Chambaz, A., and Weichwald, S. (2023). A Scale-Invariant Sorting Criterion to Find a Causal Order in Additive Noise Models. Advances in Neural Information Processing Systems, 36, 785–807.

Question 3-2. FiCS after standardization

[…] and how does FiCS do after standardizing each variable?

Standardization lowers AtopA_{\mathrm{top}} and F1 of FiCS on all three benchmarks. We reselect FiCS hyperparameters by BIC on the standardized data using the same candidate grid as in raw units. Since FiCS uses the relative scales of the variables, standardization can remove its ordering signal, as for other scale-based methods ([1]; Park, 2020). In these benchmarks, the variables of each dataset are measurements of the same kind, river discharges in Danube and CausalRivers and protein abundances in Sachs, so the recorded units keep their relative scales.

BenchmarkUnitsAtopA_{\mathrm{top}}F1SHD
SachsRaw.529.51613
Standardized.294.13818
DanubeRaw1.000.45217
Standardized.545.25021
CausalRiversRaw.892.4755.27
Standardized.642.3475.87

We recognize this limitation and now report the standardized results in Table 11 (Appendix G.3 of the revised manuscript).

References

[1] Peters, J. and Bühlmann, P. (2014). Identifiability of Gaussian structural equation models with equal error variances. Biometrika, 101(1):219–228.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.