acceptodds
Under review as a conference paper at ICLR 2027

Discretization-free exact recovery in geometric community detection

Abstract

Many graph-learning problems combine relational observations with continuous geometric side information, yet existing exact-recovery methods for geometric community detection propagate labels according to a fixed spatial discretization. We instead introduce an information-adaptive algorithm for the Geometric Hidden Community Model that operates directly on the observed geometry: at each step it labels the frontier vertex whose already labeled neighbors provide the strongest worst-case Hellinger evidence, so the propagation order is determined by statistical information rather than by a spatial mesh. This perspective also permits heterogeneous information across communities and distances: different community pairs may rely on different witness communities and different distance ranges. In particular, our condition covers canonical symmetric multi-community models, including the geometric stochastic block model, for which the previous all-witness condition fails whenever there are at least three communities. Under an explicit witness-connectivity condition and the known Chernoff–Hellinger information condition, we prove polynomial-time exact recovery; in the standard fully distinguishable regime, the sufficient boundary coincides with the information-theoretic threshold. Experiments show that information-adaptive ordering substantially reduces propagation errors relative to spatial and degree-based schedules, succeeds beyond the regime covered by our proof, and performs competitively with calibrated block propagation on a canonical geometric block-model benchmark.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
geometric community detection, exact recovery, graph learning, geometric graphs, message passing, spatial networks, information-theoretic thresholds, stochastic block models

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_SPwuOpenReview ↗
Rating
4(+2)
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
3
Read review
Paper summary

The paper considers exact recovery in the geometric stochastic blockmodel. In this model, we have a random geometric graph (vertices have positions and are connected if their distance is at most r) with edge weights (or interactions) drawn from some distribution that depends on the community labels of the endpoints and of the distance between the endpoints. They assume the model parameters are known (community label distribution, interaction distributions), assume the coordinates are observed and construct an algorithm for which they prove exact recovery under additional conditions. The conditions on the interaction distributions are more lenient than the conditions in prior work.

Critical strengths

The witness assumption is weaker than the one from prior work, and allows the guarantees to apply to a broader class of GSBM models.

The information-based propagation is elegant. The spatial discretization that prior work relies on throws away information, presumably to simplify the problem. This algorithm does not depend on such a simplification.

From their experiments, it seems that the algorithm works up until the information theoretical threshold.

Critical weaknesses

A large amount of parameter knowledge is assumed, which is unrealistic in practice. This is fine for such a theoretical paper. However, the paper could be a bit more transparent about this and add a few sentences to the discussion section.

The premise of the paper is nice and simple: geometric community detection without relying on discretization. However, it is motivated in a clumsy matter. They use a lot of space to argue why they do NOT discretize, while discretization obviously seems like a simplification. I think this comparison to the prior work that relies on discretization should be postponed until after the model is introduced.

There is a lot of LLM language in the introduction. In particular, some sentences have this typical AI style that I find frustrating to read. It's fine to use AI to assist with writing (I also do that), but focus on making the paper pleasant to read for humans. Here's a list of sentences that bothered me:

  • Lines 033-035, first sentence of the paper, very unnatural and hard to decipher
  • Lines 036-037
  • Line 045 "fixed geometric scaffold"
  • Paragraph headers on lines 048 and 059. In particular "propagate where the information is".
  • Line 201 "previews what this buys"
  • Lines 358-359 "Assumption 1 enters the analysis in two distinct ways, only one tied to discretization"

Later in the paper, the AI sentences become more infrequent. Again, I don't mind the fact that AI was used, but the resulting text is just very imprecise and hard to read.

In the introduction (line 040) edge-weights are introduced before introducing edges. It was unclear to me at this point that the underlying graph is simply a (community-agnostic) RGG and that the communities only affect the edge weight distributions.

Their main Algorithm A calls subroutines Algorithm 1-3 that are only described in the appendix. These subroutines seem to be crucial in understanding the paper, so it might be worth-while including them in the main text.

The weight-set X\mathbb X appears in Assumption 3 without being introduced.

McNemar's exact test and MAP are not explained.

Figure 2 is too cluttered: I don't see the line of Alg. A because of all the other lines. I don't see a legend item for the green squares with white border.

Questions for authors

