Robustness and stability of spin-glass ground states to perturbed interactions

Across many problems in science and engineering, it is important to consider how much the output of a given system changes due to perturbations of the input. Here, we investigate the glassy phase of $\pm J$ spin glasses at zero temperature by calculating the robustness of the ground states to flips in the sign of single interactions. For random graphs and the Sherrington-Kirkpatrick model, we find relatively large sets of bond configurations that generate the same ground state. These sets can themselves be analyzed as subgraphs of the interaction domain, and we compute many of their topological properties. In particular, we find that the robustness, equivalent to the average degree, of these subgraphs is much higher than one would expect from a random model. Most notably, it scales in the same logarithmic way with the size of the subgraph as has been found in genotype-phenotype maps for RNA secondary structure folding, protein quaternary structure, gene regulatory networks, as well as for models for genetic programming. The similarity between these disparate systems suggests that this scaling may have a more universal origin.

Figure 1

$G(V,E)$ for (a) and (b) two representative examples of random graphs and (c) and (d) two representative examples of complete graphs (Sherrington-Kirkpatrick model). Each Ising spin $s_i$ is placed on a vertex, and each interaction $J_{ij}$ is placed on an edge. Each spin also experiences an external random field $h_i$.

Figure 2

Linear-linear plot of robustness ${\rho }_s$ versus normalized neutral set size $|U_s|/2^{\left|E\right|}$ for representative random graphs (a) and (b) and representative SK models (c) and (d). The dashed curve arises from the linear least-squares fit calculated for data on a linear-log scale (see also Fig. 3). The data are consistent with a logarithmic relationship between robustness and NSS. The plot window is adjusted to ensure that plot points for all neutral networks are within the viewing window.

Figure 3

Linear-log plot of robustness ${\rho }_s$ versus normalized neutral set size $|U_s|/2^{\left|E\right|}$ for representative random graphs (a) and (b) and representative SK models (c) and (d). The dashed line is the line of best of fit in the linear-log scale. The data are consistent with a linear relationship between robustness and the log of NSS. Regression means and 95% confidence intervals are given for the slope of the best fit lines. The dotted line shows the random null expectation for robustness. The plot window is adjusted to ensure that plot points for all neutral networks are within the viewing window.

Figure 4

Transition probability ${\varphi }_{rs}$ (for $r\ne s$ versus normalized neutral set size $|U_s|/2^{\left|E\right|}$ for the largest neutral network $s$ of representative random graphs (a) and (b) and representative SK models (c) and (d). The transition probability ${\varphi }_{rs}$ is, starting with a bond configuration that maps to ground state $s$, the probability that a single bond perturbation would now cause a change to ground state $r$, with $r\ne s$. To see the $r\ne s$ transition probabilities compared to the $r=s$ case, see the Supplemental Material [50]. Here, the dashed line is the line of best of fit in the linear-log scale; the dotted line is the identity line (in which abscissa = ordinate). In (d), for the SK model, the line of best fit deviates most from the identity line (which is outside the viewing area), but the data are consistent with a linear fit, as for the other models. Regression means and 95% confidence intervals are given for the slope of the best fit lines.

Figure 5

Plot of normalized induced subgraph size ${log}_{10}\left(\right|U_s|/2^{\left|E\right|})$ (equivalent to the NSS or frequency) versus the rank of the size for (a) and (b) random graphs and (c) and (d) SK models. All the models exhibit a similar rapid decay of the neutral set size.

Figure 6

Results for 1D Edwards-Anderson model: (a) Graph representation of the 1D Edwards-Anderson model with $\left|V\right|=11$, (b) neutral set size versus rank plot on log-log scale, (c) degree distribution of neutral set vertices, and (d) robustness ${\rho }_s$ versus log of the normalized neutral set size $|U_s|/2^{\left|E\right|}$. The dashed line is the analytical result from Eq. (8).