Sharp exact recovery threshold for two-community Euclidean random graphs

Charlie K. Guan; Julia Gaudio

REVIEW 3 major objections 5 minor 1 cited by

Sharp exact recovery threshold for two-community Euclidean random graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read In the two-community Geometric Hidden Community Model, exact recovery is achievable in linear time whenever the Chernoff-Hellinger threshold is crossed, removing the distinctness-of-distributions assumption.

desk verdict A real advance on a 2024 conjecture, but the Gaussian branch of the key lemma needs a proof, not a one-line MGF claim. read the letter →

arxiv 2501.14830 v1 pith:WSKOPDXO submitted 2025-01-22 cs.SI math.PR

Julia Gaudio , Charlie K. Guan This is my paper · ORCID

classification cs.SImath.PR MSC 05C8060D0562H30

keywords exactrecoveryGeometricHiddenCommunityModelEuclideanrandomgraphsChernoff-Hellingerdivergenceplanteddensesubgraphsubmatrixlocalizationlinear-timealgorithmstochasticblock

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper establishes that the information-theoretic threshold for exact recovery in the two-community Geometric Hidden Community Model (GHCM) is sharp: when $\lambda\nu_d\min_{i\neq j}D^+(\theta_i,\theta_j)>1$, a linear-time two-phase algorithm recovers every vertex's label with high probability. This removes the 'distinctness-of-distributions' assumption that earlier achievability results required, under a bounded log-likelihood ratio or Gaussian edge distributions. The result matters because the same model covers geometric planted dense subgraph and submatrix localization, problems in which the distinctness assumption fails, so the threshold now characterizes exact recovery for a broad class of spatial inference problems. The proof works by first producing an almost-exact labeling through a data-driven exploration of a block-level visibility graph, then refining it with a genie-aided-style MAP step.

What carries the argument

The central object is the $C^\star$-visibility graph, the coarsening of the vertex-level visibility graph obtained by restricting to planted-community vertices and grouping them into blocks of volume $\chi\log n$, with an edge between blocks when every pair of points is mutually visible. Its connectivity above the threshold lets the algorithm replace a fixed exploration order with a data-driven one: a block is labeled only after receiving a propagated labeling from an already-labeled neighbor, and it is added to the active set only if enough of its vertices are estimated to be planted. The propagation step's error control rests on Lemma 4.1, which gives a polynomial $n^{-b}$ bound on single-vertex misclassification under either a bounded log-likelihood ratio $\log(p_{12}/p_{11})<\eta$ or Gaussian $P_{ij}$.

What would settle it

Take a two-community GHCM with $\lambda\nu_d\min_{i\neq j}D^+(\theta_i,\theta_j)>1$ but with unbounded log-likelihood ratio and non-Gaussian $P_{ij}$ (for instance, heavy-tailed edge densities), run the two-phase algorithm, and measure the misclassification probability. If the per-vertex error does not decay polynomially in $n$ or exact recovery fails with non-vanishing probability, the sharp threshold claim for the full two-community GHCM is refuted.

Watch

Extended reading notes

Core claim

Above the threshold $\lambda\nu_d\min_{i\neq j}D^+(\theta_i,\theta_j)>1$, the algorithm's Phase I labels almost all vertices correctly by propagating labels along connected occupied blocks of the planted community, without knowing in advance which blocks contain planted vertices. The $C^\star$-visibility graph formed by the planted vertices is connected with high probability, so a breadth-first exploration discovers every block that contains many planted vertices; per-vertex misclassification probability decays polynomially, and the total fraction of wrongly labeled vertices vanishes. Phase II then refines the almost-exact labeling with a MAP estimator that treats the Phase I labels as ground truth; this refinement needs no distinctness assumption and yields exact recovery. Consequently the earlier impossibility threshold is also an achievability threshold for the two-community GHCM under the stated conditions.

Load-bearing premise