Line 012 of the abstract: "Exact-recovery methods" seems to carry multiple things: an algorithm for which exact recovery is proven in some parameter regime?

Lines 048-053 use notation that is not yet introduced. Same for "Phase II" in line 089.

What is meant with "uniform" in the paragraph header on line 048?

Can't we fix λ=1\lambda=1 and rescale the other parameters of the model?

What is meant with "Any fixed t∈(0,1)t\in(0,1) would serve." in line 153?

2 comments

Thank you for highlighting the weaker witness assumption and information-based ordering, and for the detailed presentation comments. We have rewritten the opening, made Algorithm A self-contained and clarified the limitations.

Parameter knowledge. Known parameters are now explicit in the abstract and introduction (p. 1). Section 5 (p. 10) distinguishes known-law guarantees from estimated-law experiments. Proportions enter exhaustive MAP and optional final class naming, but are not needed by the practical pipeline for partition recovery (p. 7; Appendix D, p. 22).

Motivation and discretization. Section 1 (pp. 1–2) now explains spatial observations, the three-community example and the evidence available when assigning a label. The detailed "Relation to block propagation" discussion follows the guarantees in Section 3 (p. 7), including the distinction between operational blocks and auxiliary blocks used in the proof.

Language. We have rewritten the flagged passages and removed the expressions and headings you identified. The revised opening explains the model and selection rule directly (pp. 1–2), and the proof sketch states the assumptions' roles explicitly (p. 7).

Observation weights introduced before visible pairs. The introduction now explains that distance determines which pairs are observed, while communities affect the distribution of the edge indicator or weight (p. 1). Definition 1 formalizes this distinction (p. 3).

Subroutines appearing only in the appendix. Algorithm A now gives all three phases in the main text: the MAP objective, information-based selection and likelihood assignment, and synchronous refinement (p. 4).

Undefined observation space. Definition 1 introduces X\mathbb X, the edge-weight distributions and their densities before the assumptions (p. 3). Appendix F.1 supplies the measure conventions.

MAP and McNemar's test. MAP is explained at its first occurrence (p. 2). Section 4 explains McNemar's test through paired discordant outcomes (p. 7); Appendix B.2 gives the formula and the cautions about multiplicity and nonsignificance (pp. 14–15).

Cluttered figure. Figure 2 (p. 8) is redesigned: every method and the refinement-from-truth reference have legend entries, the legend notes that A and A-WC coincide in the banded model, and the regions and thresholds within the plotted range are marked.

Q1 — "Exact-recovery methods" in the abstract. The ambiguous phrase has been replaced by a direct statement of polynomial-time exact recovery under the stated conditions and known-parameter assumption (p. 1). Exact recovery is formally defined on p. 3.

Q2 — Premature notation and "Phase II." The opening now describes the model and witness example verbally (pp. 1–2). The three phases are introduced in Section 2 (p. 3) and written out in Algorithm A (p. 4).

Q3 — "Uniform" in the heading. The heading has been removed. The contributions and assumptions are stated explicitly on p. 2 and in Section 3 (pp. 4–6).

Q4 — Normalizing the intensity. Yes. Definition 1 now acknowledges this normalization (p. 3). Scaling coordinates by λ1/d\lambda^{1/d} gives unit intensity on a region of volume λn\lambda n; the visibility radius and kernel arguments must also be transformed consistently, including the logarithmic normalization. We retain λ\lambda as a density parameter.

Q5 — "Any fixed tt would serve." Equation (1) and Definition 2 (p. 3) distinguish the general affinity from our choice t=1/2t=1/2. The recovery guarantee extends to any fixed t∈(0,1)t\in(0,1), with tt-dependent constants and the minimum taken over ordered candidate-label pairs. We use 1/21/2 because its affinity is symmetric in its arguments. Changing tt can change the labeling order, as the text now states.

We would appreciate your reassessment of the presentation in light of the rewritten introduction, the self-contained Algorithm A and the redesigned Figure 2. Please let us know whether any of the specific clarity concerns remain unresolved.

I thank the authors for addressing my concerns. The presentation is much better now. I have increased my rating accordingly.

Reviewer_K8vUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies community detection in the Geometric Hidden Community Model (GHCM), introduced by Gaudio et al. (2025). Vertices are generated by a Poisson point process over a continuous spatial domain, their locations are observed, and the edge-weight distributions depend jointly on the latent community labels and the geometric distances between vertices. The goal is exact recovery of the community labels, up to permutations preserving the model parameters.

