Research map / Probabilistic and scientific modeling / Causal discovery

Markov Equivalence and Consistency in Differentiable Structure Learning

NeurIPS 2024 · Probabilistic and scientific modeling › Causal discovery · approach: Differentiable and score-based DAG learning · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that differentiable acyclicity-constrained likelihood scores with quasi-MCP regularization recover the sparsest DAG and, under faithfulness, the Markov equivalence class, and are scale-invariant for Gaussian models.

Problem

Continuous (differentiable) score-based DAG structure learning relies on strong identifiability assumptions and uses least squares loss, which is sensitive to data scale (varsortability); it is unclear which score guarantees recovery of the sparsest model or Markov equivalence class under nonidentif

Approach

Replace the least squares score with the negative log-likelihood regularized by a differentiable nonconvex quasi-MCP penalty (an approximation of the l0 penalty) under an acyclicity constraint; show global minimizers are minimal-edge I-maps (sparsest representations), hence in the Markov equivalence class under faithfulness, and that the Gaussian log-likelihood score is scale-invariant.

Key results

• Global minimizers of log-likelihood plus quasi-MCP (for small lambda, delta) recover the minimal-edge equivalence class, and under faithfulness the Markov equivalence class (Theorems 3.x and 4.x).
• Gaussian log-likelihood score is scale-invariant: standardizing data does not change the recovered DAG structure at global optima, while NOTEARS, GOLEM and DAGMA degrade sharply on standardized data.
• On small graphs (ER-2, p=10) the logll-notears variants stay robust under standardization alongside PC and FGES, while VarSort and other CSL baselines deteriorate.

Measured effects reported in the paper

Surprising findings

• Standardization substantially degrades GOLEM, NOTEARS and DAGMA to roughly empty-graph performance, and VarSort with standardized data exceeds SHD 300 on average.

Limitations

• Theory relies on finite equivalence class, Lipschitz B(psi), and bounded level-set assumptions for general models.
• Global optimization becomes difficult as graph size grows, so scale invariance is not fully realized empirically for p=50 and above.
• Only parametric models and observational data are considered; interventional data and nonparametric models are left to future work.

Experimental setup

Datasets: synthetic linear Gaussian DAGs (ER and SF graphs)

Benchmarks: synthetic ER and SF graphs with p=10,20,50,70,100

Metrics: structural Hamming distance between CPDAGs

Baselines: NOTEARS GOLEM DAGMA VarSort FGES PC

Builds on: NOTEARS MCP SCAD sparsest Markov representation

Closest papers by meaning

• Differentiable Structure Learning with Partial Orders (NeurIPS 2024 · similarity 0.89)
• ProDAG: Projected Variational Inference for Directed Acyclic Graphs (NeurIPS 2025 · similarity 0.89)
• Differentiable Structure Learning with Ancestral Constraints (ICML 2025 · similarity 0.88)
• Constraint-Free Structure Learning with Smooth Acyclic Orientations (ICLR 2024 · similarity 0.87)
• Scores for Learning Discrete Causal Graphs with Unobserved Confounders (AAAI 2024 · similarity 0.87)
• A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the Same Skeleton (AAAI 2024 · similarity 0.87)