TL;DR
This paper presents a massive benchmarking study evaluating 12 mainstream causal discovery algorithms across 8 distinct real-world assumption violations. The authors discover that differentiable (gradient-based) causal discovery methods are remarkably robust against most forms of model misspecification—such as hidden confounders and missing data—with the notable exception of scale variation.
What Problem Does This Paper Address?
Causal discovery—the process of learning cause-and-effect relationships purely from observational data—is a holy grail in machine learning. However, traditional algorithms rely on strict, often unverifiable assumptions: that data is independent and identically distributed (i.i.d.), that there are no unobserved hidden causes (causal sufficiency), and that measurement is error-free.
In the real world, these assumptions are routinely violated. Data is messy, variables are measured with noise, and underlying mechanisms are rarely perfectly linear or cleanly Gaussian. While specialized algorithms exist for specific violations, practitioners rarely know which assumptions are broken in their data. This paper addresses a critical gap: How robust are mainstream causal discovery methods—especially recent, fast differentiable approaches—when their foundational assumptions fail?
Methods
The authors conduct a comprehensive evaluation of 12 prominent causal discovery algorithms, categorizing them into four paradigms:
- Constraint-based: PC
- Score-based: GES
- Functional Causal Model (FCM)-based: DirectLiNGAM, CAM, Var-SortnRegress, $R^2$-SortnRegress
- Differentiable/Gradient-based: NOTEARS, GOLEM, NOTEARS-MLP, GraN-DAG, NoCurl, DAGMA
The algorithms' built-in assumptions are summarized by the authors below:
These methods were stress-tested against eight model assumption violations:
- Latent Confounders: Unobserved variables influencing multiple observed variables.
- Measurement Error: Adding independent noise to the observed variables.
- Autoregressive Effects: Introducing temporal dependencies.
- Unfaithful Distribution: Causal effects along different paths canceling each other out.
- Heterogeneous Effects: Data coming from multiple domains with varying noise distributions.
- Scale-Variant Effects: Variables scaled differently, altering variance.
- Missing Mechanisms: Data Missing Completely At Random (MCAR).
- Mechanism Violation: Feeding nonlinear data into linear models, and vice versa.
Datasets
The scale of the empirical evaluation is massive, encompassing over 70,000 experiments across:
- Synthetic Datasets: More than 2,400 graphs generated using Erdős-Rényi (ER), Scale-Free (SF), and Gaussian Random Partitions (GRP) models, with node counts $d \in \{10, 20, 50\}$.
- Real-World Dataset: The widely accepted Sachs dataset (7,466 samples, 11 nodes, 17 edges), which measures protein signaling networks in human immune cells.
- Semi-Synthetic Datasets: Data generated using linear and nonlinear vanilla mechanisms structured around the real-world Sachs network topology.
Key Insights and Ideas
- The Resilience of Differentiable Methods: Differentiable methods (like DAGMA and NOTEARS-MLP) optimize a continuous score function over a graph space using gradient descent. Surprisingly, this continuous optimization framework gives them a "soft cushion" that allows them to degrade gracefully rather than fail catastrophically when assumptions like causal sufficiency are violated.
- Scale Variation is the Achilles' Heel: Differentiable methods suffer severely when data scales vary across nodes. The authors note that variance-sorting methods or traditional score-based methods handle scale variation much better because gradient-based losses are highly sensitive to magnitude imbalances.
- The "Noise Ratio" Explains the Failure Modes: The authors provide theoretical backing for why methods degrade under measurement error and unfaithfulness. They show that these violations artificially inflate the "noise ratio" ($r$) between the maximum and minimum error variances. When this ratio exceeds a certain theoretical threshold, least-squares optimization mathematically can no longer guarantee finding the correct Directed Acyclic Graph (DAG).
Key Results
The performance was evaluated using Structural Hamming Distance (SHD, measuring edge errors) and Structural Intervention Distance (SID, measuring causal ordering errors).
- Synthetic Benchmarks: As illustrated in the radar charts above, differentiable methods consistently occupied the inner rings (lower SHD/SID, meaning better performance) across 7 out of the 8 challenging scenarios, showing clear superiority over traditional constraint- and score-based methods.
- Real-World Sachs Dataset: DAGMA (a differentiable method) achieved the best overall performance with an SHD of 12 and SID of 42, outperforming traditional benchmarks like PC (SHD=22, SID=49) and GES (SHD=30, SID=47).
- Computational Efficiency: Differentiable methods proved to be highly practical. For instance, on a 20-node graph, DAGMA executed in just 3.19 seconds, compared to the functional method CAM, which required 113.37 seconds.
Limitations and Future Work
While nonlinear differentiable methods show immense promise, the authors acknowledge that handling scale-variant data remains an open and difficult challenge for them. Additionally, this study explicitly confined itself to non-temporal causal discovery. The authors highlight that benchmarking causal discovery under assumption violations within time-series data and event sequences is a crucial frontier for future research.
Summary updated