The Stochastic Block Model Has the Overlap Graph Property for Modularity

Modularity maximisation [28, 29] is one of the main methods used for finding clusters and communities in networks. Modularity maximisation is NP-hard [8]; in practice, modularity has a complex landscape, and there are many high scoring solutions [18]. On the other hand, one major advantage of modularity is that its local updates are easy to compute. Naturally, local updates form the initial phase in the go-to algorithms for modularity maximisation: the Louvain algorithm [6] and its improved version, the Leiden algorithm [34]. However, as already observed in [6], algorithms based on local updates get trapped in a local maximum. To avoid this, both Louvain and Leiden include an additional non-local phase. An alternative approach, proposed by Wang and Kolter [35] via the Locale algorithm, escapes local maxima by replacing the local update with low-cardinality embedding.

Given the abundance of applications of modularity maximisation and Louvain and Leiden algorithms, theoretical understanding of modularity–based algorithms is surprisingly scarce. Cohen-Addad et al. [10] proved that in the Stochastic Block Model (SBM) with sufficient signal and two equal-sized blocks, a local algorithm, very similar to the local phase of Louvain, initiated on a random bisection, recovers the correct partition with high probability. See Section 6 for further discussion including how this relates to our result.

The question remains whether local updates lead to a global optimum in this random model with more than two communities or different initialisation. In this work, we answer this question negatively. Specifically, we establish that in SBM with $k\ge 3$ blocks, modularity exhibits the overlap gap property (OGP). The OGP is a statement of the geometry of near-optimal solutions and is considered a signature of algorithmic hardness – see Definition 2.1. Indeed, for many problems known to exhibit a computational-statistical gap, the threshold for OGP coincides with the conjectured algorithmic threshold [15, 16]. The idea has origins in statistical physics, and can be used to prove failure of greedy and Markov Chain Monte Carlo algorithms in average case problems. We show OGP in a planted random model as in [17, 14], though the theory is usually applied to optimisation problems in null models [15].

The practical implication of this result is that in networks with more than two communities, the local updates of Louvain or Leiden can get stuck in a local maximum even for a random graph model with clear communities. The same holds for other algorithms based on local updates. For example, Gösgens et al. [19] offer a new interpretation of modularity as an angular distance in a high-dimensional hypersphere, thus establishing equivalence of modularity maximisation and nearest-neighbour search. Then, OGP implies that greedy algorithms for nearest-neighbour search may return a local rather than the global maximum. Furthermore, using the OGP we prove that a natural generalisation of the greedy algorithm, namely the Markov Chain Monte Carlo algorithm, mixes exponentially slowly, and, in particular, takes an exponential time to reach partitions close to the planted partition with high probability.

While there are few theoretical results for modularity–based algorithms, there are positive results for recovering ground truth partitions using local-updates based on modularity in the SBM. As mentioned earlier, Cohen-Addad et al. [10] showed that for the SBM with sufficient signal and two equal-sized blocks, a local algorithm recovers the communities with high probability. This was further extended to general $k$ by giving an algorithm with parallel local updates based on the modularity function [11]. For more details and a discussion of how these relate to our OGP results, see Section 6.

More is known about the behaviour of modularity on random models; we briefly review this for context – see also the survey paper [27]. Considering first random graph models without planted structure, the main results focus on the setting of growing average degree $\overline{d}$ for the random $d$-regular graph [23, 24, 30] and the Erdős-Rényi random graph [25, 31], which are likely to have modularity of the order $1/\sqrt{\overline{d}}$. For the Preferential Attachment (PA) model [2], very recently, this same behaviour was established up to log factors [32]. For models with planted structure, break-through results were given for the SBM by Bickel and Chen [4] showing that the modularity-optimal partition is close to the planted partition. These were extended to the degree-corrected SBM in [36]. See Theorem 2.4 for details. Finally, the modularity in the Artificial Benchmark for Community Detection (ABCD) model, a model similar to the well-known LFR model [21] used by practitioners, was studied in [20].

For now, for simplicity of exposition, we assume that $n$ is divisible by $k$, as this will be assumed in the first lemma, Lemma 3.1. However, in the proof of Theorem 2.6, we relax this condition and deal with the general case.

