Score matching through the roof: linear, nonlinear, and latent variables causal discovery

Francesco Montagna, Philipp M. Faller, Patrick Bloebaum, Elke Kirschbaum, Francesco Locatello

TL;DR

This paper introduces AdaScore, a flexible causal discovery algorithm that leverages the score function ($\nabla \log p(X)$) to infer causal relationships. Crucially, it breaks free from the rigid assumptions of prior methods by successfully handling linear, nonlinear, and latent (hidden) variable models under a unified framework.

What Problem Does This Paper Address?

Causal discovery—the task of learning cause-and-effect graphs from purely observational data—is notoriously difficult. Traditional methods typically suffer from two major pain points:

  1. The Full Observability Assumption: They assume we have measured every relevant variable. In reality, hidden confounders (unobserved variables that influence multiple observed ones) are everywhere.
  2. Rigid Functional Assumptions: Existing algorithms are often hyper-specialized. For instance, some only work if the relationships are strictly linear and non-Gaussian, while others fail unless the relationships are strictly nonlinear.

The authors address this gap by showing that the score function (the gradient of the log-probability density of the observed data) contains rich geometric information that can map out causal structures even when hidden confounders are present and functional forms vary.

Methods

The authors propose AdaScore (Adaptive Score-matching-based causal discovery). The method builds on two primary theoretical pillars:

  • Vanishing Cross-Partials for Equivalence Classes: The authors show that constraints on the Jacobian/Hessian of the score function ($\nabla^2 \log p(X)$) can identify the Markov equivalence class of a causal graph, even with latent variables. This generalizes constraint-based approaches like the Fast Causal Inference (FCI) algorithm.
  • Score-Matching for Direct Causes: For additive noise models (ANMs), the score component of a "sink" node (a node with no children) depends purely on its regression residual. AdaScore uses this property to iteratively find sinks, prune graph neighborhoods, and orient edges.

What's new: Unlike previous score-matching methods (like NoGAM) that assume strict nonlinearity, this paper proves that nonlinearity is not necessary. Furthermore, it extends score-based edge orientation to settings with latent variables.

In practice, the algorithm uses the Stein gradient estimator to approximate the score function from finite samples and employs Kernel Ridge Regression (KRR) to estimate regression residuals flexibly.

Datasets

The authors evaluated AdaScore using both synthetic and real-world benchmark datasets:

  • Synthetic Data: Random graphs generated via the Erdős-Rényi model (both sparse and dense configurations). Hidden variables were introduced by randomly dropping two nodes from the data matrix.
  • Sachs Causal Protein-Signaling Network: A classic biological dataset (1,000 samples) mapping flow cytometry data.
  • AutoMPG Dataset: A pseudo-real dataset concerning fuel consumption in cars, using a known causal ground truth.
  • Sim2 fMRI Dataset: A realistic synthetic dataset simulating blood-oxygen-level-dependent (BOLD) signals from functional magnetic resonance imaging.

Key Insights and Ideas

  • Linearity is Welcome: Previously, researchers believed score-matching causal discovery strictly required nonlinear mechanisms. This paper proves that "restricted additive noise models"—which encompass linear non-Gaussian settings—are perfectly identifiable using the score.
  • Local Causal Discovery is Possible: AdaScore can discover parent-child relationships between a targeted pair of nodes without needing to compute the global topological order of the entire graph. This makes it highly attractive for targeted, local causal queries.
  • Adaptivity by Design: Depending on what the user believes about their data, AdaScore can adaptively output a Directed Acyclic Graph (DAG), a Partial Ancestral Graph (PAG), or a mixed graph that explicitly accounts for latents.

Key Results

The primary metric used for evaluation was the Structural Hamming Distance (SHD), where a lower score indicates fewer missing or wrongly directed edges.

  • Fully Observable Settings: On nonlinear data, AdaScore significantly outperformed linear baselines like RCD and matched state-of-the-art nonlinear methods (CAM-UV, NoGAM).
  • Latent Variable Settings: When hidden confounders were introduced, AdaScore remained highly competitive with CAM-UV and vastly outperformed RCD, which degraded rapidly as the number of nodes increased.
  • Real Benchmarks: On the Sachs cell-signaling dataset, AdaScore achieved the lowest SHD among all tested methods. It also maintained competitive, robust performance across the AutoMPG and fMRI datasets.

Limitations and Future Work

  • Scalability Bottlenecks: Computing score functions and iterating through subsets of neighborhoods is computationally expensive. The synthetic experiments were strictly limited to graphs with 9 nodes because both AdaScore and CAM-UV struggle to scale to high-dimensional spaces.
  • Worst-Case Complexity: While the algorithm runs in polynomial time under ideal conditions (when unconfounded sinks are easily found), its worst-case complexity remains exponential ($O(d^2 \cdot 2^d)$) relative to the number of observed nodes $d$.

The authors suggest that future work should focus on optimizing these score-matching principles specifically for local causal discovery to bypass the global computational burden.

Summary updated

Abstract

Causal discovery from observational data holds great promise, but existing methods rely on strong assumptions about the underlying causal structure, often requiring full observability of all relevant variables. We tackle these challenges by leveraging the score function $\nabla \log p(X)$ of observed variables for causal discovery and propose the following contributions. First, we fine-tune the existing identifiability results with the score on additive noise models, showing that their assumption of nonlinearity of the causal mechanisms is not necessary. Second, we establish conditions for inferring causal relations from the score even in the presence of hidden variables; this result is two-faced: we demonstrate the score's potential to infer the equivalence class of causal graphs with hidden variables (while previous results are restricted to the fully observable setting), and we provide sufficient conditions for identifying direct causes in latent variable models. Building on these insights, we propose a flexible algorithm suited for causal discovery on linear, nonlinear, and latent variable models, which we empirically validate.
BibTeX
@inproceedings{montagna2025score,
  author = {Francesco Montagna and Philipp M. Faller and Patrick Bloebaum and Elke Kirschbaum and Francesco Locatello},
  title = {{Score matching through the roof: linear, nonlinear, and latent variables causal discovery}},
  booktitle = {CLeaR},
  year = {2025},
  url = {https://openreview.net/forum?id=HNMuBz1JXO},
}
Figure