Algorithmic detectability threshold of the stochastic block model

The assumption that the values of model parameters are known or correctly learned, i.e., the Nishimori condition, is one of the requirements for the detectability analysis of the stochastic block model in statistical inference. In practice, however, there is no example demonstrating that we can know the model parameters beforehand, and there is no guarantee that the model parameters can be learned accurately. In this study, we consider the expectation–maximization (EM) algorithm with belief propagation (BP) and derive its algorithmic detectability threshold. Our analysis is not restricted to the community structure but includes general modular structures. Because the algorithm cannot always learn the planted model parameters correctly, the algorithmic detectability threshold is qualitatively different from the one with the Nishimori condition.

Figure 1

An instance of the labeled SBM with two modules. The red solid edges represent the edges with an assortative structure, and the gray dashed edges represent the edges with a disassortative structure.

Figure 2

(top) (a) Learning curves of the model parameters that indicate the strength of the modular structures. The vertical axis represents the total variation $\mathrm{\Delta }$ of the affinity matrix elements $c_{\sigma {\sigma }^{\prime }}$ from the mean value $\overline{\mathbf{c}}$. The horizontal axis represents the number of steps in the EM algorithm. We considered examples for the SBMs with a simple community structure (circles) and a bipartite structure (rectangles), as shown in the inset. To detect these structures, we did not use the affinity matrix restricted to Eq. (2); instead, we used the one with full degrees of freedom. (bottom) Second-order expansions of the right-hand side of Eq. (14) with the first moments (b) $〈{\xi }_{ij}〉=0$ and (c) $〈{\xi }_{ij}〉=0.2$ (gray curves). For the other parameters, we set $\mathrm{\Omega }=0.5$ and $〈{\xi }_{ij}^2〉=0.9$. The dashed line represents ${\widehat{x}}^{(t+1)}={\widehat{x}}^{\left(t\right)}$. The arrows in each figure show the update process of ${\widehat{x}}^{\left(t\right)}$ schematically.

Figure 3

Detectability phase-diagram of the two equally sized ($q=2$) labeled SBM with two types of edges ($p=2$). Each axis represents the normalized strength of the modular structure $x_{\alpha }$ ($\alpha \in \{1,2\}$). The center of the diagram represents the uniform random graph, while the edges of the diagram represent the strongly modular graphs. The size of the graph is $N=10000$. The average degree of each edge type is $c_1=3$ and $c_2=5$. The shaded region represents the undetectable region, i.e., the region where the inferred module assignments by the EM algorithm are uncorrelated to the planted assignments. The dashed ellipse represents the detectability threshold under the Nishimori condition. (The ellipse becomes a circle when the average degrees of both edge types are equal.) On the other hand, the shaded region represents the undetectable region of the EM algorithm, and its boundary is the algorithmic detectability threshold that we derived. The circles represent the phase boundary obtained by the numerical experiment; each point represents the average over five samples.

Figure 4

(Top) Trajectories of parameter learning based on the M-step of the EM algorithm for various planted values of $(x_1,x_2)$. This plot shows the upper-left region of the phase diagram shown in Fig. 3, and we consider the same labeled SBM as in Fig. 3. The arrows show the directions in which the estimated parameters move. (a) The trajectories of the estimates $({\widehat{x}}_1,{\widehat{x}}_2)$ for the case that the planted values $(x_1,x_2)$ (shown in open symbols) are in the detectable region. The trajectory for the graph with the planted value $(x_1,x_2)=(0.1,0.6)$ is represented by blue circles; $(x_1,x_2)=(0.45,0.8)$ is represented by yellow squares; $(x_1,x_2)=(0.45,0.9)$ is represented by red diamonds; and $(x_1,x_2)=(0.1,0.8)$ is represented by green triangles, respectively. In all cases, the initial estimate is set as $({\widehat{x}}_1,{\widehat{x}}_2)=(0.1,0.9)$. The dotted line represents the line with slope $-1$. (b) The trajectories of the estimates $({\widehat{x}}_1,{\widehat{x}}_2)$ in other cases. The trajectories with the planted values $(x_1,x_2)=(0.15,0.55)$ (red circles) and $(x_1,x_2)=(0.45,0.72)$ (cyan squares) are the cases in which the planted values (shown in open symbols) are in the undetectable region though the initial estimates are set as $({\widehat{x}}_1,{\widehat{x}}_2)=(0.1,0.9)$. The trajectories with the planted values $(x_1,x_2)=(0.1,0.6)$ (orange diamonds) and $(x_1,x_2)=(0.45,0.9)$ (purple triangles) are the cases in which $({\widehat{x}}_1,{\widehat{x}}_2)$ is initially located in the undetectable region $[({\widehat{x}}_1,{\widehat{x}}_2)=(0.45,0.55)]$, though the planted values are in the detectable region. (Bottom) Spectra of the weighted nonbacktracking matrix $B^{\prime }$ in the complex plane with $N=500$ corresponding to (i) $({\widehat{x}}_1,{\widehat{x}}_2)=(0.1,0.9)$, (ii) $({\widehat{x}}_1,{\widehat{x}}_2)=(0.323,0.677)$, and (iii) $({\widehat{x}}_1,{\widehat{x}}_2)=(0.1,0.6)$. The solid line (red) represents the circle with radius $|{\lambda }_b|$.

