Crossing the KS threshold in the stochastic block model with information theory

The stochastic block model (SBM) is a canonical model of network with communities. The terminology SBM comes from the machine learning and statistics literature [1], while the model is typically called the planted partition model in theoretical computer science [2], [3], and the inhomogeneous random graphs model in the mathematical literature [4]. Although the model was defined as far back as the 80s, it resurged in the recent years due in part to the following fascinating conjecture established in [5] (and backed in [10]) from deep but non-rigorous statistical physics arguments:

We have recently prove part (i) of this conjecture in [6], and this paper shows that for $k=5$, it is indeed possible to cross the KS threshold using information theory in the disassortative case. For part (i), i.e., achieving the KS threshold efficiently, [6] relies on a linearized version of BP that can handle cycles and runs in $O(n\log n)$ time. This approach is related to spectral methods based on non -backtracking operators [7].

To cross the KS threshold information-theoretically, we rely on a non-efficient algorithm that samples a typical clustering. Upon observing a graph drawn from the SBM, the algorithm builds the set of all partitions of the $n$ nodes that have a typical fraction of edges inside and across clusters, and then samples a partition uniformly at random in that set. Our analysis of this algorithm reveals two different regimes, that reflect two layers of refinement in the bounds on the typical set's size. In a first regime, bad clusterings (i.e., partitions of the nodes that agree in no more than close to $1/k$ vertices) are with high probability not typical using a union-bound, and the algorithm samples only good clusterings with high probability. This allows to cross the KS threshold at $a=0$, and shows in this case that detection is information-theoretically solvable if $b > ck\ln k+o_{k}(1), c\in[1,2]$. Thus the gap between the information-theoretic and KS threshold can be large, since the KS threshold reads $b > k(k-1)$. However, the union bound does not allow to recover the correct bound at $b=0$. For $b=0$, previous analysis leads to a bound given by $a > 2k$, which is suboptimal. In fact, as soon as $a > k$, each cluster in the SBM graph has a giant component of linear size, and thus an algorithm that simply separates these components and randomly assigned the remaining vertices will detect the communities. Of course, such an algorithm only applies to the strict case of $b=0$. To obtain a tighter bound in the general case, we next exploit the large number of tree-like components that in the SBM graph, reaching a regime where some bad clusterings are typical but unlikely to be sampled. This shows that the algorithm succeed with the right bound¹ at $b=0$, i.e., $a > k$.

The SBM can be defined with a uniform or Binomial model for the communities. This means that for a probability vector $p=(p_{1},\,\, \ldots,p_{k})$, the communities may be drawn uniformly at random among all partitions of $n$ having $np_{i}$ vertices in community $i$ (with an arbitrary rounding rule on $np_{i}$ to obtain integers adding up to $n)$, or each vertex may be assigned a label in $[k]$ independently with probability $p$. These are equivalent for the purpose of this paper, due to standard concentration argument. In the case where $p=(1/k,\,\, \ldots,\,\, 1/k)$, we say that the communities are balanced.

Note that if $\hat{X}$ is a randomized algorithm (i.e., it takes the graph as an input and outputs various clusterings with different probabilities), and if for some $\varepsilon > 0,\mathbb{P}_{X,G,\hat{X}}\left\{\hat{X}(G)\in B_{\varepsilon}(X)\right\}=o_{n}(1)$ then detection is solvable (information-theoretically).

We next present the algorithm used to detect below the KS threshold.

Typicality Sampling Algorithm

