Fast Mixing in Sparse Random Ising Models*

Motivated by the community detection problem in Bayesian inference, as well as the recent explosion of interest in spin glasses from statistical physics, we study the classical Glauber dynamics for sampling from Ising models with sparse random interactions. It is now well-known that when the in- teraction matrix has spectral diameter less than 1, Glauber dynamics mixes in near-linear time. Unfortunately, such criteria fail dramatically for interactions supported on arguably the most well-studied sparse random graph: the Erdos-Renyi random graph. There is a scarcity of positive results in this setting due to the presence of almost linearly many outlier eigenvalues of unbounded magnitude. We prove that for the Viana-Bray spin glass, where the interactions are supported on a random graph and randomly assigned signs, Glauber dynamics mixes in almost-linear time with high probability at sufficiently high temperatures, and we conjecture that our results are tight up to constants. We further extend our results to random graphs drawn according to the 2-community stochastic block model, as well as when the interactions are given by a “centered” version of the adjacency matrix. The latter setting is particularly relevant for the inference problem in community detection. Indeed, we build on this result to demonstrate that Glauber dynamics succeeds at recovering communities in the stochastic block model in a companion paper. The primary technical ingredient in our proof is showing that with high probability, a sparse random graph can be decomposed into two parts - a bulk which behaves like a graph with bounded maximum degree and a well-behaved spectrum, and a near- forest with favorable pseudorandom properties. We then use this decomposition to design a localization procedure that interpolates to simpler Ising models supported only on the near-forest, and then execute a pathwise analysis to establish a modified log- Sobolev inequality. The full version of this paper can be found on arXiv (arXiv ID: 2405.06616).