Figure 5

Behavior of the EM algorithm in the simple community structure with three modules. The average degree of each edge-type is $c_1=3$ and $c_2=5$. We consider two types of edges ($p=2$). (a) Second-order expansion of the right-hand side of Eq. (14) with $〈{\xi }_{ij}〉=0$; the dashed line represents ${\widehat{x}}^{(t+1)}={\widehat{x}}^{\left(t\right)}$. In the inset, $W$ matrix where $c_{\mathrm{in}}$ and $c_{\mathrm{out}}$ are represented by black and white, respectively. (b) Detectability phase-diagram. The dashed ellipse, shaded region, and circles represent the detectability threshold under the Nishimori condition, undetectable region of the EM algorithm, and results of the numerical experiments (the average is taken over five samples), respectively, as shown in Fig. 3. $(x_1,x_2)=(1/3,1/3)$ represents the point of the uniform random graph. (c) Trajectories of $({\widehat{x}}_1,{\widehat{x}}_2)$ with various initial values in the phase space. The trajectory for the graph with the planted value $(x_1,x_2)=(0.3,0.7)$ corresponds to the blue circles; $(x_1,x_2)=(0.9,0.4)$ corresponds to the yellow squares; $(x_1,x_2)=(0.8,0.2)$ corresponds to the red diamonds; and $(x_1,x_2)=(0.15,0.05)$ corresponds to the green triangles. As in Fig. 4, the planted values are shown by open symbols. The dashed lines represent the lines with slopes $-1/3$, 1, and $-3$. For the numerical experiments, we use the labeled SBMs with $N=15000$.

Figure 6

Behavior of the EM algorithm in a noncommunity structure with two modules. The average degree of each edge type is $c_1=3$ and $c_2=5$. (a) $W$ matrix where $c_{\mathrm{in}}$ and $c_{\mathrm{out}}$ are represented by black and white, respectively. We consider two types of edges ($p=2$). (b) Detectability phase diagram. The dashed ellipse, shaded region, and circles represent the detectability threshold under the Nishimori condition, undetectable region of the EM algorithm, and results of the numerical experiments (the average is taken over five samples), respectively, as in Fig. 3. $(x_1,x_2)=(1/2,1/2)$ represents the point of the uniform random graph. (c) Trajectories of ${\widehat{x}}_{\alpha }$ with various initial values in the phase space. The trajectory for the graph with the planted value $(x_1,x_2)=(0.4,0.9)$ corresponds to the blue circles; $(x_1,x_2)=(0.9,0.8)$ corresponds to the yellow squares; $(x_1,x_2)=(0.8,0.1)$ corresponds to the red diamonds; and $(x_1,x_2)=(0.35,0.1)$ corresponds to the green triangles. As in Fig. 4, the planted values are shown by open symbols. The dashed lines represent lines with slopes $-1$ and 1. For the numerical experiments, we use the labeled SBMs with $N=4000$.

Figure 7

(a) Same detectability phase-diagram as in Fig. 3. The striped region represents the undetectable region that becomes detectable when the edges of $\alpha =2$ are discarded. (b) Vertical histograms of the overlap distribution. The same labeled SBM as that in Fig. 7 is considered, and the instances with $N=10000$, $c_1=3$, and $(x_1,x_2)=(0.85,0.45)$ are generated. The histograms of various values of $c_2$ are horizontally aligned (30 samples for each histogram). The ones in the detectable phase, i.e., $c_2\le 2$, are indicated in blue, while the ones in the undetectable phase, i.e., $c_2\ge 3$, are in red. The white points (connected via dashed lines) indicate the medians of overlaps. The population of the success and failure changes at the critical value that we estimated.

Figure 8

Planted $W^{\alpha }$ matrices (two left panels) and evolution of the deviation from the uninformative module-assignment distribution (two right panels). In each $W^{\alpha }$ matrix, the colored elements represent $W_{\sigma {\sigma }^{\prime }}^{\alpha }=1$, and the white elements represent $W_{\sigma {\sigma }^{\prime }}^{\alpha }=0$. In the right panels, the mean value $〈{\xi }_{ij}^{\alpha }〉$ is represented as a white line, and its standard deviation $\mathrm{Std}\left[{\xi }_{ij}^{\alpha }\right]$ is shown as a colored tie. The top panels correspond to the example given in Sec. 7a, i.e., the simple community structure with $q=2$, and we set $(x_1,x_2)=(0.1,0.6)$ as the planted model parameters. The middle panels correspond to the example given in Sec. 7b, i.e., the simple community structure with $q=3$, and we set $(x_1,x_2)=(0.8,0.2)$ as the planted model parameters. The bottom panels correspond to the example given in Sec. 7c, i.e., the general structure of Fig. 6, and we set $(x_1,x_2)=(0.8,0.1)$ as the planted model parameters.