Given an n-vertex graph $g$ and $\delta > 0$, the algorithm draws $\hat{x}_{\mathrm{typ}}(g)$ uniformly at random in $T_{\delta}(g)=\{x\in$ Balanced $(n,\,\, k)$:

$$\begin{equation*}\begin{split} &\sum_{i=1}^{k}\vert \{g_{u,v}\,\,: \,\, (u,\,\, v)\in\begin{pmatrix} [n]\\ 2 \end{pmatrix}\,\, \mathrm{s}.\mathrm{t}.\,\, x_{u}=i,\,\, x_{v}=i\}\vert \\ &\qquad \geq\frac{an}{2k}(1-\delta),\\ &\sum_{i,j\in[k], i < j} \vert \{g_{u,v}\,\,: \,\, (u,\,\, v)\in\begin{pmatrix} [n]\\ 2 \end{pmatrix}\,\, \mathrm{s}.\mathrm{t}.\,\, x_{u}=i,\,\, x_{v}=j\}\vert\\ &\qquad \leq\frac{bn(k-1)}{2k}(1+\delta)\} \end{split}\end{equation*}$$ View Source\begin{equation*}\begin{split} &\sum_{i=1}^{k}\vert \{g_{u,v}\,\,: \,\, (u,\,\, v)\in\begin{pmatrix} [n]\\ 2 \end{pmatrix}\,\, \mathrm{s}.\mathrm{t}.\,\, x_{u}=i,\,\, x_{v}=i\}\vert \\ &\qquad \geq\frac{an}{2k}(1-\delta),\\ &\sum_{i,j\in[k], i < j} \vert \{g_{u,v}\,\,: \,\, (u,\,\, v)\in\begin{pmatrix} [n]\\ 2 \end{pmatrix}\,\, \mathrm{s}.\mathrm{t}.\,\, x_{u}=i,\,\, x_{v}=j\}\vert\\ &\qquad \leq\frac{bn(k-1)}{2k}(1+\delta)\} \end{split}\end{equation*} if the SBM is assortative $(\mathrm{i}.\mathrm{e}.,\,\, a\geq b)$, otherwise flip the direction of the above two inequalities.

Theorem 1

Let $d:=\frac{a+(k-1)b}{k}$, assume $d > 1$, and let $\tau=\tau_{d}$ be the unique solution in $(0,1)$ of $\tau e^{-\tau}=de^{-d}$, i.e., $\tau:=\sum_{j=1}^{+\infty}\frac{j^{j-1}}{j!}(de^{-d})^{j}$. The Typicality Sampling Algorithm detects² communities in SBM $(n,\,\, k,\,\, a,\,\, b)$ if

$$\begin{align*}&\frac{1}{2\ln k}\left(\frac{a\ln a+(k-1)b\ln b}{k}-d\ln d\right)\\ &\qquad > 1-\frac{\tau}{d}\left(1-\frac{\tau}{2}\right). \tag{1}\end{align*}$$ View Source\begin{align*}&\frac{1}{2\ln k}\left(\frac{a\ln a+(k-1)b\ln b}{k}-d\ln d\right)\\ &\qquad > 1-\frac{\tau}{d}\left(1-\frac{\tau}{2}\right). \tag{1}\end{align*}

Remark 1

Define $d(\tau,\,\, d)=1-\frac{\tau}{d}(1-\frac{\tau}{2})$. Note that since $d(\tau,\,\, d) < 1$ when $d > 1$ (which is needed for the presence of the giant), detection is already solvable in SBM $(n,\,\, k,\,\, a,\,\, b)$ if

$$\begin{equation*}\frac{1}{2\ln k}\left(\frac{a\ln a+(k-1)b\ln b}{k}-d\ln d\right) > 1. \tag{2}\end{equation*}$$ View Source\begin{equation*}\frac{1}{2\ln k}\left(\frac{a\ln a+(k-1)b\ln b}{k}-d\ln d\right) > 1. \tag{2}\end{equation*}

The above corresponds to the regime where there is not bad clustering that is typical with high probability. However, the above bound is not tight in the extreme regime of $b=0$, since it reads $a > 2k$ as opposed to $a > k$ (the presence of a giant).

Defining $a_{k}(b)$ as the solution in $a$ of $\frac{1}{2\ln k}\left(\frac{a\ln a+(k-1)b\ln b}{k}-d\ln d\right)= d(\tau,\,\, d)$ and expanding the bound in Theorem 1 gives the following.

