Slow spin dynamics and self-sustained clusters in sparsely connected systems

To identify emerging microscopic structures in low-temperature spin glasses, we study self-sustained clusters (SSC) in spin models defined on sparse random graphs. A message-passing algorithm is developed to determine the probability of individual spins to belong to SSC. We then compare the predicted SSC associations with the dynamical properties of spins obtained from numerical simulations and show that SSC association identifies individual slow-evolving spins. Studies of Erdos-Renyi (ER) and random regular (RR) graphs show that spins belonging to SSC are more stable with respect to spin-flip fluctuations, as suggested by the analysis of fully connected models. Further analyses show that SSC association outperforms local fields in predicting the spin dynamics, specifically the group of slow- and fast-evolving spins in RR graphs, for a wide temperature range close to the spin-glass transition. This insight gives rise to a powerful approach for predicting individual spin dynamics from a single snapshot of an equilibrium spin configuration, namely from limited static information. It also implies that single-sample SSC association carries more information than local fields in describing the state of individual spins, when little information can be extracted from the system's topology.

Figure 1

A superfactor graph corresponding to the original graph at the bottom right of the figure. Each supervariable contains two variables of the original graph. For each node of the original graph $\mathcal{G}$ we have a superfactor and for each link we have a supervariable. All the variables ${\sigma }_{ik},\forall k\in \partial i$ are forced to be the same by the superfactors' constraint. The superfactor and original graphs share the same topology.

Figure 2

A toy model which comprises 38 spin variables. Unfrustrated links are marked in green and frustrated links in red. Positive $J$ and $s$ are denoted by solid lines and circles, respectively, while negatives $J$ and $s$ are denoted by dashed lines and circles, respectively. White nodes represents $p({\sigma }_i=1)=0$ and black $p({\sigma }_i=1)=1$; the gray region identifies nodes for which $p\left({\sigma }_i\right)>0.5$.

Figure 3

Scatter plot of $p_i^{+}$ and ${\rho }_i$ for dynamics on (a) a Erdos-Renyi graph of mean connectivity $c=6$ and (b) a random regular graph of connectivity $c=6$. A configuration is sampled at ${\beta }_1=5$ after $t_1={10}^4$ sweeps. As discussed in the text, from this configuration we ran 1000 simulations that we observed for $t_2=100$ Monte Carlo Sweeps (MCS), which can been used to compute ${\rho }_i$. The symbols $\{+,\mathtt{o},*,\mathtt{x},\text{and}\square \}$ refer to dynamics at ${\beta }_2=3,1,0.7,0.4,\text{and}0.1$, respectively. Spin-glass transition inverse temperatures are ${\beta }_6^{\mathrm{ER}}\sim 0.387$ and ${\beta }_6^{\mathrm{RR}}\sim 0.420$.

Figure 4

The AUC values for the ROC curves defined by Eq. (12), of cumulative flip rate by ranking spins according to their SSC marginal probabilities, obtained for (a) Erdos-Renyi graphs and (b) random regular graphs with $N=1000$ vertices and degree connectivity $c=6$, as a function of flipping inverse temperature ${\beta }_2$, with waiting time $t_1={10}^4$, sampling inverse temperature ${\beta }_1=5$, and flipping time $t_2=100$ over 200 trajectories. Each data point is averaged over 10 realizations of graph topologies. Inset: The ROC curves at different ${\beta }_2$ on (a) Erdos-Renyi graphs and (b) random regular graphs. The closer the sampling temperature ${\beta }_2$ is to the configuration temperature ${\beta }_1$ the more accurate is the SSC association is as a predictor of slow spin dynamics.

Figure 5

The AUC obtained on ER graphs with (a) $c=5$ and (b) $c=6$, and RR graphs with (c) $c=5$ and (d) $c=6$, with $N=1000$, waiting time $t_1={10}^4$, and flipping time $t_2=100$, at different sampling temperatures ${\beta }_1$ as a function of flipping temperatures ${\beta }_2$ over 200 trajectories. Each data point is averaged over 10 realizations of graph topologies.

Figure 6