The proposed algorithm uses an adaptive vertex-level propagation rule. At each step, it evaluates every unlabeled frontier vertex according to the worst-case Hellinger-affinity information provided by its labeled visible neighbors. It selects the vertex with the largest available information, assigns its maximum-likelihood label, and updates the corresponding scores. Thus, geometry determines which evidence is available, while statistical information determines the propagation order. The complete algorithm combines this propagation procedure with local MAP initialization and a final likelihood-refinement step.

Under some technical assumptions, together with the known Chernoff–Hellinger information condition, the authors prove polynomial-time exact recovery. For fixed model parameters and unit-cost evaluations of the relevant statistical quantities, the propagation phase runs in O(nlog⁡2n)O(n\log^2 n) time with high probability.

Critical strengths
  1. The paper appears to be technically solid and proposes a new algorithm for a model originally introduced in the statistics literature.
Critical weaknesses
  1. My overall impression is that the model is somewhat specialized, and the paper does not make its broader significance sufficiently clear to readers unfamiliar with GHCM. I do not regard the use of a specialized probabilistic model as a weakness by itself. However, because I am not sufficiently familiar with GHCM to assess its broader importance, the paper needs to do more to establish why progress on this model is interesting beyond the immediate literature. A concrete application or a more intuitive comparison with the ordinary stochastic block model would help. Similarly, I found the question of whether propagation should follow a fixed geometric structure or available statistical information too abstract as a central motivation. The introduction should explain the concrete limitation it captures.

  2. I think the paper insufficiently accessible to readers who are not already familiar with GHCM. For example, the motivating discussion introduces the requirement Paw≠PbwP_{aw}\ne P_{bw} using the phrase “separated by every third community,” before adequately explaining what the distributions represent or why this requirement mattered in the previous analysis. Some assumptions also appear technical and tailored to the proof, at least from the current presentation. I would suggest to include a more thorough comparison with previous results in terms of scope of assumptions, results and intuitions.

  3. The complete theorem seems not a strict weakening of the previous theorem. The propagation condition is weaker, but the full assumption package introduces an additional initialization restriction. Therefore, the paper should not leave readers with the impression that its theorem simply subsumes the previous GHCM theorem.

Questions for authors
  1. How can one compare all assumptions with the previous GHCM theorem? Can you add a corollary for canonical symmetric models where witness connectivity follows automatically from the CH condition?

Minor comment:

  1. For references with published conference or journal versions, please include the publication venue and bibliographic details rather than citing only the arXiv version.
1 comment

Thank you for recognizing the technical contribution and identifying where the motivation and comparison with earlier results needed clarification.

W1 — Significance and abstract motivation. Section 1 (pp. 1–2) now starts with spatial-network examples and explains how geometry changes the SBM: observation availability depends on distance, neighborhoods overlap, and each vertex has only logarithmically many visible neighbors near the recovery threshold.

The three-community example (p. 2) makes the earlier limitation concrete: a third-community neighbor cannot distinguish the first two communities, violating the all-witness requirement. Corollary 5 (p. 6) covers this canonical model strictly above the CH boundary in d≥2d\ge2.

We distinguish the weaker witness condition, which enlarges the covered model class, from the adaptive rule's removal of the block-size parameter (Section 3, p. 7).

W2 — Accessibility and interpretation of the assumptions. The introduction explains observations before introducing witnesses and uses the three-community example before the formal assumptions (pp. 1–2). Table 1 (p. 6) compares CH information, pair separation, initialization, the shape of the laws and bounded likelihood ratios. The proof sketch (p. 7) explains their respective roles. Table 2 in Appendix A (p. 13) collects the notation.

W3 — Comparison of the complete theorem. Proposition 6 and Table 1 (p. 6), with proof in Appendix H.4 (p. 46), show that Gaudio and Jin's Assumptions 1–3, together with CH and their dimensional condition, imply all our assumptions, including initialization separation. Thus our theorem covers their achievability statement under Assumptions 1–3 in every dimension, with strict inclusion for k≥3k\ge3. In dimension one, their statement under Assumptions 1–3 and ours both require λr>1\lambda r>1.

