Integer Programming for Learning Directed Acyclic Graphs from Continuous Data
This work addresses the computational challenge of learning DAGs, which is important for causal inference and network analysis in fields like biology and social sciences, but it is incremental as it builds on prior mathematical programming approaches.
The paper tackles the problem of learning directed acyclic graphs (DAGs) from continuous observational data by proposing a new mixed-integer quadratic optimization model called the layered network formulation, which outperforms existing methods in computational time, especially with sparse super-structures.
Learning directed acyclic graphs (DAGs) from data is a challenging task both in theory and in practice, because the number of possible DAGs scales superexponentially with the number of nodes. In this paper, we study the problem of learning an optimal DAG from continuous observational data. We cast this problem in the form of a mathematical programming model which can naturally incorporate a super-structure in order to reduce the set of possible candidate DAGs. We use the penalized negative log-likelihood score function with both $\ell_0$ and $\ell_1$ regularizations and propose a new mixed-integer quadratic optimization (MIQO) model, referred to as a layered network (LN) formulation. The LN formulation is a compact model, which enjoys as tight an optimal continuous relaxation value as the stronger but larger formulations under a mild condition. Computational results indicate that the proposed formulation outperforms existing mathematical formulations and scales better than available algorithms that can solve the same problem with only $\ell_1$ regularization. In particular, the LN formulation clearly outperforms existing methods in terms of computational time needed to find an optimal DAG in the presence of a sparse super-structure.