{"id":"32d35d54-0c1c-418a-94c9-703570e44efc","arxiv_id":"2501.14830","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"For two-community geometric hidden community models, exact recovery is achievable above the Chernoff-Hellinger threshold even without the distinctness-of-distributions assumption, via a two-phase linear-time algorithm.","lead":"This paper proves that the exact-recovery threshold for two-community geometric random graphs is tight, by giving a linear-time algorithm that works even when one community's edge distributions are identical to the background. The result extends exact recovery to geometric versions of planted dense subgraph and submatrix localization problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.1's Gaussian case is not proven: for unequal variances log(p12/p11) is quadratic, not Gaussian, so the polynomial error decay underpinning Phase I lacks a valid derivation.","rationale":"The reader's weakest assumption identifies the same load-bearing object, Lemma 4.1, and the same underlying risk: the paper does not actually derive the error bound on which Phase I depends. I agree that conditional acceptance is appropriate. However, I find a sharper, more concrete defect than 'deferred proof': in the Gaussian case with unequal variances, the proof says log(p12/p11) is a Gaussian, which is false; the log-ratio is quadratic. This means the displayed bound (4.3) cannot be obtained by the stated argument, and the theorem's Gaussian clause is not established by the text as written. This reinforces the reader's CONDITIONAL verdict: the result is plausible and likely repairable, especially for the equal-variance submatrix-localization case, but the manuscript needs a complete derivation of Lemma 4.1 before the main claim can be accepted. I set verdict_should_be to UNCHANGED because my read does not move the reader's verdict; it sharpens the same concern.","tokens_in":8835,"tokens_out":21211,"duration_ms":216581,"concrete_test":"Independently derive Lemma 4.1 for the unequal-variance Gaussian case, e.g. P11=N(0,1), P12=N(0,sigma^2) with sigma != 1. Compute the large-deviation rate of the per-vertex score sum and verify that the per-vertex error probability is at most a*n^{-b} with b>0 independent of n, and that the subsequent n^{-9/8} union bound survives. In particular, check whether the MGF of log(p12/p11) under both true labels is finite on an interval containing the value needed for the Chernoff argument; if for some sigma the rate is 0 or the MGF is infinite, Theorem 2.1's Gaussian clause is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on Lemma 4.1, the per-vertex error bound that drives the n^{-9/8} union bound in Phase I. The proof of the bounded-LLR case is only a citation to the authors' unpublished preprint [3], so the main theorem is not self-contained. More seriously, the Gaussian case as written is mathematically inaccurate: for general Gaussian P11=N(mu1,sigma1^2) and P12=N(mu2,sigma2^2), log(p12/p11) is a quadratic function of y unless sigma1=sigma2, not a Gaussian random variable. The displayed bound (4.3) is derived using a uniform constant eta ('bounded log-likelihood'), which does not exist for unequal-variance Gaussians, and the 'expectation is the moment-generating function of a Gaussian' argument cannot be applied directly to a quadratic form. Consequently, Theorem 2.1's claim for arbitrary Gaussian Pij rests on an unproved tail bound for sums of such quadratic log-likelihood ratio terms. If that tail bound has zero or non-uniform rate in some parameter regime, Phase I's error control collapses and sharp recovery is not established. This is load-bearing because removing the distinctness assumption is the paper's main contribution, and the Gaussian case is one of only two distributional regimes in which the theorem is claimed.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9192,"tokens_out":6769,"duration_ms":67236,"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":[{"comment":"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":"Section 4.2, Lemma 4.1(ii)"},{"comment":"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.","section":"Section 4.2, Lemma 4.1(i) and Section 3.2"},{"comment":"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.","section":"Theorem 2.1 and Proposition 3.1"}],"minor_comments":[{"comment":"The title contains a spacing artifact: 'Euclidea n' should be 'Euclidean'.","section":"Title"},{"comment":"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.","section":"Inequality (4.1)"},{"comment":"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.","section":"Definition 2.1"},{"comment":"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.","section":"Algorithm 2, Line 12"},{"comment":"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.","section":"Proof of Theorem 3.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's main theorem rests on several key results that are not proved in the paper but are taken from the authors' own preprint [3]. While importing from a companion paper is sometimes acceptable, the Gaussian case of the central Lemma 4.1 is not merely deferred but is mathematically inaccurate as stated. The error is likely fixable by a proper large-deviation argument for quadratic forms, but in its current form the paper does not establish the theorem for general Gaussian Pij. The editor might consider whether the paper should be paired with [3] in the review process, and whether the claimed 'sharp threshold' should be stated as conditional on the companion preprint until the deferred proofs are publicly available. The algorithmic idea and the data-driven exploration are interesting, and the applications to PDS and submatrix localization are valuable, but the technical core needs substantial revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nWho 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.\n\nMy 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.","headline":"A real advance on a 2024 conjecture, but the Gaussian branch of the key lemma needs a proof, not a one-line MGF claim.","tokens_in":9639,"tokens_out":2526,"would_cite":false,"duration_ms":28178,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","60D05","62H30"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["exact recovery","Geometric Hidden Community Model","Euclidean random graphs","Chernoff-Hellinger divergence","planted dense subgraph","submatrix localization","linear-time algorithm","stochastic block model"],"falsifier":"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.","tokens_in":8630,"feed_emoji":"🧩","tokens_out":11953,"duration_ms":100202,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exact recovery threshold sharp for two-community geometric graphs","feed_subtitle":"A linear-time two-phase algorithm recovers labels exactly above the threshold, no distinctness needed.","key_machinery":"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}$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the GHCM, proves the impossibility side of the threshold, provides the Phase II refinement, and supplies the per-vertex error estimates (Lemma D.7, Appendix G) that Lemma 4.1 adapts.","marker":"[3]"},{"why":"Supplies the connectivity bound for the vertex visibility graph of the planted Poisson process, which Proposition 3.1 coarsens to the C-star visibility graph.","marker":"[6]"},{"why":"Establishes the sharp threshold in the Geometric SBM, the baseline special case that the GHCM generalizes.","marker":"[4]"},{"why":"Proposes the Geometric SBM and gives an earlier recoverability result that the sharper threshold refines.","marker":"[8]"}],"fun_headline_variants":["Sharp threshold: exact recovery without distinctness assumption","Linear-time exact recovery at the sharp threshold","Two-community graphs: exact recovery threshold is sharp","No distinctness needed: exact recovery in geometric graphs","Two-phase linear-time algorithm hits sharp exact recovery threshold"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sharp threshold: exact recovery without distinctness assumption","Linear-time exact recovery at the sharp threshold","Two-community graphs: exact recovery threshold is sharp","No distinctness needed: exact recovery in geometric graphs","Two-phase linear-time algorithm hits sharp exact recovery threshold"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000841,"raw_usage":{"total_tokens":3682,"prompt_tokens":977,"completion_tokens":2705,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":593,"completion_tokens_details":{"reasoning_tokens":2632}},"tokens_in":593,"tokens_out":2705,"duration_ms":20129,"temperature":1.0,"reasoning_tokens":2632,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:19:07.585081+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Exact label recovery in euclidean random graphs, 2024","cited_arxiv_id":null,"evidence_quote":"Defines the GHCM, proves the impossibility side of the threshold, provides the Phase II refinement, and supplies the per-vertex error estimates (Lemma D.7, Appendix G) that Lemma 4.1 adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the connectivity bound for the vertex visibility graph of the planted Poisson process, which Proposition 3.1 coarsens to the C-star visibility graph."},{"cited_title":"Exact communi ty recovery in the geometric sbm","cited_arxiv_id":null,"evidence_quote":"Establishes the sharp threshold in the Geometric SBM, the baseline special case that the GHCM generalizes."},{"cited_title":"Community d etection on Euclidean random graphs","cited_arxiv_id":null,"evidence_quote":"Proposes the Geometric SBM and gives an earlier recoverability result that the sharper threshold refines."}],"review_version":1}