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:
- 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.
- 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