# Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 57 references that are in the map.
- First posted on arXiv 4 Jul 2021.

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

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Learning Sparse Nonparametric DAGs](https://mlsanity.com/paper/1909.13189/) (2019)
- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [High-dimensional learning of linear causal networks via inverse covariance estimation](https://mlsanity.com/paper/1311.3492/) (2013)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Concave Penalized Estimation of Sparse Gaussian Bayesian Networks](https://mlsanity.com/paper/1401.0852/) (2014)
- [Convex Relaxations for Permutation Problems](https://mlsanity.com/paper/1306.4805/) (2013)
- [Optimizing regularized Cholesky score for order-based learning of Bayesian networks](https://mlsanity.com/paper/1904.12360/) (2019)
- [Learning Local Dependence In Ordered Data](https://mlsanity.com/paper/1604.07451/) (2016)
- [High Dimensional Forecasting via Interpretable Vector Autoregression](https://mlsanity.com/paper/1412.5250/) (2014)

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

- [Permutation-based Inference for Variational Learning of Directed Acyclic Graphs](https://mlsanity.com/paper/2402.02644/) (2024)

## Abstract (arXiv)

We establish a novel framework for learning a directed acyclic graph (DAG) when data are generated from a Gaussian, linear structural equation model. It consists of two parts: (1) introduce a permutation matrix as a new parameter within a regularized Gaussian log-likelihood to represent variable ordering; and (2) given the ordering, estimate the DAG structure through sparse Cholesky factor of the inverse covariance matrix. For permutation matrix estimation, we propose a relaxation technique that avoids the NP-hard combinatorial problem of order estimation. Given an ordering, a sparse Cholesky factor is estimated using a cyclic coordinatewise descent algorithm which decouples row-wise. Our framework recovers DAGs without the need for an expensive verification of the acyclicity constraint or enumeration of possible parent sets. We establish numerical convergence of the algorithm, and consistency of the Cholesky factor estimator when the order of variables is known. Through several simulated and macro-economic datasets, we study the scope and performance of the proposed methodology.