- 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 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 and rescale the other parameters of the model?
What is meant with "Any fixed would serve." in line 153?
2 comments
I thank the authors for addressing my concerns. The presentation is much better now. I have increased my rating accordingly.
Response
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, 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 gives unit intensity on a region of volume λn; the visibility radius and kernel arguments must also be transformed consistently, including the logarithmic normalization. We retain λ as a density parameter.
Q5 — "Any fixed t would serve." Equation (1) and Definition 2 (p. 3) distinguish the general affinity from our choice t=1/2. The recovery guarantee extends to any fixed t∈(0,1), with t-dependent constants and the minimum taken over ordered candidate-label pairs. We use 1/2 because its affinity is symmetric in its arguments. Changing t 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.