Scatter plot of $p_i^{+}$ and ${\rho }_i$ for dynamics on an RR graph of connectivity equal to 5. A configuration is sampled at ${\beta }_1=5$ after (a) $t_1={10}^4$ sweeps and (b) $t_1={10}^6$ sweeps. As discussed in the text, from this configuration we ran 1000 simulations that we observed for 100 MCS, which can been used to compute ${\rho }_i$. The symbols $\{+,\mathtt{o},*,\mathtt{x},\text{and}\square \}$ refer to dynamics at ${\beta }_2=3,1,0.7,0.4,\text{and}0.1$, respectively. Inverse spin-glass temperature in this case is ${\beta }_{c=5}^{\mathrm{RR}}\sim 0.464$.

Figure 7

The AUC values obtained for random regular graphs with $N=1000$ and $c=5$, with ${\beta }_1=5$ and different waiting times $t_1$ in stage one, but the same flipping time $t_2=100$ in stage two. Inset: The AUC values with the same waiting time $t_1=10000$ in stage one but a different $t_2$ in stage two.

Figure 8

Scatter plot of $p_i^{+}$ and ${\rho }_i$ for the dynamics on an RR graph of connectivities (a) $c=3$ and (b) $c=4$. A configuration is sampled at ${\beta }_1=5$ after $t_1={10}^4$ sweeps. As discussed in the text, from this configuration we ran 1000 simulations that we observed for $t_2=100$ MCS, which can been used to compute ${\rho }_i$. The symbols $\{+,\mathtt{o},*,\mathtt{x},\text{and}\square \}$ refer to dynamics at ${\beta }_2=3,1,0.7,0.4,\text{and}0.1$, respectively. Spin-glass transition inverse temperatures are ${\beta }_{c=3}^{\mathrm{RR}}\sim 0.615$ and ${\beta }_{c=4}^{\mathrm{RR}}\sim 0.524$.

Figure 9

Scatter plot of $p_i^{+}$ and ${\rho }_i$ for the dynamics on an ER graph of mean connectivity 5. A configuration is sampled at ${\beta }_1=5$ after (a) $t_1={10}^4$ sweeps and (b) $t_1={10}^6$ sweeps. From this configuration we ran 1000 simulations that we observed for $t_2=100$ MCS to compute ${\rho }_i$. The symbols $\{+,\mathtt{o},*,\mathtt{x},\text{and}\square \}$ refer to dynamics at ${\beta }_2=3,1,0.7,0.4,\text{and}0.1$, respectively. Inverse spin-glass temperature in this case is ${\beta }_{c=5}^{\mathrm{ER}}\sim 0.420$.

Figure 10

Scatter plot of $p_i^{+}$ and ${\rho }_i$ for the dynamics on an ER graph of mean connectivity equal to 3. A configuration is sampled at ${\beta }_1=5$ after (a) $t_1={10}^4$ sweeps and (b) $t_1={10}^6$ sweeps. From this configuration we ran 1000 simulations that we observed for $t_2=100$ MCS to compute ${\rho }_i$. The symbols $\{+,\mathtt{o},*,\mathtt{x},\text{and}\square \}$ refer to dynamics at ${\beta }_2=3,1,0.7,0.4,\text{and}0.1$, respectively. Inverse spin-glass temperature in this case is ${\beta }_{c=3}^{\mathrm{ER}}\sim 0.523$.

Figure 11

Comparing the difference in values of (a) AUC, (b) KL divergence $D_{\mathrm{slow}}$ between the flip-rate distributions of slow spins (i.e., large-$p^{+}$ or large-field spins) and all spins, and (c) KL divergence $D_{\mathrm{fast}}$ between the flip-rate distributions of fast spins (i.e., small-$p^{+}$ or small-field spins) and all spins, obtained by the SSC-based prediction and local fields. The results are obtained for $t_1=10000$, $t_2=100$ on graphs with $N=1000$, and by setting ${\beta }_1={\beta }_2$. The data at ${\beta }_2=0.1$ are omitted since the AUC values $D_{\mathrm{slow}}$ and $D_{\mathrm{fast}}$ are very small in this case and result in large fluctuations in the fractional difference. Insets: The AUC and the two KL divergences $D_{\mathrm{slow}}$ and $D_{\mathrm{fast}}$ values in the case of RR graphs with $N=1000$ and $c=6$.

Figure 12

The original graph topology (left) specified by the tree $\mathcal{G}$ and corresponding factor graph for the SSC problem (right), which clearly include many small loops.