Corollary 1

Detection is solvable

$$\begin{align*}&in\,\, \mathrm{SBM}(n,\,\, k,\,\, 0,\,\, b)\,\, if\,\, b > \frac{2k\ln k}{(k-1)\ln\frac{k}{k-1}}g(\tau,\,\, \frac{b(k-1)}{k})\tag{3}\\ &in\,\, \mathrm{SBM}(n,\,\, k,\,\, a,\,\, b)\,\, if\,\, a > k+\Delta_{k}(b), \tag{4}\end{align*}$$ View Source\begin{align*}&in\,\, \mathrm{SBM}(n,\,\, k,\,\, 0,\,\, b)\,\, if\,\, b > \frac{2k\ln k}{(k-1)\ln\frac{k}{k-1}}g(\tau,\,\, \frac{b(k-1)}{k})\tag{3}\\ &in\,\, \mathrm{SBM}(n,\,\, k,\,\, a,\,\, b)\,\, if\,\, a > k+\Delta_{k}(b), \tag{4}\end{align*} where (3) is strictly stronger than the KS threshold at $k=5$, and where $\Delta_{k}(b):=a_{k}(b)-k$ is such that $\Delta_{k}(0)=0$.

Remark 2

Note that (4) approaches the optimal bound given by the presence of the giant at $b=0$. Note also that (3) improves significantly on the KS threshold given by $b > k(k-1)$ at $a=0$. By continuity arguments, we can also cross the KS threshold for some positive values of $a$ at $k=5$.

Remark 3

We further claim that the scaling in $k$ of our IT threshold is correct $a=0$. To see this, consider $v\in G, b=(1-\epsilon)k\ln(k)$, and assume that we know the communities of all vertices more than $r=\ln(\ln(n))$ edges away from $v$. For each vertex $r$ edges away from $v$, there will be approximately $k^{\epsilon}$ communities that it has no neighbors in. Then vertices $r-1$ edges away from $v$ have approximately $k^{\epsilon}\ln(k)$ neighbors that are potentially in each community, with approximately $\ln(k)$ fewer neighbors suspected of being in its community than in the average other community. At that point, the noise has mostly drowned out the signal and our confidence that we know anything about the vertices' communities continues to degrade with each successive step towards $v$. A different approach is developed in [15].

A first question is to estimate the likelihood that a bad clustering, i.e., one that has an overlap that is close to $1/k$, belongs to the typical set. This means the probability that a clustering which splits each of the true cluster into $k$ groups belonging to each community still manages to keep the right proportions of edges inside and across the clusters. This is unlixely to take place, but we care about the exponent of this rare event probability.

Fig. 1:

A bad clustering roughly splits each community equally among the $k$ communities. Each pair of nodes connects with probability $a/n$ among vertices of same communities (i.e., same color groups, plain line connections), and $b/n$ across communities (i.e., different color groups, dashed line connections). Only some connections are displayed in the figure to ease the visualization.

View All

As illustrated in Figure 1, the number of edges that are contained in the clusters of a bad clustering is roughly distributed as the sum of two Binomial random variables,

View Source\begin{equation*} E_{\mathrm{in}}\dot{\sim} \mathrm{Bin}\left(\frac{n^{2}}{2k^{2}}, \frac{a}{n}\right)+\mathrm{Bin}\left(\frac{(k-1)n^{2}}{2k^{2}}, \frac{b}{n}\right),\end{equation*}

$$\begin{equation*} E_{\mathrm{out}}\dot{\sim} \mathrm{Bin}\left(\frac{n^{2}(k-1)}{2k^{2}}, \frac{a}{n}\right)+\mathrm{Bin}\left(\frac{n^{2}(k-1)^{2}}{2k^{2}}, \frac{b}{n}\right),\end{equation*}$$ View Source\begin{equation*} E_{\mathrm{out}}\dot{\sim} \mathrm{Bin}\left(\frac{n^{2}(k-1)}{2k^{2}}, \frac{a}{n}\right)+\mathrm{Bin}\left(\frac{n^{2}(k-1)^{2}}{2k^{2}}, \frac{b}{n}\right),\end{equation*}

