pith. sign in

arxiv: 1907.02496 · v1 · pith:4L32XYPOnew · submitted 2019-07-04 · 💻 cs.IT · math.IT· math.ST· stat.TH

The Geometry of Community Detection via the MMSE Matrix

Galen Reeves , Vaishakhi Mayya , Alexander Volfovsky This is my paper

Pith reviewed 2026-05-25 08:52 UTC · model grok-4.3

classification 💻 cs.IT math.ITmath.STstat.TH
keywords community detectionstochastic block modelMMSE matrixI-MMSE relationshipheterogeneous networkssignal-to-noise ratiomutual informationminimum mean squared error
0
0 comments X

The pith

Community detection limits in heterogeneous networks reduce to a matrix of effective signal-to-noise ratios that geometrically encodes relationships among communities.

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

The paper examines community detection in network models that allow communities to differ in size and connection behavior, moving beyond the symmetric cases studied earlier. It establishes that the fundamental limits are captured by a single matrix whose entries are effective signal-to-noise ratios, obtained from a matrix extension of the I-MMSE relation. This matrix supplies closed-form expressions for the asymptotic mutual information per node and upper bounds on the minimum mean-squared error of any estimator. The geometric interpretation recovers the familiar scalar SNR threshold when all communities are identical and supplies a concrete way to read off detectability in more realistic, unbalanced networks.

Core claim

The ability to detect communities can be described succinctly in terms of a matrix of effective signal-to-noise ratios that provides a geometrical representation of the relationships between the different communities. This characterization follows from a matrix version of the I-MMSE relationship and generalizes the concept of an effective scalar signal-to-noise ratio. Explicit formulas are obtained for the asymptotic per-node mutual information together with upper bounds on the minimum mean-squared error.

What carries the argument

The MMSE matrix, whose entries are effective signal-to-noise ratios derived via the matrix I-MMSE relation and whose geometry encodes inter-community detectability.

If this is right

  • The asymptotic mutual information per node is given explicitly by a functional of the MMSE matrix.
  • Upper bounds on the MMSE of community recovery follow immediately from the matrix entries.
  • The classical scalar SNR threshold appears as the special case in which the MMSE matrix is a multiple of the identity.
  • Detectability phase transitions for unequal communities are determined by the eigenvalues or positive-definiteness properties of the matrix.

Where Pith is reading between the lines

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

  • In real networks whose communities vary in size, the matrix may reveal that some pairs of communities remain undetectable even when others are easy to separate.
  • The same matrix construction could be applied to other structured inference tasks whose parameters are heterogeneous, such as community detection on degree-corrected or weighted graphs.
  • Finite-size corrections to the matrix predictions could be tested by comparing the large-n formulas against exact computations on moderate-sized graphs.

Load-bearing premise

A matrix version of the I-MMSE relationship must hold for the heterogeneous network models in the large-network limit.

What would settle it

Compute the actual per-node mutual information on a sequence of heterogeneous stochastic block models with increasing size and check whether it deviates from the value predicted by the MMSE matrix.

Figures

Figures reproduced from arXiv: 1907.02496 by Alexander Volfovsky, Galen Reeves, Vaishakhi Mayya.

