title: Nonbacktracking operator for the Ising model and its applications in systems with multiple states.
abstract: The nonbacktracking operator for a graph is the adjacency matrix defined on directed edges of the graph. The operator was recently shown to perform optimally in spectral clustering in sparse synthetic graphs and have a deep connection to belief propagation algorithm. In this paper we consider nonbacktracking operator for Ising model on a general graph with a general coupling distribution and study the spectrum of this operator analytically. We show that spectral algorithms based on this operator is equivalent to belief propagation algorithm linearized at the paramagnetic fixed point and recovers replica-symmetry results on phase boundaries obtained by replica methods. This operator can be applied directly to systems with multiple states like Hopfield model. We show that spectrum of the operator can be used to determine number of patterns that stored successfully in the network, and the associated eigenvectors can be used to retrieve all the patterns simultaneously. We also give an example on how to control the Hopfield model, i.e., making network more sparse while keeping patterns stable, using the nonbacktracking operator and matrix perturbation theory.
authors.affiliation: Santa Fe Institute, Santa Fe, New Mexico 87501, USA and State Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China.
authors.forename: Pan
authors.initials: P
authors.lastname: Zhang