The sharpness proof rests on Lemma 4.1's polynomial per-vertex error decay, which is established only when the log-likelihood ratio $\log(p_{12}/p_{11})$ is bounded by $\eta$ or all $P_{ij}$ are Gaussian, and whose proof is deferred to the authors' earlier preprint rather than derived in this paper; if neither condition holds, the two-community threshold is not proven.

Editorial extensions

If this is right

Geometric planted dense subgraph and submatrix localization become exactly recoverable in linear time above their respective Chernoff-Hellinger thresholds, even though the background and cross distributions coincide.
The threshold $\lambda\nu_d\min_{i\neq j}D^+(\theta_i,\theta_j)=1$ is not just an impossibility bound for two-community GHCM: it is the exact recovery threshold whenever the bounded-LLR or Gaussian condition holds.
A single generic two-phase algorithm solves any two-community GHCM meeting these assumptions, so no problem-specific recovery scheme is required.
Almost exact recovery already holds under the weaker condition $\pi_1\lambda\nu_d>1$, independent of distinctness.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The block-exploration idea suggests a route to $k\geq 3$ communities by tracking the subgraph of communities that are distinguishable from a given pair; the paper notes that logical interdependencies between communities would require new ideas, so this is an extrapolation rather than a claim.
The bounded-LLR condition is likely replaceable by a moment or tail condition on the log-likelihood ratio; the Gaussian case shows the proof mechanism can tolerate unbounded ratios with sufficient tail decay.
Because the argument uses only visibility connectivity and Poisson concentration, it probably transfers to binomial point-process versions of the model, though the paper does not discuss that variant.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague, this is a genuine step past [3]. It removes the distinctness-of-distributions assumption for k=2 and introduces a data-driven block exploration in Phase I, which seems like the right way to find the C-star-connected component without knowing labels. The two-phase structure (almost exact then refine) is coherent, and the claim that Phase II works without distinctness is plausible and consistent with the earlier argument. The threshold sharpness result for the two-community GHCM, modulo the distributional assumptions, is solid progress and worth taking seriously.

The main soft spot is where the stress-test points. Lemma 4.1 drives the n^{-9/8} union bound, and its proof is not in the paper. For the bounded log-likelihood case it is a citation to [3, Lemma D.7] plus an "adaptation." For the Gaussian case, the text says log(p12/p11) is Gaussian and hence the expectation is an MGF. That is only true when P11 and P12 share a variance. In the general Gaussian case, the log ratio is a quadratic form, not Gaussian, so the displayed tail bound is not established by that sentence. This matters because the Gaussian case is one of two regimes in which Theorem 2.1 is claimed, and removing distinctness is the paper's contribution. If the quadratic tail can be controlled (likely, perhaps by diagonalizing the quadratic form or by assuming equal variances), the theorem stands; but as written it does not.

The reliance on the authors' own unpublished preprint [3] is heavy but not inherently illegitimate, since this is a direct extension of that framework. Still, a referee cannot verify Lemma 4.1 without chasing another arXiv preprint, and the new adaptation should at least be sketched. The citation pattern is honest: the paper openly says the conjecture comes from [3] and the proof builds on it.

Who should read this: people working on geometric SBM, planted dense subgraph, and submatrix localization. The data-driven exploration idea may be reusable, and the paper does a good job of explaining why the old tree-search order fails without distinctness.

My recommendation: send it to peer review, but do not accept it as is. Ask for a real proof of the Gaussian case of Lemma 4.1, and make the bounded-LLR case self-contained enough that the main theorem does not rest entirely on an unpublished citation. This is likely fixable, and if fixed, it is a solid paper.

Referee Report

3 major / 5 minor

