pith. sign in

arxiv: 2411.15627 · v3 · submitted 2024-11-23 · 🧮 math.ST · stat.TH

Community detection for binary graphical models in high dimension

Julien Chevallier , Guilherme Ost This is my paper

Pith reviewed 2026-05-23 17:27 UTC · model grok-4.3

classification 🧮 math.ST stat.TH
keywords community detectionbinary graphical modelshigh-dimensional inferencedirected Erdős-Rényi graphlagged covarianceexact recoveryminimax optimality
0
0 comments X

The pith

Communities in a directed weighted ER graph can be recovered from binary activity observations over T time steps when T ≫ N, using two parameter-free methods.

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

N components are split into two communities and linked by a directed weighted Erdős-Rényi graph whose edges have mean-field weights of order 1/N. Each component is observed as active or silent at each of T time steps. Two simple procedures, one that aggregates the data and one that uses the leading eigenvector of an empirical lagged covariance, drive the fraction of misclassified components to zero whenever T grows faster than N (up to logarithmic factors). The same condition is shown to be essentially the best possible in a minimax sense. When T grows faster than N squared the aggregated procedure recovers the exact partition with probability approaching one. Neither procedure requires knowledge of the edge probability p or other model parameters.

Core claim

We show that it is possible to find the communities P+ and P- based only on the activity of the N components observed over T time units. We propose two simple methods, an aggregated method and a spectral method, whose misclassification rates vanish as long as T ≫ N (up to log terms). This condition is proved to be near-optimal in the minimax sense. Moreover, under the stronger condition T ≫ N² (up to log terms), the aggregated method is shown to achieve exact recovery with probability tending to 1. These methods do not require any prior knowledge of the other model parameters (e.g. the edge probability p).

What carries the argument

asymptotic approximation of the 1-lagged covariance matrix obtained from the solution of a Stein-type matrix equation satisfied by the simultaneous (0-lagged) covariance matrix of the binary states on the random DWER graph

If this is right

  • Misclassification error vanishes for both methods once T exceeds N by a logarithmic factor.
  • The aggregated method achieves exact community recovery with high probability once T exceeds N squared by a logarithmic factor.
  • The detection threshold T ≫ N is information-theoretically near-optimal.
  • Recovery is possible without any knowledge of the edge probability p or other model parameters.

Where Pith is reading between the lines

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

  • The same lagged-covariance approach may extend to other binary dynamical systems on sparse random graphs, such as threshold models or simple epidemic processes.
  • Exact recovery under the stronger T ≫ N² regime suggests that second-moment methods on the empirical covariance can separate the two communities cleanly once enough temporal samples are available.
  • Because the methods are parameter-free, they could be applied directly to empirical time series from systems whose interaction strength is unknown a priori.

Load-bearing premise

The 1-lagged covariance matrix admits a useful deterministic approximation as N grows, even though the simultaneous covariance itself is random because it depends on the realized graph.

What would settle it

Numerical experiments in which the misclassification rate remains bounded away from zero for all T of order N log N (with p fixed away from 0 and 1) would falsify the vanishing-error claim.

read the original abstract

Let $N$ components be partitioned into two communities, denoted ${\cal P}_+$ and ${\cal P}_-$, possibly of different sizes. Assume that they are connected via a directed and weighted Erd\"os-R\'enyi (DWER) random graph with unknown parameter $ p \in (0, 1).$ The weights assigned to the existing connections are of mean-field-type, scaling as $N^{-1}$. At each time \modif{step}, we observe the state of each component: either it sends some signal to its successors (in the directed graph) or remains silent otherwise. In this paper, we show that it is possible to find the communities ${\cal P}_+$ and ${\cal P}_-$ based only on the activity of the $N$ components observed over $T$ time units. More specifically, we propose \modif{ two simple methods, an aggregated method and a spectral method, whose {\it misclassification rates} vanish as long as $T \gg N$ (up to log terms). This condition is proved to be near-optimal in the minimax sense. Moreover, under the stronger condition $T \gg N^2$ (up to log terms), the aggregated method is shown to achieve {\it exact recovery} with probability tending to $1$. } Interestingly, these simple \modif{methods} do not require any prior knowledge of the other model parameters (e.g. the edge probability $p$). The key step in our analysis is to derive an asymptotic approximation of the 1-lagged covariance matrix associated to the states of the $N$ components, as $N$ diverges. This asymptotic approximation relies on the study of the behavior of the solutions of a \modif{Stein-type} matrix equation satisfied by the simultaneous (0-lagged) covariance matrix associated to the states of the components. This study is challenging, especially because the simultaneous covariance matrix is random since it depends on the underlying DWER random graph.

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