Figure 1
Figure 1. Figure 1: Comparison of upper bound on tr(MMSE(X | G)) given in Theorem 3 (black contour lines) and the empirical MSE of belief propagation (heat map) on a network of size n = 105 with average degree d = 30. In both cases, R = diag(λ1, λ2). The upper bound on the weak recovery threshold given in Theorem 5 (solid blue line) corresponds to the boundary where ∆∗ = 0. The weak recovery threshold for acyclic BP [10] (das… view at source ↗
read the original abstract

The information-theoretic limits of community detection have been studied extensively for network models with high levels of symmetry or homogeneity. The contribution of this paper is to study a broader class of network models that allow for variability in the sizes and behaviors of the different communities, and thus better reflect the behaviors observed in real-world networks. Our results show that the ability to detect communities can be described succinctly in terms of a matrix of effective signal-to-noise ratios that provides a geometrical representation of the relationships between the different communities. This characterization follows from a matrix version of the I-MMSE relationship and generalizes the concept of an effective scalar signal-to-noise ratio introduced in previous work. We provide explicit formulas for the asymptotic per-node mutual information and upper bounds on the minimum mean-squared error. The theoretical results are supported by numerical simulations.

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.

Referee Report

0 major / 3 minor

Summary. The paper extends the information-theoretic study of community detection from homogeneous to heterogeneous stochastic block models that allow variability in community sizes and behaviors. It claims that detection limits are characterized by a matrix of effective signal-to-noise ratios obtained via a matrix generalization of the I-MMSE relation; this matrix supplies a geometric representation of inter-community relationships. Explicit formulas are given for the asymptotic per-node mutual information together with upper bounds on the minimum mean-squared error, and the results are illustrated with numerical simulations.

Significance. If the matrix I-MMSE relation holds for the stated class of models, the geometric SNR-matrix description constitutes a natural and useful generalization of the scalar effective-SNR concept from prior work. The explicit formulas for mutual information and the MMSE bounds are a concrete strength that facilitates further analysis.

minor comments (3)
  1. The abstract states that the matrix I-MMSE relation 'follows from' the standard identity but does not list the precise regularity conditions on community-size distributions or edge-probability heterogeneity required for the asymptotic limit; adding one sentence would improve clarity for readers.
  2. [Numerical Simulations] In the simulation section, the captions of the figures comparing the matrix-based predictions to empirical MMSE should report the exact community-size vectors and intra-/inter-community probability matrices used, to support reproducibility.
  3. Notation for the effective SNR matrix (denoted M or similar) should be introduced once with a clear mapping to the underlying community parameters before it is used in the main theorems.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work and the recommendation for minor revision. No specific major comments are provided in the report, so there are no individual points requiring detailed rebuttal or revision at this stage. We will address any minor editorial suggestions from the editor in the revised manuscript.

Circularity Check

0 steps flagged

No significant circularity; matrix I-MMSE applied as generalization of prior scalar results to heterogeneous models.

full rationale

The paper states that the geometric representation via the effective SNR matrix follows from a matrix version of the I-MMSE relationship, generalizing prior scalar SNR concepts. No quoted derivation step reduces the claimed prediction or characterization to a fitted parameter, self-defined quantity, or unverified self-citation chain by construction. The central result is presented as an application of the identity to the chosen model class in the large-network limit, with explicit formulas and bounds derived from that application. This is self-contained against external benchmarks and receives the default non-finding.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the applicability of a matrix I-MMSE relation to the heterogeneous stochastic block model class and on the existence of an asymptotic per-node limit; no free parameters or invented entities are visible in the abstract.

axioms (2)
  • domain assumption Matrix version of the I-MMSE relationship holds for the heterogeneous network model
    Invoked to obtain the effective SNR matrix and the mutual information formulas.
  • domain assumption Asymptotic regime for per-node mutual information and MMSE
    Stated explicitly in the abstract for the main results.

pith-pipeline@v0.9.0 · 5669 in / 1215 out tokens · 35375 ms · 2026-05-25T08:52:29.888413+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · 1 internal anchor

  1. [1]

    Stochastic block models: First steps,

    P. W. Holland, K. B. Laskey, and S. Leinhardt, “Stochastic block models: First steps,” Social networks, vol. 5, no. 2, pp. 109–137, 1983

    work page 1983

  2. [2]

    Asympt otic analysis of the stochastic block model for modular networks and its algorithmic applications,

    A. Decelle, F. Krzakala, C. Moore, and L. Zdeborov´ a, “Asympt otic analysis of the stochastic block model for modular networks and its algorithmic applications,” Physitcal Review Eq , vol. 84, no. 6, Dec. 2011

    work page 2011

  3. [3]

    Asymptotic mutual information for the balanced binary stochastic block model,

    Y. Deshpande, E. Abbe, and A. Montanari, “Asymptotic mutual information for the balanced binary stochastic block model,” Information and Inference , vol. 6, no. 2, pp. 125–170, Jun. 2017

    work page 2017

  4. [4]

    Recovering asymmet ric communities in the stochastic block model,

    F. Caltagirone, M. Lelarge, and L. Miolane, “Recovering asymmet ric communities in the stochastic block model,” IEEE Transactions on Network Science and Engineering , vol. 5, no. 3, pp. 237–246, 2018

    work page 2018

  5. [5]

    Fundamental limits of symmetric low-ra nk matrix estimation,

    M. Lelarge and L. Miolane, “Fundamental limits of symmetric low-ra nk matrix estimation,” Probability Theory and Related Fields , 2018

    work page 2018

  6. [6]

    Mutual information for sym- metric rank-one matrix estimation: A proof of the replica formula,

    J. Barbier, M. Dia, N. Macris, F. Krzakala, T. Lesieur, and L. Zde borov´ a, “Mutual information for sym- metric rank-one matrix estimation: A proof of the replica formula,” in Advances in Neural Information Processing Systems (NIPS) , vol. 29, Barcelona, Spain, 2016, pp. 424–432

    work page 2016

  7. [7]

    Constrained low- rank matrix estimation: Phase transi- tions, approximate message passing and applications,

    T. Lesieur, F. Krzakala, and L. Zdeborov´ a, “Constrained low- rank matrix estimation: Phase transi- tions, approximate message passing and applications,” Journal of Statistical Mechanics: Theory and Experiment, Jul. 2017

    work page 2017

  8. [8]

    Mutual information in r ank-one matrix estimation,

    F. Krzakala, J. Xu, and L. Zdeborov´ a, “Mutual information in r ank-one matrix estimation,” in Proceed- ings of the IEEE Information Theory Workshop (ITW) , 2016

    work page 2016

  9. [9]

    Contextu al stochastic block models,

    Y. Deshpande, A. Montanari, E. Mossel, and S. Sen, “Contextu al stochastic block models,” in NeurIPS, 2018

    work page 2018

  10. [10]

    Proof of the achievability conjecture s for the general stochastic block model,

    E. Abbe and C. Sandon, “Proof of the achievability conjecture s for the general stochastic block model,” Communications on Pure and Applied Mathematics , vol. 71, no. 7, pp. 1334–1406, 2018

    work page 2018

  11. [11]

    Informatio n-theoretic thresholds for community detection in sparse networks,

    J. Banks, C. Moore, J. Neeman, and P. Netrapalli, “Informatio n-theoretic thresholds for community detection in sparse networks,” in Conference On Learning Theory , 2016

    work page 2016

  12. [12]

    Community detection and stochastic block models: Re cent developments,

    E. Abbe, “Community detection and stochastic block models: Re cent developments,” Journal of Ma- chine Learning Research, vol. 18, no. 177, pp. 1–86, 2018

    work page 2018

  13. [13]

    Spectral clustering and the high-dimensional stochastic block- model,

    K. Rohe, S. Chatterjee, B. Yu et al. , “Spectral clustering and the high-dimensional stochastic block- model,” The Annals of Statistics , vol. 39, no. 4, pp. 1878–1915, 2011

    work page 1915

  14. [14]

    Empirical Bayes estimation for the stochastic blockmodel,

    S. Suwan, D. S. Lee, R. Tang, D. L. Sussman, M. Tang, and C. E . Priebe, “Empirical Bayes estimation for the stochastic blockmodel,” Electronic Journal of Statistics , vol. 10, no. 1, pp. 761–782, 2016

    work page 2016

  15. [15]

    Mutual information a s a function of matrix SNR for linear gaussian channels,

    G. Reeves, H. D. Pfister, and A. Dytso, “Mutual information a s a function of matrix SNR for linear gaussian channels,” in Proceedings of the IEEE International Symposium on Informa tion Theory (ISIT) , Vail, CO, Jun. 2018

    work page 2018

  16. [16]

    The concave-convex procedu re (CCCP),

    A. L. Yuille and A. Rangarajan, “The concave-convex procedu re (CCCP),” in Advances in Neural Information Processing Systems (NIPS) , 2002, pp. 1033–1040

    work page 2002

  17. [17]

    Applications of the Lindeberg p rinciple in communications and sta- tistical learning,

    S. B. Korada and A. Montanari, “Applications of the Lindeberg p rinciple in communications and sta- tistical learning,” IEEE Transactions on Information Theory , vol. 57, no. 4, p. 2011, Apr. 2011. 25

    work page 2011

  18. [18]

    Broken replica symmetry bounds in the mean field sp in glass model,

    F. Guerra, “Broken replica symmetry bounds in the mean field sp in glass model,” Communications in Mathematical Physics, vol. 233, no. 2, pp. 1–12, 2003

    work page 2003

  19. [19]

    The adaptive interpolation method: a simple scheme to prove replica formulas in bayesian inference,

    J. Barbier and N. Macris, “The adaptive interpolation method: a simple scheme to prove replica formulas in bayesian inference,” Probability Theory and Related Fields , Oct. 2018

    work page 2018

  20. [20]

    Additivity of Information in Multilayer Networks via Additive Gaussian Noise Transforms

    G. Reeves, “Additivity of information in multilayer networks via ad ditive Gaussian noise transforms,” in Proceedings of the Allerton Conference on Communication, C ontrol, and Computing , Monticello, IL, 2017, [Online]. Available https://arxiv.org/abs/1710.04580

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  21. [21]

    H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spa ces, 2nd ed. Springer, 2017

    work page 2017

  22. [22]

    Envelope theorems for arbitrary choic e sets,

    P. Milgrom and I. Segal, “Envelope theorems for arbitrary choic e sets,” Econometrica, vol. 70, no. 2, pp. 583–601, Mar. 2002

    work page 2002

  23. [23]

    Boucheron, G

    S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013

    work page 2013

  24. [24]

    A generalization of the lindeberg principle,

    S. Chatterjee, “A generalization of the lindeberg principle,” The Annals of Probability , vol. 34, no. 6, pp. 2061–2076, 2006

    work page 2061

  25. [25]

    Mutual information and minim um mean-square error in Gaussian channels,

    D. Guo, S. Shamai, and S. Verd´ u, “Mutual information and minim um mean-square error in Gaussian channels,” IEEE Transactions on Information Theory , vol. 51, no. 4, pp. 1261–1282, Apr. 2005

    work page 2005

  26. [26]

    Gradient of mutual information in linear vector Gaussian channels,

    D. P. Palomar and S. Verd´ u, “Gradient of mutual information in linear vector Gaussian channels,” IEEE Transactions on Information Theory , vol. 52, no. 1, pp. 141–154, Jan. 2006

    work page 2006

  27. [27]

    Linear precoding for mutual information maximiza tion in MIMO systems,

    M. Lamarca, “Linear precoding for mutual information maximiza tion in MIMO systems,” in Proceedings of the International Conference on Wireless Communication Systems, Tuscany, Italy, Sep. 2009

    work page 2009

  28. [28]

    Hessian and concavity of mutual in formation, differential entropy, and entropy power in linear vector Gaussian channels,

    M. Payar´ o and D. Palomar, “Hessian and concavity of mutual in formation, differential entropy, and entropy power in linear vector Gaussian channels,” IEEE Transactions on Information Theory , vol. 55, no. 8, pp. 3613–3628, 2009. 26

    work page 2009