Summary. The paper studies the two-community Geometric Hidden Community Model (GHCM), in which community 1 (C⋆) has internal-edge distribution P11 and all other pairs have distribution P12 = P21 = P22. The authors propose a two-phase, linear-time algorithm. Phase I constructs an almost exact labeling by exploring the C⋆-visibility graph in a data-driven manner; Phase II refines this labeling with a genie-aided estimator that replaces the true labels by the Phase I estimates. Theorem 2.1 claims exact recovery above the Chernoff–Hellinger threshold λνd D+(θ1,θ2) > 1 without the distinctness-of-distributions assumption, under either a bounded log-likelihood-ratio condition or Gaussian Pij. The proof imports connectivity, MAP-estimation, and Phase II refinement results from the companion preprint [3] and derives a per-vertex error bound in Lemma 4.1 that underpins the union bound of Phase I.

Significance. If correct, the result sharpens the exact-recovery threshold for the two-community GHCM, confirms the conjecture that the distinctness assumption is unnecessary in this setting, and extends achievability to geometric planted dense subgraph and submatrix localization problems. The algorithmic idea is appealing: the search order of the visibility graph is data-driven rather than fixed a priori, and the runtime is linear in the number of edges. The paper is clearly structured and gives a concrete proof roadmap. However, the central per-vertex error bound in Lemma 4.1 is not fully established in the manuscript. The bounded-LLR case is only a citation to the authors' own unpublished preprint [3], and the Gaussian case contains a mathematical error: the log-likelihood ratio of two Gaussians with unequal variances is a quadratic form, not a Gaussian random variable. Since the n^{-9/8} union bound and the almost-exact-recovery guarantee rest entirely on Lemma 4.1, this gap is load-bearing for the main theorem.

major comments (3)

[Section 4.2, Lemma 4.1(ii)] The proof of the Gaussian case is mathematically incorrect as written. For P11=N(μ1,σ1^2) and P12=N(μ2,σ2^2), the log-likelihood ratio log(p12(y)/p11(y)) is a quadratic polynomial in y, not a Gaussian random variable, unless σ1=σ2. Even in the equal-variance case, the ratio is a linear function of y and therefore unbounded, so the constant η in the displayed bound (4.3) does not exist. The sentence 'the expectation is the moment-generating function of a Gaussian' does not apply to a quadratic form; when the quadratic coefficient is positive, the expectation of exp(t·log(p12/p11)) may be infinite for some t. The reference to [3, Appendix G] does not supply the missing derivation. Because Theorem 2.1 explicitly claims the result for all Gaussian Pij (including unequal variances), the polynomial error decay in Lemma 4.1 is not established for that case, and the sharp threshold is not proven for the full Gaussian family. The authors should either provide a rigorous tail bound for sums of such quadratic log-likelihood-ratio terms or restrict the theorem statement to a class for which the bound can be proven (e.g., equal variances).
[Section 4.2, Lemma 4.1(i) and Section 3.2] The key per-vertex error bound that drives Phase I is not derived in this paper. For the bounded-LLR case, Lemma 4.1 is proved only by citing [3, Lemma D.7] as a 'straightforward adaptation'; for the Gaussian case, it cites [3, Appendix G]. The Phase II refinement is likewise imported from [3, Theorem E.3]. Since [3] is an unpublished preprint by two of the present authors, the main theorem is not self-contained and the reader cannot independently verify the central estimate. This is a formal gap, not merely a stylistic one: the n^{-9/8} union bound and the subsequent almost-exact-recovery proof in Theorem 3.2 depend entirely on Lemma 4.1. The authors should include the statement and proof of the adapted bound (or at least a precise statement with explicit dependence on η, δ, and M) in an appendix, or clearly state that the main result is conditional on the companion preprint.
[Theorem 2.1 and Proposition 3.1] The theorem claims exact recovery whenever λνd min_{i≠j} D+(θi,θj) > 1, but the proof of Proposition 3.1 uses the condition only to show π1λνd > 1. The step from the CH threshold to π1λνd > 1 is correct because P12=P22, but the connectivity of the C⋆-visibility graph is then asserted by replacing λ′ with π1λ in the visibility-graph connectivity theorem of [3, Appendix C]. This is another imported result that is not proved here. If the connectivity claim in [3] has hidden assumptions (e.g., about χ and δ), those assumptions need to be stated explicitly in the present paper, since Proposition 3.1 is essential for the exploration process to visit all C⋆-occupied blocks.

