Research map / Graph learning / Graph algorithms and clustering
Analytic DAG Constraints for Differentiable DAG Learning
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 analytic functions with positive power-series coefficients yield valid DAG constraints, closed under differentiation, addition and multiplication, and uses them (orders 1-4) in a path-following solver that beats DAGMA on linear and some nonlinear DAG learning benchmarks.
Problem
Continuous (differentiable) DAG learning suffers from gradient vanishing and numerical issues in existing acyclicity constraints (matrix exponential, log-det, polynomial), and their spectral-radius/scale handling is unclear, especially for normalized data.
Approach
Characterize a class of analytic functions with positive coefficients and finite radius of convergence that yield valid DAG constraints via tr f(B∘B)=c0 d; show this class is closed under differentiation, sum and product, so new constraints (e.g., f_inv=(s-x)^-1 powers, f_log) can be derived, with a cheap doubling-based evaluation of the power series.
Key results
- On ER2/3/4 Gaussian graphs with 500-2000 nodes, the order-1 to order-4 analytic constraints beat DAGMA in SHD in most settings, e.g., ER2-Gaussian 500 nodes: 29.80 (order-4) vs 44.90 (DAGMA).
- On 1000-node normalized ER1 Gaussian graphs, order-4 achieves SHD 389.4 vs DAGMA 588.8, PC 563.9, GES 4490.2.
- On the GraN-DAG dataset in single precision, the analytic constraints reduce SHD from 15 (original GraN-DAG) to 13 for all orders.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply the analytic Order 4 DAG constraint | continuous DAG learning · 1000-node ER1 Gaussian, normalized | SHD: 488.6± 24.29 -> 389.4 ± 16.70 | Helped |
| apply analytic Order 4 instead of DAGMA | continuous DAG learning · ER2, ER3, and ER4 Gaussian graphs with 1000 nodes | SHD: 94.80 ± 35.80 -> 52.40 ± 19.86; 339.60 ± 67.80 -> 165.80 ± 35.95; 878.50 ± 174.96 -> 626.30 ± 157.59 | Helped |
| use a higher-order DAG constraint (ablation) | analytic DAG learning · ER graphs with known scale | SHD | Mixed |
| use Order 4 rather than Order 2 (ablation) | analytic DAG learning · 1000-node SF2 | SHD: 22.50 ± 13.21 -> 58.10 ± 27.58 | Hurt |
| use Order 2 rather than Order 1 (ablation) | analytic DAG learning · 1000-node SF2 | SHD: 41.20 ± 36.02 -> 22.50 ± 13.21 | Helped |
| replace the original DAG constraint with Order 1 | GraN-DAG · Nonlinear dataset, single precision | SHD: 15 -> 13 | Helped |
| replace the original DAG constraint with Order 1 | GraN-DAG · Nonlinear dataset, double precision | SHD: 13 -> 13 | No clear effect |
| add a restriction allowing edges only between highly correlated nodes | analytic DAG learning with unknown scale · 1000-node ER1 Gaussian, normalized | SHD | Helped |
| use the analytic-function-based strategy to reset s rather than DAGMA's search strategy | Order 1 DAG constraint · linear SEM with known scale | SHD | Helped |
Surprising findings
- Order-4 constraints performed worse than lower orders on scale-free graphs, attributed to stronger non-convexity.
- On 2000-node exponential and Gumbel ER graphs, several methods including DAGMA reach TPR near 0, indicating failure at that scale.
Limitations
- Higher-order constraints show stronger non-convexity, which hurts performance on some settings (e.g., order-4 on SF graphs).
- Unknown-scale setting requires an extra correlation-based edge restriction (|corr|>0.1) that is a heuristic.
- Gains over DAGMA are often small relative to standard deviations.
Experimental setup
Datasets: synthetic ER and SF graphs (linear SEM, Gaussian/exponential/Gumbel noise) GraN-DAG nonlinear benchmark dataset
Benchmarks: synthetic ER2/3/4 and SF2/3/4 graphs with 500-2000 nodes 1000-node ER1 normalized data GraN-DAG dataset
Metrics: structural hamming distance true positive rate false detection rate running time
Baselines: DAGMA PC GES Exponential (NOTEARS) constraint GraN-DAG
Builds on: NOTEARS DAGMA GraN-DAG
Closest papers by meaning
- CoLiDE: Concomitant Linear DAG Estimation (ICLR 2024 · similarity 0.87)
- Markov Equivalence and Consistency in Differentiable Structure Learning (NeurIPS 2024 · similarity 0.86)
- ProDAG: Projected Variational Inference for Directed Acyclic Graphs (NeurIPS 2025 · similarity 0.86)
- Differentiable Structure Learning with Ancestral Constraints (ICML 2025 · similarity 0.86)
- Learning Gaussian DAG Models without Condition Number Bounds (ICML 2025 · similarity 0.85)
- Causal Discovery via Bayesian Optimization (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.