To prove our main result, we need to investigate a family of partitions of $[n]$ with a given distance to the planted partition $𝒫={(P_i)}_{i=1}^k$. It will be convenient to represent partitions as $k\times k$ matrices that capture the way how these partitions overlap with $𝒫$. Let $𝒜={(A_i)}_{i=1}^k$ be any partition of $[n]$ into $k$ parts. Then, the signature of $𝒜$ (with respect to $𝒫$) is defined as the matrix $X=X(𝒜)={(x_{ij})}_{1\le i\le j\le k}$, where

Note that for the signature to be well defined, one needs to fix the labelling of both $𝒫$ and $𝒜$. To compute the distance between $𝒫$ and $𝒜$, one needs to align these labels as best as possible (see Lemma 3.1 below), but the modularity score clearly does not depend on the way the labels are aligned (see Lemma 4.1 below). Note also that, trivially, $x_{ij}\ge 0$ for all $i,j\in [k]$. Moreover, since $A_1\cup \mathrm{\cdots }\cup A_k=[n]$, for any $j\in [k]$,

Finally, note that the signature of the planted partition $𝒫$ is the matrix $Y^{𝒫}={(y_{ij})}_{1\le i\le j\le k}$ with $y_{ii}=1$ for all $i\in [k]$ and $y_{ij}=0$ for all $i\ne j$.

In our first lemma, we rewrite the distance between any partition $𝒜$ and the planted partition $𝒫$ in a convenient form, namely, as a function of the signature of $𝒜$. The proof is short so we give it below.

The signature of $𝒜$ not only determines the distance between $𝒜$ and $𝒫$ but, more importantly, it predicts (up to an arbitrarily small error in a sufficiently dense graph $G$) the modularity score $q_{𝒜}(G)$ of $𝒜$ for $G\in 𝒢(n,k,p,q)$ generated by the SBM. Indeed we will prove that the modularity score of $𝒜$ is well-approximated by a scaling of $g(X)$, a function only of the signature $X$ of $𝒜$ that is defined by

Recall that the planted partition $𝒫$ has signature $Y^{𝒫}={(y_{ij})}_{1\le i\le j\le k}$ with $y_{ii}=1$ for all $i\in [k]$ and $y_{ij}=0$ for all $i\ne j$. Since $g(Y^{𝒫})=k\cdot (k-1)$, we get that $q_{𝒫}(G)$ is very close to $\left(1-\frac{1}{k}\right)\cdot \frac{a-b}{a+(k-1)b}$.

As one might want to use this result for other purposes, we state it (and prove it, of course) without assuming that $n$ is divisible by $k$. The proof of Lemma 4.1 can be found in the full version of the paper [3], though we describe some intermediate steps below. One of these intermediate steps concerns the modularity score of partitions $𝒜$ with given signature $X$ on a deterministic weighted graph. This can be regarded as a mean-field calculation. Indeed, working with the deterministic weighted graph means we may consider, for example, the edge-weight of edges in part $A_i$ between the planted blocks $P_j$ and $P_{j^{\prime }}$, which corresponds to the expected number of such edges. After that step, it remains only to make a link between the modularity scores of our random graph and those of the deterministic weighted graph.

We have now established that, up to small errors, we may consider $g(X)$ as our objective function, and have re-written our distance to the planted partition in terms of $X$. Thus, the new aim is to maximise $g(X)$ given the distance of $X$ to the planted partition $Y^{𝒫}$.

Note that in the optimiser $X_k^{(i,j)}(t)$, the row sums are $(1+t,1-t,1,\mathrm{\dots },1)$, corresponding to part sizes $(1/k+d,1/k-d,1/k,\mathrm{\dots },1/k)\cdot n$ in the partition at distance with $d=t/k$ (or, thus, equivalently, ).

The following lemma shows that the maximal $g(X)$ for signatures at distance $d>1/k$ (i.e., for $t>1$) is at most the maximal $g(X)$ for signatures at distance $d=1/k$. This result is important to several of our proofs as it will allow us to infer that partitions $𝒜$ with high modularity scores must be at distance $d\le 1/k$ from the planted partition.

