PaperlayerView exact revision on arXiv

Source-linked AI summary

Score matching enables causal discovery of nonlinear additive noise models

Paul Rolland, Volkan Cevher, Matthäus Kleindessner, Chris Russel, Bernhard Schölkopf, Dominik Janzing, Francesco Locatello

arXiv:2203.04413v1cs.LGstat.ML

TL;DR

Causal discovery from observational data can be ill-posed, and this paper studies recovery under nonlinear additive Gaussian noise assumptions. It uses the data score and a score-Jacobian estimator to recover causal graphs; the authors report competitive results with faster runtimes than named methods. The work also identifies assumptions and extensions that delimit its scope.

  • Problem

    Causal discovery from observational data is generally ill-posed because different generative models can yield the same distribution, so recovery requires assumptions on the generative process.

    Source: §1 · p. 1

  • Method

    SCORE estimates a causal topological order from the data score, using an estimated score Jacobian to identify leaves sequentially before pruning the resulting graph.

    Source: §1 · p. 2

  • Results

    The authors report competitive results on synthetic and real-world data, with runtimes 10× faster than CAM [8] on 20-node graphs and 5× faster than GraN-DAG [14] on 50-node graphs.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For nonlinear additive Gaussian noise models, the paper establishes a connection between the score and causal graph structure and presents score estimation as an application for causal discovery.

    Source: §6 · p. 9

    The analysis assumes twice continuously differentiable link functions that are nonlinear in every parent component, and the paper leaves application beyond additive Gaussian noise for further study.

    Source: §2.1 · p. 2, §6 · p. 9

Abstract

from arXiv · show

This paper demonstrates how to recover causal graphs from the score of the data distribution in non-linear additive (Gaussian) noise models. Using score matching algorithms as a building block, we show how to design a new generation of scalable causal discovery methods. To showcase our approach, we also propose a new efficient method for approximating the score's Jacobian, enabling to recover the causal graph. Empirically, we find that the new algorithm, called SCORE, is competitive with state-of-the-art causal discovery methods while being significantly faster.

1 Introduction

The paper proposes SCORE, an order-based approach that uses the data distribution’s score to recover causal graphs in nonlinear additive Gaussian noise models. It introduces a score-Jacobian estimator and reports competitive results with substantially faster runtimes than named state-of-the-art methods.

1 Introduction

  • Observational causal discovery is generally ill-posed, while additive-noise assumptions with additional link-function assumptions can make the model identifiable [3].The paper situates this challenge alongside classical DAG optimization, which is NP-hard, and heuristic or continuous-optimization approaches.Source: §1 · p. 1
  • Order-based methods first seek a node ordering and then prune edges; a fixed order enforces acyclicity and makes pruning easier.The paper relates its use of score estimation to broader work on score-based generative and discriminative models.Source: §1 · pp. 1–2
  • SCORE estimates a topological order from the data score, identifies leaves sequentially, and then applies classical pruning to recover the graph.The authors state that identifying the order has linear complexity in the number of nodes.Source: §1 · p. 2
  • A new estimator extends Stein-identity methods to approximate the score’s Jacobian over observations, supporting practical estimation of the causal order.The authors also describe the estimator as potentially useful independently of this algorithm.Source: §1 · p. 2
  • 10× faster than CAM [8] on 20-node graphs and 5× faster than GraN-DAG [14] on 50-node graphs, with competitive results against state-of-the-art methods.The evaluation includes synthetic and real-world data and reports robustness to noise misspecification and good performance with non-Gaussian additive noise.Source: §1 · p. 2

2 Preliminaries

The preliminaries specify the nonlinear additive Gaussian setting and explain why observational identifiability can be approached through the data score. They introduce score matching at sample points and the Stein-based estimator that the paper extends to estimate the score’s Jacobian.

2.1 Causal discovery for non-linear additive Gaussian noise models

  • The model assumes link functions that are twice continuously differentiable and nonlinear in every parent component.Source: §2.1 · p. 2
  • Under the stated identifiability result [3], the DAG can be recovered from the joint distribution, and the score is targeted because it corresponds one-to-one with that distribution.Source: §2.1 · p. 2
  • Here, “score” means ∇log p(x), distinguishing the statistical quantity from causal-literature uses of “score” for an optimization objective.Source: §2.1 · p. 2

2.2 Score matching

  • Score matching estimates the score function from an i.i.d. sample, and the presented Stein gradient estimator uses Stein’s identity with a Monte Carlo approximation and ridge regression.The estimator can use a kernel satisfying Stein’s identity, including the RBF kernel.Source: §2.2 · p. 3
  • The paper extends this score-estimation approach to estimate the score’s Jacobian at the observations.Source: §2.2 · p. 3

3 Causal discovery via score matching

The section develops causal graph recovery from the data distribution’s score, first for nonlinear additive Gaussian noise and then for broader additive noise models. It uses score-Jacobian structure to find a topological order and proposes a Stein-based estimator for the sample-level quantities needed by that procedure.

3.1 Deduce the causal graph from the score of the data distribution

  • Under nonlinear additive Gaussian noise, only leaf nodes have constant diagonal score-Jacobian entries; repeatedly removing them yields a full topological order.The method identifies a leaf using the variance of the corresponding diagonal entries.Source: §3.1 · p. 4

