Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

Area of Science:

• Machine Learning
• Causal Inference
• Mathematical Optimization

Background:

• Learning directed acyclic graphs (DAGs) from data is computationally intensive due to the superexponential number of possible graph structures.
• Existing methods for learning optimal DAGs from continuous observational data face scalability challenges.

Purpose of the Study:

• To develop a more efficient mathematical programming model for learning optimal DAGs from continuous observational data.
• To incorporate a superstructure for reducing candidate DAGs within the optimization framework.

Main Methods:

• Formulated the DAG learning problem as a mathematical programming model.
• Proposed a new mixed-integer quadratic program: the layered network (LN) formulation.
• Utilized a negative log-likelihood score function with L1 and L2 penalties.

Main Results:

• The LN formulation provides a compact model with a tight continuous relaxation value.
• Computational results demonstrate superior performance compared to existing mathematical formulations.
• The LN formulation scales better than algorithms using only L1 regularization, especially with sparse superstructures.

Conclusions:

• The proposed LN formulation is an effective and computationally efficient approach for learning optimal DAGs.
• This method offers significant advantages in terms of speed and scalability for causal discovery tasks.
• The LN formulation advances the state-of-the-art in learning graphical models from observational data.