Integer programming for learning directed acyclic graphs from nonidentifiable Gaussian models

Area of Science:

• Machine Learning
• Causal Inference
• Graph Theory

Background:

• Learning directed acyclic graphs (DAGs) from observational data is crucial for causal inference.
• Current methods often lack optimality guarantees or assume homoscedastic noise, limiting their applicability.
• These limitations hinder accurate model identification and can lead to suboptimal structure learning.

Purpose of the Study:

• To develop a robust and computationally efficient framework for learning DAGs from continuous observational data.
• To address the shortcomings of existing methods, particularly regarding optimality guarantees and noise assumptions.
• To provide a method that accounts for arbitrary heteroscedastic noise.

Main Methods:

• A mixed-integer programming framework was developed for learning DAGs.
• The method incorporates arbitrary heteroscedastic noise, a significant improvement over homoscedastic assumptions.
• An early stopping criterion for the branch-and-bound procedure was introduced to achieve asymptotically optimal solutions.

Main Results:

• The proposed framework demonstrates superior performance compared to state-of-the-art algorithms in numerical experiments.
• The method is robust to noise heteroscedasticity, unlike competing approaches whose performance degrades.
• The consistency of the approximate solution obtained via the early stopping criterion is established.

Conclusions:

• The developed mixed-integer programming framework offers an efficient and accurate approach for learning DAGs from continuous data.
• The method overcomes key limitations of existing techniques, providing optimality guarantees and handling complex noise structures.
• The availability of the micodag Python package facilitates the application of this advanced structure learning technique.