minor comments (5)

[Title] The title contains a spacing artifact: 'Euclidea n' should be 'Euclidean'.
[Inequality (4.1)] The display for condition (4.1) is garbled: the first line appears to be an inequality involving ν_d (1−3√d χ^{1/d}/2)^d and (ν_d + 1/λ′)/2, while the second line is a separate bound 0 < χ < (ν_d − 1/λ′)/2. Please reformat to make the conditions on χ and the two inequalities clear.
[Definition 2.1] The definition of the model assumes a common support for the densities pij; if the supports differ, terms like log(p12/p11) may be infinite, which is not addressed in the statement of assumption (i) in Theorem 2.1.
[Algorithm 2, Line 12] The call to Propagate on input (G, Vi, Vj) assumes that Vi and Vj are mutually visible; this follows from the definition of N(Bi), but it would be helpful to state that explicitly when the procedure is invoked.
[Proof of Theorem 3.2] The Bernoulli inequality step gives (1−γn^{-9/8})^{n/(χ log n)} ≥ 1−γn^{-1/8}/(χ log n), which is valid only for n large enough that the left-hand base is in [0,1]; the phrase 'for large enough n' covers this, but the condition could be stated explicitly.

Circularity Check

2 steps flagged · score 5.0 of 10

Main theorem's Phase I error bound is imported from the authors' own unpublished preprint, with the Gaussian case resting on an unsupported assertion; the new exploration rule is genuine but the sharp-threshold claim is not self-contained.

self citation load bearing [Section 4.2, Lemma 4.1 proof (bounded-LLR case)]
"Under assumption (i), a straightforward adaptation of [3, Lemma D.7] gives that P_{i,z}(\hat{x}(u_{ij}) \neq x^\star(u_{ij})) \leq \phi^{\delta/2 \log n - M} e^{\eta M} = (e^\eta/\phi)^M n^{-\delta \log(1/\phi)/2}."

This is the engine of Phase I: the per-vertex misclassification probability that the union bound over all blocks converts into almost exact recovery. The paper does not prove the bound; it cites Lemma D.7 of [3], a preprint by the same authors (Gaudio and Guan). The rest of Theorem 2.1 in case (i) therefore reduces, at the load-bearing step, to an unverified self-citation rather than a derivation contained in this paper.
other [Section 4.2, Lemma 4.1 proof (Gaussian case)]
"Under assumption (ii), observe that log(p12(yuijv)/p11(yuijv)) is a Gaussian and hence the expectation is the moment-generating function of a Gaussian that can be bounded following similar derivations in [3, Appendix G] to yield a similar bound as (4.3)."

The Gaussian-case bound is asserted, not proved. For general Gaussian P11=N(mu1,sigma1^2) and P12=N(mu2,sigma2^2), log(p12/p11) is quadratic in y unless sigma1=sigma2, so it is not a Gaussian random variable and the Gaussian MGF argument cited from [3, Appendix G] does not apply. Thus the Phase I tail bound is unsupported for the Gaussian regime that Theorem 2.1 claims to cover; the conclusion is imported from the same authors' prior work by an analogy that is not established.

full rationale