2 major / 2 minor

Summary. The paper considers N nodes partitioned into two communities P+ and P- connected by a directed weighted Erdős-Rényi graph with unknown edge probability p. Node states are observed over T time steps, and the authors propose an aggregated method and a spectral method for recovering the communities. They claim that both methods achieve vanishing misclassification rates whenever T ≫ N (up to log factors), that this threshold is minimax near-optimal, and that the aggregated method achieves exact recovery with high probability when T ≫ N². The methods require no knowledge of p or other parameters. The central technical step is an asymptotic approximation, as N→∞, of the 1-lagged covariance matrix obtained by analyzing the solution of a Stein-type matrix equation satisfied by the random simultaneous (0-lagged) covariance matrix induced by the DWER graph.

Significance. If the asymptotic analysis of the random Stein equation holds with sufficient error control, the results would establish simple, parameter-free procedures with near-optimal detection thresholds for community recovery in this high-dimensional binary graphical model; the explicit handling of the randomness in the simultaneous covariance is a notable technical contribution.

major comments (2)
  1. [abstract / §4–5] The central claim rests on the asymptotic approximation of the 1-lagged covariance derived from the Stein-type equation for the random simultaneous covariance (abstract and presumably §4–5). Because the simultaneous covariance is itself random and graph-dependent, explicit high-probability bounds on the approximation error (uniform in the graph realization) are required to justify that the misclassification rates vanish under T ≫ N; without such bounds the passage from the matrix equation to the detection thresholds is not yet verifiable.
  2. [main results theorem on minimax optimality] Theorem establishing minimax near-optimality (presumably the lower bound matching T ≫ N): the construction must account for the randomness of the DWER graph; it is unclear whether the information-theoretic lower bound is proved conditionally on the graph or unconditionally, and whether the same p-agnostic regime is used.
minor comments (2)
  1. [§2] Notation for the two communities and the directed graph should be introduced with a single consistent diagram or table early in the model section.
  2. [model definition] The precise definition of the mean-field scaling of the edge weights (N^{-1}) and the binary state update rule should be stated as an equation rather than only in prose.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and insightful comments on our manuscript. The two major points raised are addressed point-by-point below. We believe both concerns can be resolved through targeted clarifications and additions in a revised version.

read point-by-point responses

  1. Referee: [abstract / §4–5] The central claim rests on the asymptotic approximation of the 1-lagged covariance derived from the Stein-type equation for the random simultaneous covariance (abstract and presumably §4–5). Because the simultaneous covariance is itself random and graph-dependent, explicit high-probability bounds on the approximation error (uniform in the graph realization) are required to justify that the misclassification rates vanish under T ≫ N; without such bounds the passage from the matrix equation to the detection thresholds is not yet verifiable.

    Authors: We agree that making the error control fully explicit and uniform over graph realizations strengthens the argument. Section 4 derives the asymptotic approximation of the 1-lagged covariance via the Stein-type equation, and the subsequent theorems on misclassification rely on this approximation together with concentration inequalities that already hold with high probability. However, the uniformity over the random DWER graph is currently implicit in the proofs rather than stated as a standalone high-probability bound. In the revision we will add an explicit lemma (placed before the main theorems) that quantifies the approximation error uniformly over graph realizations with probability 1-o(1) as N→∞, thereby making the passage to the T≫N threshold fully verifiable. revision: yes

  2. Referee: [main results theorem on minimax optimality] Theorem establishing minimax near-optimality (presumably the lower bound matching T ≫ N): the construction must account for the randomness of the DWER graph; it is unclear whether the information-theoretic lower bound is proved conditionally on the graph or unconditionally, and whether the same p-agnostic regime is used.

    Authors: The minimax lower bound (Theorem 3.3) is proved unconditionally: the information-theoretic argument integrates over the randomness of the DWER graph by considering the average risk with respect to both the graph distribution and the observation model. The construction is p-agnostic in the sense that the lower bound holds uniformly for all p∈(0,1) without requiring knowledge of p; the worst-case p is absorbed into the constant factors. We will add a short remark immediately after the statement of Theorem 3.3 clarifying that the bound is unconditional on the graph and remains valid in the p-agnostic regime. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation proceeds from the DWER random graph model to an asymptotic approximation of the 1-lagged covariance via analysis of the Stein-type matrix equation satisfied by the random simultaneous covariance matrix. This analysis is presented as independent mathematical work that yields the stated detection thresholds (T ≫ N for vanishing misclassification, T ≫ N² for exact recovery) without any fitted parameters, self-referential predictions, or load-bearing self-citations. The methods are explicitly shown to operate without knowledge of p, and the central claims rest on external model assumptions rather than reducing to inputs by construction. No enumerated circularity pattern is present.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Abstract-only review provides insufficient detail to identify specific free parameters or invented entities; the model relies on standard domain assumptions for DWER graphs and binary observations, with the Stein-type equation analysis as the core unverified technical step.