We list initialization separation separately because our weaker witness condition no longer implies it. For completeness, our result does not subsume the additional one-dimensional statement in their arXiv full version (Theorem 2, second paragraph) under Assumptions 1, 2 and 4, CH, and ∣Ωπ,P∣=1|\Omega_{\pi,P}|=1.

Q1 — Complete assumption comparison and a symmetric corollary. Table 1 and Proposition 6 (p. 6) provide the complete comparison. Corollary 5 on the same page assumes d≥2d\ge2, positive proportions, bounded likelihood ratios, and within/between laws differing almost everywhere throughout the visibility interval. Its proof in Appendix H.3 (p. 46) uses D+(Pa∥Pb)≤πa+πbD_+(P_a\|P_b)\le\pi_a+\pi_b, so CH implies witness connectivity. Recovery therefore holds strictly above the CH boundary for this family, including constant symmetric geometric SBMs with arbitrary positive proportions and distinct p,q∈(0,1)p,q\in(0,1).

Minor comment — Published references. The bibliography now gives publication venues (e.g., Information and Inference, SODA 2024, ISIT 2026) and keeps arXiv links to full versions (References, pp. 11–12).

We would appreciate your reassessment of the paper's scope and contribution in light of the complete assumption comparison and the symmetric-model guarantee. Please let us know whether a substantive concern about this comparison remains.

Reviewer_ynmvOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

In this paper, the authors proposed an information-adaptive algorithm for exact recovery in geometric community detection. By selecting the frontier vertex with the strongest worst-case Hellinger evidence, the labels are propagated directly over the observed geometry. Theoretical analysis establishes polynomial-time exact recovery. Experimental results demonstrate reduced propagation errors compared with existing spatial and degree-based methods.

Critical strengths
  1. The theoretical analysis weakens the earlier all-witness requirement and covers important symmetric multi-community models. It also clearly states the regime in which the recovery boundary is sharp.
  2. The controlled schedule comparisons and lower-tail information diagnostics provide useful evidence for why the adaptive ordering reduces propagation errors.
Critical weaknesses
  1. The theoretical initializer uses exhaustive MAP search, whose polynomial exponent may be large. The practical initializer introduces a gap between the proven algorithm and an efficiently deployable implementation.
  2. The schedule advantages do not always persist after unrestricted refinement. Moreover, the model-based scores rely on distributional information, so practical sensitivity to estimated or misspecified parameters needs further attention.
Questions for authors
  1. Can the witness-connectivity condition be weakened for the adaptive algorithm, particularly in the empirically successful intermediate regime?
  2. Can the practical initialization procedure be given a recovery guarantee, and what is the full end-to-end runtime including initialization?
  3. How do final recovery accuracy and runtime compare under unrestricted refinement when community proportions and edge-distribution kernels are estimated rather than known?
2 comments

Thank you for highlighting the weaker witness condition, symmetric-model guarantees and controlled experiments. We have strengthened the initialization and runtime results and clarified the experimental limitations.

W1 — Exhaustive MAP initialization. Proposition 8 in Appendix D (pp. 21–22) proves that the covariance initializer recovers the initial partition with probability 1−o(1)1-o(1) in O((log⁡n)3)O((\log n)^3) time, without knowing p,qp,q or the proportions. This applies to the constant symmetric Bernoulli model with fixed parameters and d≥2d\ge2. Corollary 7 (p. 7) combines it with propagation and refinement to give whole-graph partition recovery above the CH boundary in O(nlog⁡2n)O(n\log^2 n) time. The full guarantee uses the true p,qp,q after initialization, as stated in Appendix D (p. 22). Fast initialization for general kernels remains open.

W2 — Gains after refinement and parameter sensitivity. Section 4.1 and Figure 2 (p. 8) now explicitly separate propagation errors from final recovery. In the long-range model at λ=1.55\lambda=1.55, all four orderings recover 97% after refinement, as does refinement started from the true labels of all vertices. We describe this as consistent with a limitation of that refinement step at this setting. Appendix B.3 and Table 6 (p. 15) restore the information diagnostic. At the same setting, average within-graph fifth percentiles are 6.40 nats for A, 5.56 for A-WC, 4.06 for informative degree and 3.36 for nearest-first. These differences accompany the propagation-error differences; they do not establish causation.

