arxiv: 2605.10911 · v1 · submitted 2026-05-11 · 🧮 math.PR · cs.CC· cs.DS· math.CO· math.ST· stat.TH

Recognition: no theorem link

The stochastic block model has the overlap graph property for modularity

David Gamarnik, Fiona Skerman, Nelly Litvak, Pawel Pralat, Remco van der Hofstad, Shankar Bhamidi, Yasmin Tousinejad

Pith reviewed 2026-05-12 03:30 UTC · model grok-4.3

classification 🧮 math.PR cs.CCcs.DSmath.COmath.STstat.TH

keywords stochastic block modelmodularityoverlap gap propertycommunity detectionlocal algorithmsMarkov chains

0 comments

The pith

The stochastic block model exhibits the overlap gap property for modularity

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proves that modularity has the overlap gap property when applied to graphs from the stochastic block model. In this model, the graph is generated with a planted partition into equal-sized communities, with higher connection probability inside communities. The overlap gap property means that partitions with near-maximal modularity scores must have either high or low overlap with the planted partition, with no solutions in between. This matters because it shows that local algorithms optimizing modularity cannot find the planted communities, and it explains why certain sampling methods mix slowly.

Core claim

The authors show that with high probability in the SBM, the modularity-optimal partition is close to the planted one, and moreover any partition with modularity close to optimal is also close to the planted partition. This establishes the overlap gap property for modularity on the planted SBM, extending earlier work that only showed it for the optimum itself.

What carries the argument

The overlap gap property for modularity, which requires that near-optimal solutions are separated in their overlap with the ground truth partition.

If this is right

Local algorithms based on modularity cannot recover the communities in the SBM.
The Markov chain on partitions with transitions that improve modularity has slow mixing time.
This is a rare example of OGP established in a planted model rather than a null model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The result suggests that optimizing modularity may be computationally hard in the same regimes where information-theoretically possible for community detection.
Similar OGP might apply to other popular clustering objectives like normalized cut.

Load-bearing premise

The planted partition is the unique global maximizer of modularity up to o(n) local moves for the parameters where the result holds.

What would settle it

Finding, in a large SBM graph, a partition that achieves modularity nearly as high as the optimum but overlaps the planted partition in a fraction between epsilon and 1-epsilon of vertices would disprove the OGP claim.

read the original abstract

The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to coincide with conjectured algorithmic limits in problems with statistical computational gap. We consider the Stochastic Block Model (SBM), where the graph has a planted partition with $k$ equal-size blocks which form the `communities', and where, for parameters $p>q$, vertices within the same community connect with probability $p$, while vertices in different communities connect with probability $q$, independently across pairs of vertices. Modularity--based clustering algorithms have become ubiquitous in applications. This article studies theoretical limits of local algorithms based on the modularity score on the SBM. We establish that modularity exhibits OGP on the SBM. This rules out a class of local algorithms based on modularity for recovery in the SBM, and shows slow mixing time for a related Markov Chain. Theoretically this is one of the few instances where OGP has been established for a `planted' model, as most such analyses to date consider the `null' model. As part of our analysis, we extend a result by Bickel and Chen 2009, who established that with high probability, the modularity optimal partition of SBM is $o(n)$ local moves away from the planted partition, where $n$ is the graph size. We show that, with high probability, any partition with modularity score sufficiently near the optimal value is close to the planted partition.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper extends Bickel-Chen to show modularity has OGP on planted SBM, but the result stays conditional on an unspecified regime where the planted partition is already the unique global max.

read the letter

The core claim here is that modularity on the equal-sized SBM exhibits the overlap gap property: with high probability, every partition whose modularity is within o(1) of the optimum differs from the planted one in only o(n) vertices. This is obtained by lifting the 2009 Bickel-Chen result (which already placed the single global optimum close to the planted partition) to all near-optimal partitions. The payoff is that local search or MCMC methods driven by modularity cannot recover the communities, even in the strong-signal regime where exact recovery is information-theoretically possible. That is the main new piece: an OGP statement for a planted rather than null model, plus the strengthening from one optimum to the whole near-optimal set. The argument appears to stay first-principles once the Bickel-Chen input is granted, so there is no obvious circularity. The extension itself is non-routine and directly addresses why a popular heuristic fails to match the information-theoretic threshold. The soft spot is exactly the one flagged in the stress-test note. The OGP conclusion is stated only under the assumption that the planted partition is already the unique global maximizer up to o(n) moves; the abstract supplies no explicit lower bound on (p-q) or on the SNR relative to k that makes this uniqueness hold. Without those thresholds the statement is formally correct only inside an unspecified subset of the p>q quadrant, and outside that subset the gap can collapse. If the full proof pins down the regime (for instance via the same second-moment or concentration tools used by Bickel-Chen), the gap is minor; if it does not, the applicability range remains unclear. The paper is aimed at people working on algorithmic barriers in community detection and on the geometry of optimization landscapes in random graphs. A reader who already knows the Bickel-Chen result and cares about local algorithms will get a clean, usable obstruction. It is worth sending to referees: the central geometric statement is well-motivated and the extension is technically interesting, even if the parameter window needs to be made explicit before publication.

