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

Abstract

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.

arXiv commentNeurIPS 2020. The code is available at https://github.com/ignavier/golem

References in corpus (12)

• Emergence of scaling in random networks
• Identifiability of Gaussian structural equation models with equal error variances
• DAGs with NO TEARS: Continuous Optimization for Structure Learning
• Causal Inference in the Presence of Latent Variables and Selection Bias
• DAG-GNN: DAG Structure Learning with Graph Neural Networks
• Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks
• ${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs
• Causal Discovery with Reinforcement Learning
• A Graph Autoencoder Approach to Causal Structure Learning
• A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed Cyclic Graphical Models
• On the Convergence of Continuous Constrained Optimization for Structure Learning
• Characterizing Distribution Equivalence and Structure Learning for Cyclic and Acyclic Directed Graphs

Cited by in corpus (11)

• CausPref: Causal Preference Learning for Out-of-Distribution Recommendation
• Causal Fourier Analysis on Directed Acyclic Graphs and Posets
• Estimation of Structural Causal Model via Sparsely Mixing Independent Component Analysis
• Data Generating Process to Evaluate Causal Discovery Techniques for Time Series Data
• Discovering Dynamic Causal Space for DAG Structure Learning
• Unsuitability of NOTEARS for Causal Graph Discovery
• Directed Acyclic Graphs With Tears
• Efficient Neural Causal Discovery without Acyclicity Constraints
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
• Deconfounded Score Method: Scoring DAGs with Dense Unobserved Confounding
• Fast Causal Discovery by Approximate Kernel-based Generalized Score Functions with Linear Computational Complexity