Parameter estimation is addressed under Q3.

Q1 — Weakening witness connectivity. The proof sketch in Section 3 (p. 7) explains how witness connectivity, through auxiliary blocks, ensures that some frontier vertex has information of order log⁡n\log n while local errors remain controlled. Algorithm A does not construct these blocks. Whether a direct argument using accumulated information could weaken the condition remains open (Section 5, p. 10). For the symmetric family of Corollary 5 (p. 6), whose within- and between-community laws differ almost everywhere throughout the visibility range, CH already implies witness connectivity in d≥2d\ge2; see Appendix H.3 (p. 46). Section 4.1 (p. 8) and Figure 5 in Appendix C.1 (p. 20) provide finite-sample evidence of recovery in the intermediate region. These experiments use true initial labels.

Q2 — Practical initialization and end-to-end runtime. The guarantee is given by Corollary 7 and Appendix D (pp. 7, 21–22). Tables 11–12 (p. 18), discussed in Appendix B.6, report complete inference times, including visible-pair construction, initialization, fitting, propagation and refinement. At 1.2λIT1.2\lambda_{\mathrm{IT}} and torus area n=8⋅104n=8\cdot10^4, median totals with inferred initial labels and estimated probabilities are 3.94 s for balanced proportions and 5.88 s for unequal proportions. Measurements use ten graphs per setting and one CPU core. Across the tested sizes, doubling nn multiplies the median total by 2.05–2.11.

Q3 — Estimated proportions and kernels: recovery and runtime. Proportions. The practical initializer, propagation and refinement do not use π\pi for partition recovery (Section 4, p. 7). Proportions only enter the MAP initializer.

Constant probabilities. Section 4.2 and Figure 3 (p. 9) cross true/inferred initial labels with known/estimated p,qp,q. Holding initial labels fixed, no known-versus-estimated recovery difference is significant (Table 5, p. 15). This does not establish equivalence. At 1.2λIT1.2\lambda_{\mathrm{IT}}, balanced recovery is 99–100%; unequal recovery is 99% with true initial labels and 98% with inferred labels. Median total runtimes differ by less than 2% (Table 12, p. 18).

Distance-dependent kernels. Appendix B.4 (pp. 15–17) compares ten- and sixty-bin estimates fitted in the initial region and held fixed through propagation and refinement. A and nearest-first share each fit. In the long-range model at λ=1.55\lambda=1.55, A recovers 82% of graphs with ten bins and 97% with sixty, against 97% with the known kernel; in the banded model at λ=0.42\lambda=0.42, it recovers 100% with ten bins and 93% with sixty, against 99%. Figure 4 (p. 10) and Tables 7–9 (pp. 16–17) give all settings and paired comparisons. The sixty-bin grid aligns with the generating kernels' discontinuities, but finer resolution is not uniformly better.

For Algorithm A, Appendix B.6 and Table 13 (p. 19) give median within-graph estimated/known runtime ratios of 1.17–1.19 for the banded model and 1.54–1.57 for the long-range model. These ten-graph timing comparisons include preprocessing, fitting, propagation and refinement, but exclude recovering the supplied true initial labels.

We hope the new guarantee and runtime results address your main concerns.

I thank the author for responding to my concerns and questions. I will keep my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the reviewers for their constructive comments and have revised the manuscript accordingly.

Proposition 6 and Table 1 (p. 6) show that Gaudio and Jin's Assumptions 1–3, together with CH and their dimensional condition, imply all our assumptions, with strict inclusion for k≥3k\ge3.

Corollary 5 (p. 6) establishes recovery above the CH boundary in d≥2d\ge2 for canonical symmetric models, including the three-community geometric SBM.

Corollary 7 and Appendix D provide a fast initializer and an O(nlog⁡2n)O(n\log^2 n) end-to-end partition-recovery guarantee for the constant symmetric Bernoulli model in d≥2d\ge2, using known probabilities after initialization.

The experiments now include fixed ten-/sixty-bin kernel estimates and their runtime comparison (Figure 4; Appendices B.4 and B.6).

We have also rewritten the motivation and model explanation, made Algorithm A self-contained, and redesigned Figure 2. The individual responses below refer to the revised manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.