Causal structure learning with momentum: Sampling distributions over
  Markov Equivalence Classes of DAGs
Moritz Schauer Marcel Wienöbst
In the context of inferring a Bayesian network structure (directed acyclic
graph, DAG for short), we devise a non-reversible continuous time Markov chain,
the "Causal Zig-Zag sampler", that targets a probability distribution over
classes of observationally equivalent (Markov equivalent) DAGs. The classes are
represented as completed partially directed acyclic graphs (CPDAGs). The
non-reversible Markov chain relies on the operators used in Chickering's Greedy
Equivalence Search (GES) and is endowed with a momentum variable, which
improves mixing significantly as we show empirically. The possible target
distributions include posterior distributions based on a prior over DAGs and a
Markov equivalent likelihood. We offer an efficient implementation wherein we
develop new algorithms for listing, counting, uniformly sampling, and applying
possible moves of the GES operators, all of which significantly improve upon
the state-of-the-art.