Thus, we need to estimate the rare event that the Binomial sum deviates from its expectations. While there is a large list of bounds on Binomial tail events, the number of trials here is quadratic in $n$ and the success bias decays linearly in $n$, which require particular care to ensure tight bounds. We derive these in [6], obtaining that for a bad clustering $x$,

View Source\begin{equation*}\mathbb{P}\{x\,\, \mathrm{is\, typical}\} \approx\exp\left(-\frac{n}{k}A\right)\end{equation*}

$$\begin{equation*}\begin{split} &A:=\\ &\frac{a+b(k-1)}{2}\ln\frac{k}{a+(k-1)b}+\frac{a}{2}\ln a+\frac{b(k-1)}{2}\ln b. \end{split}\end{equation*}$$ View Source\begin{equation*}\begin{split} &A:=\\ &\frac{a+b(k-1)}{2}\ln\frac{k}{a+(k-1)b}+\frac{a}{2}\ln a+\frac{b(k-1)}{2}\ln b. \end{split}\end{equation*}

One can then use a union bound, since there are at most $k^{n}$ bad clusterings, to obtain a first regime where no clustering is typical with high probability. This already allows to cross the KS threshold in some regime of the parameters when $k\geq 5$. However, this does not interpolate the correct behavior of the information-theoretic bound in the extreme regime of $b=0$. In fact, for $b=0$, the union bound requires $a > 2k$ to imply no bad typical clustering with high probability, whereas as soon as $a > k$, an algorithm that simply separates the two giants in SBM $(n,\,\, k,\,\, a,\,\, 0)$ and assigns communities uniformly at random for the other vertices solves detection. Thus when $a\in(k,\,\, 2k]$, the union bound is loose. To remediate to this, we next take into account the topology of the SBM graph.

Since the algorithm samples a typical clustering, we only need the number of bad and typical clusterings to be small compared to the total number of typical clusterings, in expectation. Thus, we seek to better estimate the total number of typical clusterings. The main topological property of the SBM graph that we exploit is the large fraction of nodes that are in tree-like components outside of the giant. Conditioned on being on a tree, the SBM labels are distributed as in a broadcasting problem on a (Galton-Watson) tree. Specifically, for a uniformly drawn root node $X$, each edge in the tree acts as a k-ary symmetric channel. Thus, labelling the nodes in the trees according to the above distribution and freezing the giant to the correct labels leads to a typical clustering with high probability.

Fig. 2:

Illustration of the topology of SBM $(n,\,\, k,\,\, a,\,\, b)$ for $k=2$. A giant component covering the two communities takes place when $d=\frac{a+(k-1)b}{k} > 1$; a linear fraction of vertices belong to isolated trees (including isolate vertices). To estimate the size of the typical set: sample a bit uniformly at random in each isolated tree (green vertices) and propagate the bit according to the symmetric channel with flip probability $b/(a+(k-1)b)$ (plain edges do not flip whereas dashed edges flip).

View All

We hence need to count the number of nodes $T$ and edges $M$ that belong to such trees in the SBM graph. This is done in a series of lemmas in our arxiv paper [6], and requires combinatorial estimates similar to those carried for the Erdos-Renyi case [16]. The fractions are shown to concentrate around

View Source\begin{align*}&T/n\approx\frac{\tau}{d}\left(1-\frac{\tau}{2}\right),\tag{5}\\ &M/n\approx\frac{\tau^{2}}{2d}, \tag{6}\end{align*}

III.

Theorem 2

Let $T_{\delta}(G)$ denote the typical set for $G$ drawn under SBM $(n,\,\, k,\,\, a,\,\, b)$. Then, for any $\varepsilon > 0$,