The paper's new contribution is a data-driven Phase I exploration procedure, and the proof that all C*-occupied blocks are visited does not simply rename an existing fit or normalize by a fitted parameter. However, the derivation chain for Theorem 2.1 is not self-contained: Proposition 3.1 is obtained by applying the visibility-graph connectivity theorem of [3, Appendix C]; the initial MAP block is guaranteed by [3, Theorem D.2]; the block-size bound is [3, Lemma D.1]; the Phase II refinement is [3, Theorem E.3]; and the crucial per-vertex error bound of Lemma 4.1 is 'a straightforward adaptation of [3, Lemma D.7]' in the bounded-LLR case and an unproved Gaussian-MGF assertion plus citation in the Gaussian case. All of these are from the authors' own unpublished preprint, so the sharp-threshold claim is load-bearing on self-citation. The Gaussian-case statement is also technically inaccurate as written, because the log-likelihood ratio of two unequal-variance Gaussians is a quadratic form, not a Gaussian; this makes the cited bound inapplicable. Because the exploration rule itself is a genuine algorithmic idea and the cited lemmas, if valid, would imply the theorem, this is not a fully circular derivation; but the central result is not established independently of the same-author preprint and is partially unproven in the Gaussian regime. Score set to 5.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central claim rests on several imported theorems from the authors' own prior preprint [3], which are not independently verified here. Algorithmic constants (chi, delta, epsilon0, M) are proof parameters, not fitted values. No new physical entities are postulated.

free parameters (4)

block volume constant chi = small constant satisfying (4.1)
Introduced to define the block partition; the proof requires chi small enough. Not fitted to data; existence suffices.
occupancy threshold delta = small constant satisfying (4.2)
Defines delta-occupied blocks and the C-star-identified threshold delta/2. Chosen for the proof; not fitted.
MAP sample size epsilon0 = at most min{1/(2 log 2), delta}
Size of the initially labeled subset V0. Chosen for linear runtime and the proof; not fitted.
error budget M = 5/(4b)
Used to define successful propagation events; derived from the Chernoff bound. Not a data fit.

assumptions (5)

domain assumption P21 = P22, so community 2 is indistinguishable from background and P11 differs from P12
Restricts the model to the case where distinctness fails, stated in Section 2. This is the nontrivial planted-community case.
domain assumption Either log(p12/p11) is bounded by eta, or all Pij are Gaussians
Assumption in Theorem 2.1 required for the per-vertex error bound in Lemma 4.1.
ad hoc to paper Connectivity of the (chi, delta)-visibility graph for a Poisson process with intensity lambda' nu_d > 1 (from [3, Appendix C])
The proof of Proposition 3.1 invokes this self-cited theorem to show the C-star visibility graph is connected with high probability.
ad hoc to paper MAP achieves exact recovery on the initial subset V0 (from [3, Theorem D.2])
The algorithm assumes the initial block labeling is correct with high probability, imported from the authors' prior preprint.
ad hoc to paper Phase II refinement succeeds when Phase I has few errors (from [3, Theorem E.3])
The exact recovery step relies on this imported theorem, which does not require the distinctness assumption.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sharp exact recovery threshold for two-community Euclidean random graphs." pith.science (2026). https://pith.science/paper/WSKOPDXO

@misc{pith2026250114830,
  author       = {Pith},
  title        = {Pith review of: Sharp exact recovery threshold for two-community Euclidean random graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WSKOPDXO}},
  note         = {Machine review of arXiv:2501.14830}
}

read the original abstract

This paper considers the problem of label recovery in random graphs and matrices. Motivated by transitive behavior in real-world networks (i.e., ``the friend of my friend is my friend''), a recent line of work considers spatially-embedded networks, which exhibit transitive behavior. In particular, the Geometric Hidden Community Model (GHCM), introduced by Gaudio, Guan, Niu, and Wei, models a network as a labeled Poisson point process where every pair of vertices is associated with a pairwise observation whose distribution depends on the labels and positions of the vertices. The GHCM is in turn a generalization of the Geometric SBM (proposed by Baccelli and Sankararaman). Gaudio et al. provided a threshold below which exact recovery is information-theoretically impossible. Above the threshold, they provided a linear-time algorithm that succeeds in exact recovery under a certain ``distinctness-of-distributions'' assumption, which they conjectured to be unnecessary. In this paper, we partially resolve the conjecture by showing that the threshold is indeed tight for the two-community GHCM. We provide a two-phase, linear-time algorithm that explores the spatial graph in a data-driven manner in Phase I to yield an almost exact labeling, which is refined to achieve exact recovery in Phase II. Our results extend achievability to geometric formulations of well-known inference problems, such as the planted dense subgraph problem and submatrix localization, in which the distinctness-of-distributions assumption does not hold.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery
cs.SI 2025-01 conditional novelty 6.0 of 10

