Solving Statistical Mechanics on Sparse Graphs with Feedback Set
  Variational Autoregressive Networks
  We propose a method for solving statistical mechanics problems defined on
sparse graphs. It extracts a small Feedback Vertex Set (FVS) from the sparse
graph, converting the sparse system to a much smaller system with many-body and
dense interactions with an effective energy on every configuration of the FVS,
then learns a variational distribution parameterized using neural networks to
approximate the original Boltzmann distribution. The method is able to estimate
free energy, compute observables, and generate unbiased samples via direct
sampling without auto-correlation. Extensive experiments show that our approach
is more accurate than existing approaches for sparse spin glasses. On random
graphs and real-world networks, our approach significantly outperforms the
standard methods for sparse systems such as the belief-propagation algorithm;
on structured sparse systems such as two-dimensional lattices our approach is
significantly faster and more accurate than recently proposed variational
autoregressive networks using convolution neural networks.