Referee Report

2 major / 2 minor

Summary. The paper claims that modularity on the k-block stochastic block model (SBM) with equal block sizes and p > q exhibits the overlap gap property (OGP): with high probability, every partition whose modularity is within o(1) of the global maximum differs from the planted partition in only o(n) vertices. This extends the 2009 global-optimality result of Bickel and Chen and is used to rule out a class of local modularity-based algorithms for community recovery while also implying slow mixing for an associated Markov chain. The argument is presented as one of the few OGP analyses for a planted (rather than null) model.

Significance. If the thresholds and derivation hold, the result is significant: it supplies a concrete geometric obstruction for local search on a planted model that is directly relevant to the statistical-computational gap in SBM recovery, and it strengthens the link between OGP and algorithmic hardness beyond the usual null-model setting.

major comments (2)

[Abstract / extension of Bickel-Chen] Abstract and the paragraph extending Bickel-Chen (2009): the OGP statement is asserted only under the assumption that the planted partition is already the unique global maximizer up to o(n) moves, yet no explicit regime (lower bound on p-q, on the SNR (sqrt(p)-sqrt(q))^2 relative to k, or on n) is supplied in which this uniqueness holds w.h.p. Without such thresholds the claim is formally true only on an unspecified subset of the (p>q) quadrant; in the complementary regime other partitions can achieve near-optimal modularity while differing in a constant fraction of vertices, destroying the overlap gap.
[Main theorem / proof of OGP] The load-bearing step that near-optimal partitions are o(n)-close to the planted one is stated to follow from a first-principles analysis of the modularity landscape, but the manuscript supplies neither the precise quantitative bound on the modularity gap nor the concentration argument that would rule out constant-fraction overlaps; without these the extension from global optimality to near-optimality cannot be verified.

minor comments (2)

[Abstract] The abstract refers to 'sufficiently near the optimal value' without defining the o(1) gap size; a concrete expression in terms of n, p, q, k should be given in the theorem statement.
[Introduction] Notation for the modularity function and the overlap distance should be introduced once in the introduction and used consistently; several passages reuse 'close' without a formal definition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below, clarifying the dependence on prior results and committing to strengthen the quantitative details in the revision.

read point-by-point responses

Referee: [Abstract / extension of Bickel-Chen] Abstract and the paragraph extending Bickel-Chen (2009): the OGP statement is asserted only under the assumption that the planted partition is already the unique global maximizer up to o(n) moves, yet no explicit regime (lower bound on p-q, on the SNR (sqrt(p)-sqrt(q))^2 relative to k, or on n) is supplied in which this uniqueness holds w.h.p. Without such thresholds the claim is formally true only on an unspecified subset of the (p>q) quadrant; in the complementary regime other partitions can achieve near-optimal modularity while differing in a constant fraction of vertices, destroying the overlap gap.

Authors: We agree that the regime must be stated explicitly for the claim to be fully rigorous. The manuscript extends Bickel and Chen (2009) precisely in the regime where their global-optimality result applies (i.e., when the SNR (√p − √q)^2 exceeds a k-dependent constant that ensures the planted partition is the unique maximizer w.h.p.). In the revision we will insert the explicit lower bound on the SNR (or equivalently on p − q) both in the abstract and in the statement of the main theorem, together with a short reference to the precise condition from Bickel and Chen. This makes the OGP statement hold exactly on the subset of the (p > q) quadrant where the planted partition is already known to be the unique global maximizer. revision: yes
Referee: [Main theorem / proof of OGP] The load-bearing step that near-optimal partitions are o(n)-close to the planted one is stated to follow from a first-principles analysis of the modularity landscape, but the manuscript supplies neither the precise quantitative bound on the modularity gap nor the concentration argument that would rule out constant-fraction overlaps; without these the extension from global optimality to near-optimality cannot be verified.