Exact node matching and community recovery in correlated stochastic block models with correlated attributes are possible when the edge-correlation SNR plus the attribute-correlation SNR exceeds a logarithmic threshold.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages · cited by 1 Pith paper

[3]

Exact label recovery in euclidean random graphs, 2024

Julia Gaudio, Charlie Guan, Xiaochun Niu, and Ermin Wei. Exact label recovery in euclidean random graphs, 2024

work page 2024
[1]

Higher-order spectral clus- tering for geometric graphs

Konstantin A vrachenkov, Andrei Bobu, and Maximilien Dre veton. Higher-order spectral clus- tering for geometric graphs. Journal of Fourier Analysis and Applications , 27(2):22, 2021

work page 2021
[2]

The geometric block model

Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Ba rna Saha. The geometric block model. In Proceedings of the AAAI Conference on Artiﬁcial Intelligen ce, volume 32, 2018

work page 2018
[4]

Exact communi ty recovery in the geometric sbm

Julia Gaudio, Xiaochun Niu, and Ermin Wei. Exact communi ty recovery in the geometric sbm. Symposium on Discrete Algorithms (SODA) , 2024

work page 2024
[5]

Stochastic blockmodels: First steps

Paul W Holland, Kathryn Blackmond Laskey, and Samuel Lein hardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109–137, 1983

work page 1983
[6]

Mathew D. Penrose. The longest edge of the random minimal spanning tree. The Annals of Applied Probability, 7(2):340 – 361, 1997

work page 1997
[7]

Spread of information through a popula tion with socio-structural bias: I

Anatol Rapoport. Spread of information through a popula tion with socio-structural bias: I. Assumption of transitivity. The Bulletin of Mathematical Biophysics , 15:523–533, 1953

work page 1953
[8]

Community d etection on Euclidean random graphs

Abishek Sankararaman and François Baccelli. Community d etection on Euclidean random graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Al- gorithms, pages 2181–2200. SIAM, 2018. 10

work page 2018

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [3]

Exact label recovery in euclidean random graphs, 2024

Julia Gaudio, Charlie Guan, Xiaochun Niu, and Ermin Wei. Exact label recovery in euclidean random graphs, 2024

work page 2024

[2] [1]

Higher-order spectral clus- tering for geometric graphs

Konstantin A vrachenkov, Andrei Bobu, and Maximilien Dre veton. Higher-order spectral clus- tering for geometric graphs. Journal of Fourier Analysis and Applications , 27(2):22, 2021

work page 2021

[3] [2]

The geometric block model

Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Ba rna Saha. The geometric block model. In Proceedings of the AAAI Conference on Artiﬁcial Intelligen ce, volume 32, 2018

work page 2018

[4] [4]

Exact communi ty recovery in the geometric sbm

Julia Gaudio, Xiaochun Niu, and Ermin Wei. Exact communi ty recovery in the geometric sbm. Symposium on Discrete Algorithms (SODA) , 2024

work page 2024

[5] [5]

Stochastic blockmodels: First steps

Paul W Holland, Kathryn Blackmond Laskey, and Samuel Lein hardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109–137, 1983

work page 1983

[6] [6]

Mathew D. Penrose. The longest edge of the random minimal spanning tree. The Annals of Applied Probability, 7(2):340 – 361, 1997

work page 1997

[7] [7]

Spread of information through a popula tion with socio-structural bias: I

Anatol Rapoport. Spread of information through a popula tion with socio-structural bias: I. Assumption of transitivity. The Bulletin of Mathematical Biophysics , 15:523–533, 1953

work page 1953

[8] [8]

Community d etection on Euclidean random graphs

Abishek Sankararaman and François Baccelli. Community d etection on Euclidean random graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Al- gorithms, pages 2181–2200. SIAM, 2018. 10

work page 2018