Research map / Graph learning / Graph algorithms and clustering
Constraint-Free Structure Learning with Smooth Acyclic Orientations
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.
Proposes COSMO, an unconstrained continuous method for learning DAGs by parameterizing the adjacency as a weight matrix times a smooth orientation matrix derived from a priority vector, with temperature annealing and no acyclicity evaluation during training.
Problem
Continuous structure learning of DAGs relies on acyclicity constraints (e.g., NOTEARS trace-exponential) whose cubic cost per step limits scalability.
Approach
Model acyclic orientations via a priority vector and a tempered, epsilon-shifted sigmoid of pairwise priority differences, so any weight matrix multiplied elementwise by the smooth orientation yields a DAG in the limit; temperature is annealed during training, avoiding acyclicity evaluation entirely.
Key results
- COSMO achieves AUC 0.984 on linear ER-4 with 30 nodes (Gauss), comparable to DAGMA 0.985 and NOTEARS 0.973, at about 88 s versus about 781 s for DAGMA and 5193 s for NOTEARS.
- At 500 nodes, COSMO is the only constrained-free method among those finishing with NOCURL failing to return within the wall-time limit; COSMO takes about 390-436 s versus DAGMA about 2485-2853 s.
- Removing priority regularization (COSMO-NP) reduces AUC from 0.984 to 0.937 on ER4 with 30 nodes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use COSMO instead of DAGMA | structure learning on ER-4 synthetic graphs · ER-4, 30 nodes, Gaussian noise | AUC: 0.985 ± 0.01 -> 0.984 ± 0.02 | No clear effect |
| Use COSMO instead of DAGMA | structure learning on ER-4 synthetic graphs · ER-4, 30 nodes, exponential noise | AUC: 0.986 ± 0.02 -> 0.989 ± 0.01 | Helped |
| Use COSMO instead of DAGMA | structure learning on ER-4 synthetic graphs · ER-4, 30 nodes, Gumbel noise | AUC: 0.973 ± 0.02 -> 0.914 ± 0.10 | Hurt |
| Use COSMO instead of DAGMA | structure learning on ER-4 synthetic graphs · ER-4, 100 nodes, Gaussian noise | AUC: 0.982 ± 0.01 -> 0.961 ± 0.03 | Hurt |
| Use COSMO instead of DAGMA | structure learning on ER-4 synthetic graphs · ER-4, 100 nodes, exponential noise | AUC: 0.986 ± 0.01 -> 0.985 ± 0.01 | No clear effect |
| Use COSMO instead of DAGMA | structure learning on ER-4 synthetic graphs · ER-4, 100 nodes, Gumbel noise | AUC: 0.986 ± 0.01 -> 0.973 ± 0.01 | Hurt |
| Use COSMO instead of DAGMA | structure learning on ER-4 synthetic graphs · ER-4, 500 nodes, Gaussian noise | AUC: 0.980 ± 0.00 -> 0.933 ± 0.01 | Hurt |
| Use COSMO instead of DAGMA | structure learning on ER-4 synthetic graphs · ER-4, 500 nodes, exponential noise | AUC: 0.984 ± 0.01 -> 0.986 ± 0.00 | No clear effect |
| Use COSMO instead of DAGMA | structure learning on ER-4 synthetic graphs · ER-4, 500 nodes, Gumbel noise | AUC: 0.980 ± 0.00 -> 0.982 ± 0.01 | No clear effect |
| Remove priority regularization (ablation) | COSMO · ER4, 30 nodes | AUC: 0.984 ± 0.02 -> 0.937 ± 0.05 | Hurt |
| Remove priority regularization (ablation) | COSMO · ER4, 100 nodes | AUC: 0.961 ± 0.03 -> 0.974 ± 0.02 | Helped |
| Remove priority regularization (ablation) | COSMO · ER6, 30 nodes | AUC: 0.921 ± 0.04 -> 0.885 ± 0.09 | Hurt |
Surprising findings
- NOCURL with an unconstrained ordering (NOCURL-U) performs far worse (AUC around 0.69), showing the preliminary constrained solution matters for NOCURL-style methods.
- COSMO's AUC drops to 0.933 on Gaussian ER4 with 500 nodes, below NOTEARS and DAGMA on that setting.
Limitations
- Results are on synthetic linear and nonlinear data without variance normalization; causal discovery applicability is not established.
- COSMO requires careful regularization and temperature hyperparameter tuning; priority regularization matters most for small graphs.
- Performance is comparable rather than uniformly superior to DAGMA and NOTEARS.
Experimental setup
Datasets: synthetic ER and scale-free DAGs (NOTEARS generator)
Benchmarks: synthetic ER4 and ER6 linear DAGs synthetic SF graphs
Metrics: AUC NHD TPR wall-clock time
Baselines: NOTEARS DAGMA NOCURL NOCURL-U DAGMA-MLP NOTEARS-MLP
Builds on: NOTEARS NOCURL DAGMA ENCO
Closest papers by meaning
- DAGs with NO TEARS: Continuous Optimization for Structure Learning (NeurIPS 2018 · similarity 0.90)
- Markov Equivalence and Consistency in Differentiable Structure Learning (NeurIPS 2024 · similarity 0.87)
- ProDAG: Projected Variational Inference for Directed Acyclic Graphs (NeurIPS 2025 · similarity 0.86)
- Differentiable Structure Learning with Partial Orders (NeurIPS 2024 · similarity 0.85)
- Differentiable Structure Learning with Ancestral Constraints (ICML 2025 · similarity 0.85)
- Analytic DAG Constraints for Differentiable DAG Learning (ICLR 2025 · similarity 0.84)
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.