Variational DAG Estimation via State Augmentation With Stochastic
  Permutations
Edwin V. Bonilla Pantelis Elinas He Zhao Maurizio Filippone Vassili Kitsios Terry O'Kane
Estimating the structure of a Bayesian network, in the form of a directed
acyclic graph (DAG), from observational data is a statistically and
computationally hard problem with essential applications in areas such as
causal discovery. Bayesian approaches are a promising direction for solving
this task, as they allow for uncertainty quantification and deal with
well-known identifiability issues. From a probabilistic inference perspective,
the main challenges are (i) representing distributions over graphs that satisfy
the DAG constraint and (ii) estimating a posterior over the underlying
combinatorial space. We propose an approach that addresses these challenges by
formulating a joint distribution on an augmented space of DAGs and
permutations. We carry out posterior estimation via variational inference,
where we exploit continuous relaxations of discrete distributions. We show that
our approach can outperform competitive Bayesian and non-Bayesian benchmarks on
a range of synthetic and real datasets.