Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks

Abstract

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.

13 pages, 5 figures

References in corpus (12)

• Semi-Supervised Classification with Graph Convolutional Networks
• Cooperative Game Theory Approaches for Network Partitioning
• Expectation Propagation for approximate Bayesian inference
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Statistical physics of inference: Thresholds and algorithms
• Solving Statistical Mechanics Using Variational Autoregressive Networks
• Fast and simple decycling and dismantling of networks
• The Nishimori line and Bayesian Statistics
• Spin glass approach to the feedback vertex set problem
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Loop corrections in spin models through density consistency

Cited by in corpus (10)

• Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
• Tensor networks for unsupervised machine learning
• A Bayesian generative neural network framework for epidemic inference problems
• The autoregressive neural network architecture of the Boltzmann distribution of pairwise interacting spins systems
• Message Passing Variational Autoregressive Network for Solving Intractable Ising Models
• Sparse Autoregressive Neural Networks for Classical Spin Systems
• Efficient Optimization of Variational Autoregressive Networks with Natural Gradient
• A method for quantifying the generalization capabilities of generative models for solving Ising models
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• Integrating Neural Networks and Tensor Networks for Computing Free Energy