Curved Markov Chain Monte Carlo for Network Learning

John Sigbeku, Emil Saucan, Anthea Monod

Abstract

We present a geometrically enhanced Markov chain Monte Carlo sampler for networks based on a discrete curvature measure defined on graphs. Specifically, we incorporate the concept of graph Forman curvature into sampling procedures on both the nodes and edges of a network explicitly, via the transition probability of the Markov chain, as well as implicitly, via the target stationary distribution, which gives a novel, curved Markov chain Monte Carlo approach to learning networks. We show that integrating curvature into the sampler results in faster convergence to a wide range of network statistics demonstrated on deterministic networks drawn from real-world data.
BibTeX
@inproceedings{sigbeku2021curved,
  author = {John Sigbeku and Emil Saucan and Anthea Monod},
  title = {{Curved Markov Chain Monte Carlo for Network Learning}},
  booktitle = {COMPLEX NETWORKS},
  year = {2021},
  doi = {10.1007/978-3-030-93413-2\_39},
}
Figure