# ExDAG: an MIQP Algorithm for Learning DAGs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 50 references that are in the map.
- First posted on arXiv 21 Jun 2024.

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

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [DYNOTEARS: Structure Learning from Time-Series Data](https://mlsanity.com/paper/2002.00498/) (2020)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Interventional Causal Representation Learning](https://mlsanity.com/paper/2209.11924/) (2022)
- [Learning Linear Causal Representations from Interventions under General Nonlinear Mixing](https://mlsanity.com/paper/2306.02235/) (2023)
- [High-dimensional learning of linear causal networks via inverse covariance estimation](https://mlsanity.com/paper/1311.3492/) (2013)
- [A survey of Bayesian Network structure learning](https://mlsanity.com/paper/2109.11415/) (2021)
- [gCastle: A Python Toolbox for Causal Discovery](https://mlsanity.com/paper/2111.15155/) (2021)
- [DAGs with No Curl: An Efficient DAG Structure Learning Approach](https://mlsanity.com/paper/2106.07197/) (2021)
- [Fast Scalable and Accurate Discovery of DAGs Using the Best Order Score Search and Grow-Shrink Trees](https://mlsanity.com/paper/2310.17679/) (2023)
- [Causal Modeling with Stationary Diffusions](https://mlsanity.com/paper/2310.17405/) (2023)
- [Integer Programming for Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/2102.03129/) (2021)
- [Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression](https://mlsanity.com/paper/1511.08963/) (2015)
- [A Measure-Theoretic Axiomatisation of Causality](https://mlsanity.com/paper/2305.17139/) (2023)
- [Dagma-DCE: Interpretable, Non-Parametric Differentiable Causal Discovery](https://mlsanity.com/paper/2401.02930/) (2024)
- [Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models](https://mlsanity.com/paper/2404.12592/) (2024)
- [No penalty no tears: Least squares in high-dimensional linear models](https://mlsanity.com/paper/1506.02222/) (2015)

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

- [ExMAG: Learning of Maximally Ancestral Graphs](https://mlsanity.com/paper/2503.08245/) (2025)

## Abstract (arXiv)

There has been a growing interest in causal learning in recent years. Commonly used representations of causal structures, including Bayesian networks and structural equation models (SEM), take the form of directed acyclic graphs (DAGs). We provide a novel mixed-integer quadratic programming formulation and an associated algorithm that identifies DAGs with a low structural Hamming distance between the identified DAG and the ground truth, under identifiability assumptions. The eventual exact learning is guaranteed by the global convergence of the branch-and-bound-and-cut algorithm, which is utilized. In addition to this, integer programming techniques give us access to the dual bound, which allows for a real time assessment of the quality of solution. Previously, integer programming techniques have been shown to lead to limited scaling in the case of DAG identification due to the super exponential number of constraints, which prevent the formation of cycles. The algorithm proposed circumvents this by selectively generating only the violated constraints using the so-called "lazy" constraints methodology. Our empirical results show that ExDAG outperforms state-of-the-art solvers in terms of structural Hamming distance and F1 score when considering Gaussian noise on medium-sized graphs.