Nonbacktracking operator for the Ising model and its applications in systems with multiple states

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.

Figure 1

Absolute value of the largest eigenvalue of the nonbacktracking operator, $|{\lambda }_1|$, as a function of $\beta$ for the SK model with $n=60$. Each point is averaged over 10 instances.

Figure 2

Spectrum (in the complex plane) of the nonbacktracking matrix of the Viana-Bray model on a graph with $n=500,c=3$. In (a), $\beta =0.7>{tanh}^{-1}\frac{1}{\sqrt{c}},p^{+}=0.5$, the system is in the spin-glass phase and in (b), $p^{+}=0.7$, the system is in the ferromagnetic phase.

Figure 3

Comparison of a binary pattern and one eigenvector of the nonbacktracking matrix. Red stars are components of the binary pattern and blue circles denote components of the eigenvector. Parameters are $n=100,\beta =0.02,P=3$, and $c=28$.

Figure 4

The spectrum (in the complex plane) of the nonbacktracking operator for a Hopfield network with $n=500,c=8$, and 3 patterns with $\beta =1.2$ (a) and 12 patterns with $\beta =2.5$ (b). In (a), 3 patterns are all memorized, and the overlap [Eq. (17)] for the three patterns obtained using there first three eigenvectors is $0.628,0.620$, and $0.448$. In (b), none of the patterns is memorized, and the system is in the spin-glass phase.

Figure 5

The largest eigenvalue and the edge of the bulk of a Hopfield network as a function of the fraction of edges removed from the network. Red lines denote random removal and blue lines denote our approach. In both random removal and our approach, the upper line represents the largest eigenvalue and the lower line represents the edge of the bulk, that is, the absolute value of the first complex eigenvalue. In this network $n=200,c=6,P=2$, and $\beta =1.2$.