# Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models

arXiv: https://arxiv.org/abs/2404.12592 · HTML: https://mlsanity.com/paper/2404.12592/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 36 references that are in the map.
- First posted on arXiv 19 Apr 2024.

## Builds on (most cited first, 12 of 12)

- [Structure Learning in Graphical Modeling](https://mlsanity.com/paper/1606.02359/) (2016)
- [On Causal Discovery with Equal Variance Assumption](https://mlsanity.com/paper/1807.03419/) (2018)
- [Learning linear structural equation models in polynomial time and sample complexity](https://mlsanity.com/paper/1707.04673/) (2017)
- [Integer Programming for Learning Directed Acyclic Graphs from Continuous Data](https://mlsanity.com/paper/1904.10574/) (2019)
- [Bayesian Network Learning via Topological Order](https://mlsanity.com/paper/1701.05654/) (2017)
- [Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets, and Complexity](https://mlsanity.com/paper/1605.04071/) (2016)
- [Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks](https://mlsanity.com/paper/2005.14346/) (2020)
- [Ideal formulations for constrained convex optimization problems with indicator variables](https://mlsanity.com/paper/2007.00107/) (2020)
- [On the convex hull of convex quadratic optimization problems with indicators](https://mlsanity.com/paper/2201.00387/) (2022)
- [Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2307.09366/) (2023)
- [Certifiably Optimal Sparse Inverse Covariance Estimation](https://mlsanity.com/paper/1906.10283/) (2019)
- [Sparse PCA: A New Scalable Estimator Based On Integer Programming](https://mlsanity.com/paper/2109.11142/) (2021)

## Built on by (most cited first, 4 of 4)

- [ExDAG: an MIQP Algorithm for Learning DAGs](https://mlsanity.com/paper/2406.15229/) (2024)
- [An Asymptotically Optimal Coordinate Descent Algorithm for Learning Bayesian Networks from Gaussian Models](https://mlsanity.com/paper/2408.11977/) (2024)
- [ExDBN: Learning Dynamic Bayesian Networks using Extended Mixed-Integer Programming Formulations](https://mlsanity.com/paper/2410.16100/) (2024)
- [Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators](https://mlsanity.com/paper/2608.01385/) (2026)

## Abstract (arXiv)

We study the problem of learning directed acyclic graphs from continuous observational data, generated according to a linear Gaussian structural equation model. State-of-the-art structure learning methods for this setting have at least one of the following shortcomings: i) they cannot provide optimality guarantees and can suffer from learning sub-optimal models; ii) they rely on the stringent assumption that the noise is homoscedastic, and hence the underlying model is fully identifiable. We overcome these shortcomings and develop a computationally efficient mixed-integer programming framework for learning medium-sized problems that accounts for arbitrary heteroscedastic noise. We present an early stopping criterion under which we can terminate the branch-and-bound procedure to achieve an asymptotically optimal solution and establish the consistency of this approximate solution. In addition, we show via numerical experiments that our method outperforms state-of-the-art algorithms and is robust to noise heteroscedasticity, whereas the performance of some competing methods deteriorates under strong violations of the identifiability assumption. The software implementation of our method is available as the Python package micodag.