# On the Role of Sparsity and DAG Constraints for Learning Linear DAGs

arXiv: https://arxiv.org/abs/2006.10201 · HTML: https://mlsanity.com/paper/2006.10201/

## Key facts

- Cited by 191 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

## Built on by (most cited first, 30 of 191)

- [D'ya like DAGs? A Survey on Structure Learning and Causal Discovery](https://mlsanity.com/paper/2103.02582/) (2021)
- [Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game](https://mlsanity.com/paper/2102.13647/) (2021)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [DiBS: Differentiable Bayesian Structure Learning](https://mlsanity.com/paper/2105.11839/) (2021)
- [Deep End-to-end Causal Inference](https://mlsanity.com/paper/2202.02195/) (2022)
- [Efficient Neural Causal Discovery without Acyclicity Constraints](https://mlsanity.com/paper/2107.10483/) (2021)
- [BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery](https://mlsanity.com/paper/2112.02761/) (2021)
- [gCastle: A Python Toolbox for Causal Discovery](https://mlsanity.com/paper/2111.15155/) (2021)
- [DAGs with No Curl: An Efficient DAG Structure Learning Approach](https://mlsanity.com/paper/2106.07197/) (2021)
- [Unsuitability of NOTEARS for Causal Graph Discovery](https://mlsanity.com/paper/2104.05441/) (2021)
- [Large-Scale Differentiable Causal Discovery of Factor Graphs](https://mlsanity.com/paper/2206.07824/) (2022)
- [Fast Scalable and Accurate Discovery of DAGs Using the Best Order Score Search and Grow-Shrink Trees](https://mlsanity.com/paper/2310.17679/) (2023)
- [Structure Learning with Continuous Optimization: A Sober Look and Beyond](https://mlsanity.com/paper/2304.02146/) (2023)
- [Discovering Causal Relations and Equations from Data](https://mlsanity.com/paper/2305.13341/) (2023)
- [A Survey on Causal Discovery Methods for I.I.D. and Time Series Data](https://mlsanity.com/paper/2303.15027/) (2023)
- [NTS-NOTEARS: Learning Nonparametric DBNs With Prior Knowledge](https://mlsanity.com/paper/2109.04286/) (2021)
- [Causal Representation Learning Made Identifiable by Grouping of Observational Variables](https://mlsanity.com/paper/2310.15709/) (2023)
- [Towards Federated Bayesian Network Structure Learning with Continuous Optimization](https://mlsanity.com/paper/2110.09356/) (2021)
- [Stable Differentiable Causal Discovery](https://mlsanity.com/paper/2311.10263/) (2023)
- [Truncated Matrix Power Iteration for Differentiable DAG Learning](https://mlsanity.com/paper/2208.14571/) (2022)
- [Data Generating Process to Evaluate Causal Discovery Techniques for Time Series Data](https://mlsanity.com/paper/2104.08043/) (2021)
- [MissDAG: Causal Discovery in the Presence of Missing Data with Continuous Additive Noise Models](https://mlsanity.com/paper/2205.13869/) (2022)
- [Self-Compatibility: Evaluating Causal Discovery without Ground Truth](https://mlsanity.com/paper/2307.09552/) (2023)
- [NODAGS-Flow: Nonlinear Cyclic Causal Structure Learning](https://mlsanity.com/paper/2301.01849/) (2023)
- [Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions](https://mlsanity.com/paper/2201.05666/) (2022)
- [Hierarchical Graph Neural Networks for Causal Discovery and Root Cause Localization](https://mlsanity.com/paper/2302.01987/) (2023)
- [textttcausalAssembly: Generating Realistic Production Data for Benchmarking Causal Discovery](https://mlsanity.com/paper/2306.10816/) (2023)
- [FedDAG: Federated DAG Structure Learning](https://mlsanity.com/paper/2112.03555/) (2021)
- [CausPref: Causal Preference Learning for Out-of-Distribution Recommendation](https://mlsanity.com/paper/2202.03984/) (2022)
- [Optimizing NOTEARS Objectives via Topological Swaps](https://mlsanity.com/paper/2305.17277/) (2023)

## Abstract (arXiv)

Learning graphical structures based on Directed Acyclic Graphs (DAGs) is a challenging problem, partly owing to the large search space of possible graphs. A recent line of work formulates the structure learning problem as a continuous constrained optimization task using the least squares objective and an algebraic characterization of DAGs. However, the formulation requires a hard DAG constraint and may lead to optimization difficulties. In this paper, we study the asymptotic role of the sparsity and DAG constraints for learning DAG models in the linear Gaussian and non-Gaussian cases, and investigate their usefulness in the finite sample regime. Based on the theoretical results, we formulate a likelihood-based score function, and show that one only has to apply soft sparsity and DAG constraints to learn a DAG equivalent to the ground truth DAG. This leads to an unconstrained optimization problem that is much easier to solve. Using gradient-based optimization and GPU acceleration, our procedure can easily handle thousands of nodes while retaining a high accuracy. Extensive experiments validate the effectiveness of our proposed method and show that the DAG-penalized likelihood objective is indeed favorable over the least squares one with the hard DAG constraint.