Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method
This work addresses the challenge of efficient DAG learning for researchers in causal inference and machine learning, though it appears incremental as it builds on existing methods with specific relaxations.
The authors tackled the problem of learning directed acyclic graphs (DAGs) from Gaussian linear structural equation models by introducing a novel framework that uses a permutation matrix parameter and a relaxation technique to avoid NP-hard combinatorial issues, resulting in a method that recovers DAGs without expensive acyclicity checks or parent set enumeration.
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.