Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method

Abstract

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.

References in corpus (13)

• Nearly unbiased variable selection under minimax concave penalty
• Lectures on 0/1-polytopes
• Extended Bayesian Information Criteria for Gaussian Graphical Models
• Estimating high-dimensional directed acyclic graphs with the PC-algorithm
• A simple approach for finding the globally optimal Bayesian network structure
• DAGs with NO TEARS: Continuous Optimization for Structure Learning
• ${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs
• High-dimensional learning of linear causal networks via inverse covariance estimation
• Optimizing regularized Cholesky score for order-based learning of Bayesian networks
• Learning Local Dependence In Ordered Data
• BigVAR: Tools for Modeling Sparse High-Dimensional Multivariate Time Series
• A Sampling Strategy for Projecting to Permutations in the Graph Matching Problem
• Approximating orthogonal matrices by permutation matrices