Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks
This provides a more efficient solution for statistical mechanics problems in sparse systems, which is incremental but offers specific improvements in accuracy and speed for researchers in physics and machine learning.
The paper tackles statistical mechanics problems on sparse graphs by extracting a Feedback Vertex Set to reduce system complexity and using neural networks to approximate Boltzmann distributions, achieving more accurate free energy estimates and faster performance than existing methods like belief-propagation and variational autoregressive networks on sparse spin glasses, random graphs, and real-world 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.