The optimisation problems in Lemmas 5.1 and 5.2 are quadratic maximisation problems. (Note that in general quadratic maximisation problems are NP-hard [33].) We prove both lemmas in Appendix C. Lemma 5.1 is the last ingredient needed to prove Theorem 2.6, which gives the likely optimal modularity score over all partitions at distance $d\in [0,1/k]$ from the planted partition. (Recall that we will prove our main OGP result, Theorem 2.2, in Appendix D by appealing to Theorem 2.6.) Lemma 5.2 is used to show slow mixing of a natural MCMC in Theorem B.2.

To understand how these lemmas fit in, recall that the distance to the planted partition $𝒫$ of a partition $𝒜$ with signature $X$ is $d(𝒜,𝒫)=1-\frac{1}{k}{\max }_{\sigma }{\sum }_i{x}_{\sigma (i)i}=\frac{1}{k}{\min }_{\sigma }{\sum }_{i\ne j}{x}_{\sigma (i)j}$, by Lemma 3.1 and since ${\sum }_j{x}_{ij}=1$ for each $i$, so that $x_{\sigma (i)i}=1-{\sum }_{j:j\ne i}{x}_{\sigma (i)j}$. The condition ${\sum }_{i\ne j}{x}_{ij}=t$ corresponds to enforcing a distance of $t/k$ from the planted partition, and the $\arg \max$ tells us the set of partitions that achieve the maximal modularity score at distance $t/k$. Note that, for $t=1$, i.e. at distance of $d=1/k$ from the planted partition, $X_k^{(ij)}(1)$ is the signature for the “decoy” partition $𝒟$ where two planted blocks $P_i$ and $P_j$ are placed within the same part, and all other planted blocks are placed within their own part – see also Figure 1.

The literature contains positive results, with algorithms using local updates based on the modularity function to recover communities in the SBM [10, 11]. This paper proves OGP, a signature of algorithmic hardness, for such algorithms.

Of course this does not give rise to a contradiction, since the setups in [10, 11] and ours are subtly different and also OGP has been exhibited for problems known to be easy [22]. However, it leads to interesting open questions, probing which of the differences in the two setups are important. We describe this now in more detail.

As mentioned earlier, for $k=2$ communities and starting with a random partition into equal-size parts, a local algorithm based on the modularity function was shown to recover the planted communities [10]. The local moves for this algorithm take the form of a swap, which takes pairs of vertices, one from each part, and swaps them if this increases the modularity score. This naturally maintains equal-size parts. For general $k$, an algorithm with parallel local updates based on the modularity function was shown to recover the ground truth partition [11]. We note that this parallel algorithm has a random balanced start and also a mechanism to maintain the balanced sizes of parts during the algorithm.

For the overlap gap property that we establish, it was important that the “decoy” partition $𝒟$, which is an unbalanced partition into $k-1$ parts, has a “surprisingly high” modularity given its distance of $1/k$ from the ground truth partition $𝒫$. Furthermore, at distances from $𝒫$ modularity, optimal partitions are increasingly unbalanced, with part sizes $(1/k+d,\mathrm{\hspace{0.33em}1}/k-d,\mathrm{\hspace{0.33em}1}/k,\mathrm{\dots },1/k)$; see Lemma 5.1.

Perhaps a crucial difference in the two setups is that the positive results of [10, 11] had balanced partitions, both in the initialisation as well as during the algorithm. We finally show that if we introduced this balanced condition into our optimisation problem then it no longer exhibits OGP. In particular, when considering ${\max }_{𝒜}{q}_{𝒜}$ where the maximisation is over balanced $k$-part partitions instead of all $k$-part partitions, we see that this no longer exhibits OGP. We should note that this by itself does not imply success of particular greedy algorithms – and hence fast algorithms. More work needs to be done to exhibit one (as done in [10, 11]). In a similar vain, for the problem of sparse regression [17], in the regime where OGP ceases to hold a greedy type algorithm was established to be effective. The construction is not based on OGP. Instead it relies directly on the properties of the model, which is typically the case.

To state this result, we fix the random graph $G\in 𝒢(n,k,p,q)$ under the conditions of Theorem 2.6. It turns out that the maximum modularity of $G$ only over balanced partitions at distance about from the planted partition $𝒫$ concentrates about some function that now is decreasing in $d$:

Proposition 6.1 implies an analogue of Theorem 2.6, optimising now only over balanced partitions, for , now with decreasing $\tilde{h}(d),$ contrary to $h(d)$.