On the Role of Sparsity and DAG Constraints for Learning Linear DAGs
This addresses the challenge of scaling DAG structure learning for researchers in graphical models, though it appears incremental as it builds on prior continuous optimization formulations.
The paper tackles the problem of learning Directed Acyclic Graph (DAG) structures by showing that soft sparsity and DAG constraints can replace hard constraints, leading to an easier unconstrained optimization problem. The result is a method that handles thousands of nodes with high accuracy, validated through extensive experiments.
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.