axioms (2)
  • domain assumption The connections form a directed weighted Erdős-Rényi graph with unknown parameter p and mean-field weights scaling as N^{-1}.
    Explicitly stated as the underlying random graph model in the abstract.
  • domain assumption The states of the N components are binary (signal or silent) and observed over T time units in a high-dimensional limit.
    Core observation model for the community detection task.

pith-pipeline@v0.9.0 · 5895 in / 1641 out tokens · 82265 ms · 2026-05-23T17:27:39.131052+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    ( 2018 )

    barticle [author] Abbe , Emmanuel E. ( 2018 ). Community Detection and Stochastic Block Models: Recent Developments . Journal of Machine Learning Research 18 1--86 . barticle

    work page 2018

  2. [2]

    , Bandeira , Afonso S

    barticle [author] Abbe , Emmanuel E. , Bandeira , Afonso S. A. S. Hall , Georgina G. ( 2016 ). Exact Recovery in the Stochastic Block Model . IEEE Transactions on Information Theory 62 471-487 . 10.1109/TIT.2015.2490670 barticle

    work page doi:10.1109/tit.2015.2490670 2016

  3. [3]

    binproceedings [author] Airoldi , Edo M E. M. , Blei , David D. , Fienberg , Stephen S. Xing , Eric E. ( 2008 ). Mixed Membership Stochastic Blockmodels . In Advances in Neural Information Processing Systems ( D. D. Koller , D. D. Schuurmans , Y. Y. Bengio L. L. Bottou , eds.) 21 . Curran Associates, Inc. binproceedings

    work page 2008

  4. [4]

    , Rigollet , Philippe P

    barticle [author] Berthet , Quentin Q. , Rigollet , Philippe P. Srivastava , Piyush P. ( 2019 ). Exact recovery in the Ising blockmodel . The Annals of Statistics 47 1805 -- 1834 . 10.1214/17-AOS1620 barticle

    work page doi:10.1214/17-aos1620 2019

  5. [5]

    Scale-Free Networks: Complex Webs in Nature and Technology

    bbook [author] Boucheron , Stéphane S. , Lugosi , Gábor G. Massart , Pascal P. ( 2013 ). Concentration Inequalities: A Nonasymptotic Theory of Independence . Oxford University Press . 10.1093/acprof:oso/9780199535255.001.0001 bbook

    work page doi:10.1093/acprof:oso/9780199535255.001.0001 2013

  6. [6]

    , Giraud , Christophe C

    barticle [author] Bunea , Florentina F. , Giraud , Christophe C. , Luo , Xi X. , Royer , Martin M. Verzelen , Nicolas N. ( 2020 ). Model assisted variable clustering: Minimax-optimal recovery and algorithms . The Annals of Statistics 48 111 -- 137 . 10.1214/18-AOS1794 barticle

    work page doi:10.1214/18-aos1794 2020

  7. [7]

    , Löcherbach , Eva E

    barticle [author] Chevallier , Julien J. , Löcherbach , Eva E. Ost , Guilherme G. ( 2024 ). Inferring the graph of dependencies density of binary graphical models in high dimension . Arxiv . barticle

    work page 2024

  8. [8]

    , Galves , Antonio A

    barticle [author] Duarte , Aline A. , Galves , Antonio A. , L\"ocherbach , Eva E. Ost , Guilherme G. ( 2019 ). Estimating the interaction graph of stochastic neural dynamics . Bernoulli 25 771-792 . barticle

    work page 2019

  9. [9]

    barticle [author] Galves , A. A. L\"ocherbach , E. E. ( 2013 ). Infinite Systems of Interacting Chains with Memory of Variable Length—A Stochastic Model for Biological Neural Nets . Journal of Statistical Physics 151 896-921 . barticle

    work page 2013

  10. [10]

    , Peel , Leto L

    barticle [author] Hoffmann , Till T. , Peel , Leto L. , Lambiotte , Renaud R. Jones , Nick S. N. S. ( 2020 ). Community detection in networks without observing edges . Science Advances 6 eaav1478 . 10.1126/sciadv.aav1478 barticle

    work page doi:10.1126/sciadv.aav1478 2020

  11. [11]

    Rinaldo , Alessandro A

    barticle [author] Lei , Jing J. Rinaldo , Alessandro A. ( 2015 ). CONSISTENCY OF SPECTRAL CLUSTERING IN STOCHASTIC BLOCK MODELS . The Annals of Statistics 43 215--237 . barticle

    work page 2015

  12. [12]

    barticle [author] Lin , K. Z. K. Z. Lei , J. J. ( 2024 ). Dynamic clustering for heterophilic stochastic block models with time-varying node memberships . Arxiv . barticle

    work page 2024

  13. [13]

    Miele , Vincent V

    barticle [author] Matias , Catherine C. Miele , Vincent V. ( 2016 ). Statistical Clustering of Temporal Networks Through a Dynamic Stochastic Block Model . Journal of the Royal Statistical Society Series B: Statistical Methodology 79 1119-1141 . 10.1111/rssb.12200 barticle

    work page doi:10.1111/rssb.12200 2016

  14. [14]

    , Neeman , Joe J

    barticle [author] Mossel , Elchanan E. , Neeman , Joe J. Sly , Allan A. ( 2015 ). Reconstruction and estimation in the planted partition model . Probability Theory and Related Fields 162 431--461 . 10.1007/s00440-014-0576-6 barticle

    work page doi:10.1007/s00440-014-0576-6 2015

  15. [15]

    , Neeman , Joe J

    barticle [author] Mossel , Elchanan E. , Neeman , Joe J. Sly , Allan A. ( 2016 ). Belief propagation, robust reconstruction and optimal recovery of block models . The Annals of Applied Probability 26 2211 -- 2256 . 10.1214/15-AAP1145 barticle

    work page doi:10.1214/15-aap1145 2016

  16. [16]

    Reynaud-Bouret , Patricia P

    barticle [author] Ost , Guilherme G. Reynaud-Bouret , Patricia P. ( 2020 ). Sparse space-time models: Concentration Inequalities and Lasso . Annales de l'Institut Henri Poincaré (B) Probabilité et Statistique 56 2377-2405 . barticle

    work page 2020

  17. [17]

    barticle [author] Peixoto , Tiago P. T. P. ( 2019 ). Network Reconstruction and Community Detection from Dynamics . Phys. Rev. Lett. 123 128301 . 10.1103/PhysRevLett.123.128301 barticle

    work page doi:10.1103/physrevlett.123.128301 2019

  18. [18]

    Zhang , Teng T

    barticle [author] Pensky , Marianna M. Zhang , Teng T. ( 2019 ). Spectral clustering in the dynamic stochastic block model . Electronic Journal of Statistics 13 678 -- 709 . 10.1214/19-EJS1533 barticle

    work page doi:10.1214/19-ejs1533 2019

  19. [19]

    , Levina , Elizaveta E

    barticle [author] Zhao , Yunpeng Y. , Levina , Elizaveta E. Zhu , Ji J. ( 2012 ). Consistency of community detection in networks under degree-corrected stochastic block models . The Annals of Statistics 40 2266 -- 2292 . 10.1214/12-AOS1036 barticle

    work page doi:10.1214/12-aos1036 2012