$$\begin{equation*}\mathbb{P}\{\vert T_{\delta}(G)\vert < k^{(\psi-\varepsilon)n}\}=o(1),\end{equation*}$$ View Source\begin{equation*}\mathbb{P}\{\vert T_{\delta}(G)\vert < k^{(\psi-\varepsilon)n}\}=o(1),\end{equation*} where $$\begin{equation*}\begin{split} &\psi:=\frac{\tau}{d}\left(1-\frac{\tau}{2}\right)+\frac{\tau^{2}}{2d\ln k}H(\nu),\\ &\nu:=\left(\frac{a}{a+(k-1)b}, \frac{b}{a+(k-1)b},\ldots, \frac{b}{a+(k-1)b}\right) \end{split}\end{equation*}$$ View Source\begin{equation*}\begin{split} &\psi:=\frac{\tau}{d}\left(1-\frac{\tau}{2}\right)+\frac{\tau^{2}}{2d\ln k}H(\nu),\\ &\nu:=\left(\frac{a}{a+(k-1)b}, \frac{b}{a+(k-1)b},\ldots, \frac{b}{a+(k-1)b}\right) \end{split}\end{equation*} and $H(\cdot)$ is the entropy in nats.

Note that the above gives the induced label-distribution on trees in SBM $(n,\,\, k,\,\, a,\,\, b)$, with possibly a global flip for the isolated trees. Thus, with high probability on $G$, as $T$ and $M$ grow (linearly) with $n$, this assignment is typical with high probability on $U_{1}^{T}, Z_{1}^{M}$:

View Source\begin{equation*}\mathbb{P}_{U_{1}^{T},Z_{1}^{R}}\{\hat{X}(U_{1}^{T},\,\, Z_{1}^{M})\in T_{\delta}(G)\}=1-\mathrm{o}(1). \tag{7}\end{equation*}

Denote by $A_{\varepsilon,M}(\nu)$ the $\varepsilon$ -typical set for sequences of length $M$ under the distribution $\eta$ on $[k]$ (as defined in [17] $)$. Define similarly $A_{\varepsilon,T}(\eta)$ for the uniform distribution $\eta$ on $k$. By the AEP theorem, for any $\varepsilon > 0$,

View Source\begin{equation*}\mathbb{P}\{U_{1}^{T}\in A_{\varepsilon,T}(\eta),\,\, Z_{1}^{M}\in A_{\varepsilon,M}(\nu)\}\rightarrow 1.\end{equation*}

Therefore,

View Source\begin{equation*}\begin{split} &\mathbb{P}_{U_{1}^{T},Z_{1}^{R}}\{\hat{X}(U_{1}^{T},\,\, Z_{1}^{M})\in T_{\delta}(G)\}\\ &\leq \sum_{u_{1}^{T}\in A_{\varepsilon,T}(\eta),z_{1}^{R}\in A_{\varepsilon,M}(\nu)}\\ &1(\hat{X}(u_{1}^{T},\,\, z_{1}^{M})\in T_{\delta}(G))k^{-T}k^{-M(H(\nu)-\varepsilon)}+o(1). \end{split}\end{equation*}

Since the right hand side counts a subset of the typical clusterings, we have with high probability on $G$,

View Source\begin{equation*}\vert T_{\delta}(G)\vert \geq(1-o(1))k^{T+M(H(\nu)-\varepsilon)}.\end{equation*}

Further, from the topological lemmas derived in our arxiv paper [6], for $\varepsilon > 0$, with high probability on $G$,

View Source\begin{equation*}\begin{split} &T\in\left[\frac{\tau}{d}\left(1-\frac{\tau}{2}\right)-\varepsilon, \frac{\tau}{d}\left(1-\frac{\tau}{2}\right)+\varepsilon\right],\\ &M\in\left[\frac{\tau^{2}}{2d}-\varepsilon, \frac{\tau^{2}}{2d}+\varepsilon\right]. \end{split}\end{equation*}

The claims follows from algebraic manipulations. $\blacksquare$