Authors: The proof proceeds by showing that any partition whose overlap with the planted partition differs by a constant fraction incurs a modularity deficit of Ω(1) (with the implicit constant depending on p, q, k) with high probability. This follows from a direct comparison of the expected modularity contributions inside versus across blocks, combined with standard Chernoff bounds on the binomial edge counts. We acknowledge that the manuscript presents this argument at a high level without spelling out the explicit gap constant or the precise tail bounds. In the revision we will add a dedicated lemma stating the quantitative lower bound on the modularity gap (Ω(δ) where δ is the fractional overlap difference) and include the explicit concentration inequality used, thereby making the passage from global optimality to near-optimality fully verifiable. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation extends external result via independent analysis

full rationale

The paper extends the external 2009 Bickel-Chen result (that the modularity global optimum is o(n)-close to the planted partition w.h.p.) by performing a first-principles analysis of the modularity landscape to show that all sufficiently near-optimal partitions are likewise close to the planted one. This establishes the OGP without any self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations. The central claim rests on direct probabilistic control of the modularity score differences rather than re-expressing the input assumptions or prior fitted quantities. The cited Bickel-Chen result is independent and externally verifiable.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard probabilistic assumptions of the SBM (independent edges, fixed p>q, equal block sizes) and the definition of modularity; no new free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Edges are independent Bernoulli random variables with probabilities p inside blocks and q between blocks.
Standard SBM generative model invoked throughout the abstract.
domain assumption The planted partition is the unique global maximizer of modularity up to o(n) vertex moves (extension of Bickel-Chen).
The base result being extended; required for the OGP statement to hold.

pith-pipeline@v0.9.0 · 5623 in / 1454 out tokens · 36640 ms · 2026-05-12T03:30:57.305920+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

[1]

5 V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks.Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008,

work page 2008
[2]

doi: 10.1007/978-3-319-24777-9. 7 U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner. On modularity clustering.IEEE Transactions on Knowledge and Data Engineering, 20(2):172–188,

work page doi:10.1007/978-3-319-24777-9
[3]

Cohen-Addad, F

10 V. Cohen-Addad, F. Mallmann-Trenn, and D. Saulpic. A massively parallel modularity- maximizing algorithm with provable guarantees. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 356–365,

work page 2022
[4]

Coja-Oghlan, A

11 A. Coja-Oghlan, A. Galanis, L. A. Goldberg, J. B. Ravelomanana, D. Štefankovič, and E. Vigoda. Metastability of the Potts ferromagnet on random regular graphs.Comm. Math. Phys.,401(1):185–225, 2023.doi:10.1007/s00220-023-04644-6. 12 S. Fortunato and M. Barthelemy. Resolution limit in community detection.Proceedings of the national academy of sciences, ...

work page doi:10.1007/s00220-023-04644-6 2023
[5]

Gamarnik, C

15 D. Gamarnik, C. Moore, and L. Zdeborová. Disordered systems insights on computational hardness.Journal of Statistical Mechanics: Theory and Experiment, 2022(11):114015,

work page 2022
[6]

McDiarmid and F

27 C. McDiarmid and F. Skerman. Modularity and partially observed graphs.arXiv preprint arXiv:2112.13190,

work page arXiv
[7]

29 M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69(2):026113, 2004.doi:10.1103/physreve.69.026113. 30 L. O. Prokhorenkova, A. Raigorodskii, and P. Pralat. Modularity of complex networks models. Internet Mathematics,

work page doi:10.1103/physreve.69.026113 2004
[8]

Rybarczyk and M

31 K. Rybarczyk and M. Sulkowska. New bounds on the modularity ofG(n,p ).arXiv preprint arXiv:2504.16254,

work page arXiv
[9]

Rybarczyk and M

32 K. Rybarczyk and M. Sulkowska. Modularity of Preferential Attachment Graphs. In43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026), pages 76:1–76:19, 2026.doi:10.4230/LIPIcs.STACS.2026.76. 33 S. Sahni. Computationally related problems.SIAM Journal on Computing, 3(4):262–279,

work page doi:10.4230/lipics.stacs.2026.76 2026