3.2 Approximation of the score’s Jacobian

  • To apply this criterion to samples, the method estimates score-Jacobian diagonals at observations using the second-order Stein identity and a ridge-regression Stein Hessian estimator.The RBF kernel bandwidth is set by the median pairwise distance and recomputed after each leaf removal.Source: §3.2 · pp. 5–6
  • O(dn^3 + dr(n, d)) is the stated total complexity including pruning, compared with CAM’s O(d^2r(n, d)).In tested settings, order estimation takes 30% of total time at (d, n) = (20, 1000) and 5% at (50, 1000); CAM spends more than 95% estimating order.Source: §3.2 · p. 6

3.3 Extension to non-Gaussian additive noise models

  • For general additive noise, the score has a common residual term and a parent-only term; non-Gaussian recovery is expected, but not formally identified.The paper attributes possible recovery to nonlinearities in the parent-only term, which it says scale with the number of parents.Source: §3.3 · p. 6

4 Numerical experiments

The experiments compare SCORE with causal-discovery baselines on synthetic and real-world data. SCORE performs competitively, with results varying by synthetic graph sparsity and favorable runtime comparisons.

4 Numerical experiments

  • The experiments compare against CAM and GraN-DAG, measuring SHD and SID and varying synthetic graph sparsity and noise type.They also measure topological-order divergence; synthetic data use Gaussian or Laplace noise, with Gumbel-noise experiments reported in the appendix.Source: §4 · p. 7, §4.1 · p. 7

4.1 Synthetic data

  • On synthetic data, SCORE performs similarly to CAM on ER1, better on ER4 with lower Dtop, and similarly to CAM on 50-node graphs.For the 50-node setting, the authors restricted the maximum number of neighbours, providing a sparsity prior.Source: §4.1 · p. 7, Table 1 · p. 7, Table 2 · p. 8
  • Accuracy remains very similar under Laplace noise; VarSort is generally worse, while the 50-node neighbour restriction fits the sparse Erdös-Rényi setting.With the neighbour restriction, CAM’s order-finding part does not yield a single order, so Dtop could not be computed in that setting.Source: §4.1 · p. 7, Table 4 · p. 8, Table 5 · p. 8
  • SCORE is significantly faster in the runtime comparison; at d = 50, CAM pruning accounts for 95% of its runtime.The runtime table compares algorithms on ER1 and identifies the first row as SCORE’s topological-order time.Source: §4.1 · p. 7, Table 7 · p. 8

4.2 Real data

  • On Sachs, SCORE matches CAM in SHD and improves SID; on SynTReN, GraN-DAG appears best, but confidence intervals overlap substantially.The real-world Sachs dataset has 11 nodes, 17 edges, and 853 observations; the SynTReN comparison uses 10 sampled datasets.Source: §4.2 · pp. 8–9, Table 8 · p. 9

5 Related work

Prior work addresses nonlinear additive causal discovery through likelihood optimization and ordering, while linear-model methods establish a related route through leaf identification. The paper also contrasts score-estimation choices and broader nonparametric approaches.

5 Related work

  • GraN-DAG optimizes observed-data likelihood with a continuous acyclicity constraint, while CAM estimates an order greedily and prunes with sparse regression.CAM additionally assumes additive structure in the link functions.Source: §5 · p. 9
  • For linear additive models, [19] provably recovers causal graphs in polynomial time and sample complexity under hypotheses on noise variances.Its order-based approach sequentially identifies leaves using an estimated precision matrix; for linear links, the score Jacobian equals the precision matrix.Source: §5 · p. 9
  • Other non-parametric approaches use faithfulness-related assumptions and conditional-independence tests to learn graphs matching identified conditional independences.The paper distinguishes these assumptions from its focus on identifiable nonlinear additive Gaussian noise models.Source: §5 · p. 9
  • Neural score estimation for generative modeling minimizes empirical Fisher divergence and performs well, but is computationally expensive and requires tuning several training parameters.Source: §5 · p. 9
  • The paper instead minimizes kernelized Stein discrepancy, which has a closed-form solution for fast estimation at all observations and performs similarly to score matching while computing faster.The asymptotic consistency of the Stein gradient estimator and its relation to score matching were analyzed in [43].Source: §5 · p. 9

6 Conclusion

The conclusion presents score-based causal discovery for nonlinear additive Gaussian noise models and describes extensions to other models and score estimators as future work.

6 Conclusion

  • For nonlinear additive Gaussian noise models, the causal graph can be recovered from the score, and the proposed approach combines score-Jacobian evaluation with DAG pruning.Any score-matching or pruning method can be plugged in to obtain a practical algorithm.Source: §6 · p. 9
  • The method prioritizes fast topological-order estimation without permutation search or heuristic optimization, but avoids high-dimensional generative score methods because retraining after each leaf removal is expensive.Amortization is identified as a promising direction for alleviating this computational cost.Source: §6 · p. 9
  • Applying score-based causal discovery beyond additive Gaussian noise remains future work, including how to read a model's graph from its score and whether a universal method exists.Source: §6 · pp. 9–10

A Additional experiments

The appendix reports additional synthetic-experiment tables covering Gumbel-noise Erdős–Rényi graphs and Gaussian-noise scale-free graphs.

A Additional experiments

Related papers

Loading 2203.04413v1…