{"id":"e25a2b6a-2611-4978-b214-6b15ad292fcc","arxiv_id":"2508.00893","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For soft geometric block models with k communities, an algorithm using the k-1 eigenvalues closest to a model-dependent value, followed by k-means and local refinement, recovers all communities with vanishing error.","lead":"This paper proves that a spectral clustering method can recover all k hidden groups in a soft geometric block model, a random graph where edges depend on both group labels and node positions. It extends a known two-community guarantee to any fixed number of communities, with errors shrinking to zero as the graph grows.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.4's key bound is unproven: the proof equates (A-Bσ)U with (A-EA)U, and applies Chernoff to row sums that are not unconditionally independent.","rationale":"The reader's verdict is REJECT, and my reading supports that conclusion: the proof of Theorem 2.4, which underpins Theorem 2.3, contains a false algebraic identity and an unjustified unconditional independence assumption. These are load-bearing because the final Davis-Kahan bound depends on controlling exactly the matrix H U and because equations (36)-(37) are the only concentration estimates used for that control. I agree with the reader that the flaws are likely repairable rather than fatal to the theorem's truth: using EA as the reference matrix removes the algebraic mismatch (after shifting the target eigenvalue by -µin), and a standard conditional-Chernoff-plus-Hoeffding argument would supply the missing concentration. However, the paper as written does not supply these repairs, so the central claim is not rigorously established. I mark agreement as partial because the reader emphasizes the independence issue as the primary load-bearing premise, while I view the algebraic identification as the more decisive and easily checkable flaw; both, nevertheless, are real.","tokens_in":28302,"tokens_out":13290,"duration_ms":148297,"concrete_test":"Set A=Bσ in the proof of Theorem 2.4: then H=A-Bσ=0, so the left side HU is zero, while the claimed expansion AU-(EA)U equals (Bσ-EA)U=µinU, which is nonzero; this single substitution disproves the identity used to define X. Then re-run equations (36)-(37) conditionally on X: apply Chernoff to Y-E[Y|X] and add a Hoeffding bound on |E[Y|X]-nµ|; if the combined tail requires an extra logarithmic factor or a different threshold, the unconditional Chernoff step is not valid as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decisive flaw is in the proof of Theorem 2.4 (Section 4). The perturbation matrix is defined as H=A-Bσ, but after writing X=HU the text asserts X=AU-(EA)U. Since EA=Bσ-µin I, the correct identity is AU-(EA)U=(A-Bσ+µin I)U=HU+µin U, not HU. The missing term µin U has Frobenius norm µin√(k-1), so the subsequent bound on X controls a different matrix than the one required by the Davis-Kahan application. The row-sum argument has a second gap: Y_iz(a) is claimed to be a sum of independent Bernoulli variables with means determined by µin/µout. This holds only conditionally on the random positions X; in the unconditional SGBM distribution the row sums are mixtures of Poisson-binomials, so the Chernoff bounds in (36)-(37) do not follow as written. Both errors are repairable (replace Bσ by EA as the reference matrix, shifting the eigenvalue by -µin, and use a two-step concentration argument), but as submitted the proof of the central perturbation estimate is invalid.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a spectral clustering algorithm for the soft geometric block model (SGBM) with a fixed number k of communities on the d-dimensional torus, and proves weak and strong consistency of the resulting community estimator. The algorithm selects the k-1 eigenvalues of the adjacency matrix closest to a model-dependent value λ*, forms an embedding from the corresponding eigenvectors, clusters the embedding with k-means, and then applies a local majority-vote refinement. The main technical contributions are a limiting spectral measure for the SGBM (via the moment method) and a Davis-Kahan-type perturbation bound relating the sample eigenvectors to those of the expected block matrix B_σ. The paper extends the earlier k=2 result of Avrachenkov, Bobu, and Dreveton (2021).","tokens_in":28548,"tokens_out":14341,"duration_ms":128148,"significance":"If the main results are correct, the paper provides the first multi-community spectral clustering guarantees for the SGBM, with explicit rates and a perfect-recovery refinement. The limiting spectral analysis and the linear-algebra lemmas (e.g., Lemma 4.5) may be of independent interest. However, the proof of the key perturbation bound (Theorem 2.4) contains several gaps that, although apparently repairable, mean the central claim is not rigorously established as submitted.","major_comments":[{"comment":"The proof defines X = HU = AU - (EA)U, but since EA = B_σ - μ_in I_n, the correct identity is AU - (EA)U = HU + μ_in U. The bound on ||X||_F therefore controls a different matrix than the one appearing in the Davis-Kahan application. The missing term contributes O(1/n) after division by εn, which is lower-order than the claimed bound, so the issue is repairable, but as written the argument is inconsistent.","section":"Section 4, proof of Theorem 2.4"},{"comment":"The row sums Y_iz(a) are sums of entries of A, which are independent only conditional on the random positions X. In the unconditional SGBM distribution, these row sums are mixtures of Poisson-binomial variables, so the Chernoff bound of Lemma 4.3 does not apply directly. A two-step concentration argument (first on edges given X, then on X) is needed to justify the stated high-probability bounds.","section":"Section 4, equations (36)-(37)"},{"comment":"The implication that |x_j(i)| > δ only if some single term exceeds its threshold does not follow from the preceding inequality, because the estimate |û_j(p)| < √k together with summation over all k blocks makes the threshold for the sum δ√n/√k, which is smaller than the sum of the individual thresholds Σ δ_p √n. This invalidates the union bound over p as written; the argument can be repaired by using the fact that each column of U has support on only two blocks.","section":"Section 4, after equation (39)"},{"comment":"The statement claims that for every τ ∈ (0, ε), ℓ(σ,σ̂) ≤ τ log n / n, but the proof in Theorem 5.1 yields only ℓ ≤ C k^5 log n / n for a constant C that is independent of τ. Since τ can be made arbitrarily small, the stated rate cannot be concluded from the proof; the claim should be weakened to ℓ = O(log n / n) or the proof must be strengthened.","section":"Theorem 2.3(b) and Section 5"}],"minor_comments":[{"comment":"Condition (i) should be stated more precisely as pointwise convergence of the Fourier series of F_in and F_out at 0, rather than the informal 'F_in(0) is equal to the Fourier series evaluated at 0'.","section":"Theorem 2.1"},{"comment":"The theorem is restated as 'Theorem 2.-2' in the proof of Theorem 2.4; this is a typo that should be corrected.","section":"Section 4"},{"comment":"Algorithm 2 lists μ_in and μ_out as input but does not use them; the input list should be corrected to include only the output of Algorithm 1.","section":"Algorithm 2"},{"comment":"The notation for the matrix V with a bar is not clearly distinguished from V in the typeset text; consider using a different symbol or clarifying the typesetting.","section":"Lemma 5.1"}],"recommendation":"major_revision","confidential_remarks":"The reader's report recommends rejection, but in my assessment the central claims are plausible and the identified gaps are repairable within the scope of a major revision. The paper extends a known two-community result to k communities, the model is natural, and the technical work, though currently incomplete, is substantial. I would encourage the editor to consider a revised version. One additional concern is that the paper's contribution relative to [3] is incremental (generalizing from k=2 to fixed k), though this is normal and not by itself disqualifying."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The k≥2 extension is real, but the proof of Theorem 2.4 doesn't hold as written. Two load-bearing errors: the algebraic identification of (A−Bσ)U with (A−EA)U misses a μ_in U term, and the Chernoff bounds treat row sums as unconditionally independent. Both are repairable, but the paper needs major revision before the consistency theorems are established.\n\nWhat's genuinely new: first consistency guarantees for k-community soft geometric block models, the limiting spectrum via the moment method for k≥2, a basis-independent Davis-Kahan bound for non-simple eigenvalues, and a k-means perturbation lemma that extends the d=k case. These are useful tools with independent interest. The paper is honest and well-organized; Example 1.1 nicely shows why the middle eigenvectors, not the top ones, carry the community information. The extension from k=2 is more than cosmetic, since the eigenspace is no longer one-dimensional and the choice of basis matters.\n\nNow the soft spots, in the order they bite. First, in the proof of Theorem 2.4 the text defines H=A−Bσ and then writes X=HU=AU−(EA)U. But EA=Bσ−μ_in I, so AU−(EA)U = (A−Bσ+μ_in I)U = HU+μ_in U. The missing term has Frobenius norm μ_in√(k−1), same order as the bound they later derive, so the argument controls a different matrix than the one fed to Davis-Kahan. This is a genuine algebraic slip, not a stylistic issue.\n\nSecond, the concentration argument for Y_iz(a), the row sums, applies Lemma 4.3 to a sum of independent Bernoullis with means determined by μ_in and μ_out. That is only true conditional on the random positions X. Unconditionally, the row sums are mixtures of Poisson-binomials, so the Chernoff bounds in (36)–(37) do not follow as stated. A two-step concentration argument—first show X lies in a typical configuration, then apply Chernoff conditionally—should fix it, but that argument is not in the paper.\n\nThird, the paper claims the GBM is covered because conditions (i)–(iii) hold almost everywhere, citing Lemma A.2. But Lemma A.2 only addresses conditions (ii) and (iii); condition (i), which requires the Fourier series of an indicator kernel to match its value at 0, is generally false for discontinuous kernels. The coverage claim is overstated.\n\nBottom line: this deserves a serious referee, not a desk reject. The result is likely true and the proof strategy is right; the fixes are identifiable. But as submitted, the central perturbation bound is unproven, so I would not cite the theorem in its current form. Send it to a good referee and expect a careful revision.","headline":"The k-community SGBM extension is real and mostly well-argued, but the proof of Theorem 2.4 is broken as written; worth refereeing, not accepting.","tokens_in":29055,"tokens_out":2582,"would_cite":false,"duration_ms":27752,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60B20","05C80","62H30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that choosing the k-1 adjacency eigenvectors closest to $\\lambda^* = n(\\mu_{in}-\\mu_{out})/k$ and clustering the embedding with $k$-means recovers all $k$ communities in soft geometric block models on the torus.","keywords":["Soft Geometric Block Model","Community detection","Spectral clustering","Random geometric graphs","Random matrices","Davis-Kahan theorem","k-means","Spectral embedding"],"falsifier":"Simulate the SGBM with $k=3$, $n=1000,2000,4000$, and record the within-community degree of one fixed vertex over many position realizations; if its variance exceeds the binomial value $n\\mu_{in}(1-\\mu_{in})/k$, the Chernoff bound behind Theorem 2.4 cannot hold as written, and the simulation's Algorithm 1 loss will reveal whether the $O(\\log n/n)$ rate survives despite the gap.","tokens_in":28080,"feed_emoji":"🕸️","tokens_out":8768,"duration_ms":85015,"temperature":0.7,"pith_summary":"This paper extends the soft geometric block model (SGBM) community-detection problem from two communities to any fixed number $k$, and claims that a spectral algorithm succeeds where classical top-eigenvector methods fail. In the SGBM, $n$ nodes are placed uniformly at random on the $d$-dimensional flat torus, and edges appear with probabilities that depend on the distance between nodes and on whether they share a community. The proposed Algorithm 1 forms the $n \\times (k-1)$ matrix of eigenvectors belonging to the $k-1$ adjacency eigenvalues closest to $\\lambda^* = n(\\mu_{in}-\\mu_{out})/k$, embeds the rows, and clusters with $k$-means; Theorem 2.3 says this is weakly consistent, with loss $O(\\log n / n)$, and that a one-step majority-vote refinement (Algorithm 2) gives perfect recovery with probability tending to 1. The proof rests on a new eigenspace perturbation bound (Theorem 2.4) obtained from a non-standard Davis-Kahan theorem, together with a limiting-spectrum analysis of the adjacency matrix. A sympathetic reader should care because geometric dependence breaks classical spectral clustering, and this is a general method that identifies which eigenvectors actually carry the community label.","feed_headline":"Proof: k-1 middle eigenvalues recover all k communities","feed_subtitle":"On soft geometric block models, this mid-spectrum embedding is weakly consistent, and one majority-vote pass gives perfect recovery.","key_machinery":"The central object is the population edge-probability matrix $B_\\sigma$, the $n \\times n$ matrix with $\\mu_{in}$ on within-community pairs and $\\mu_{out}$ on between-community pairs. Its eigenvalue $\\lambda^* = n(\\mu_{in}-\\mu_{out})/k$ has multiplicity $k-1$, and the corresponding eigenspace has an explicit basis $U$ whose rows are constant on communities, so that $k$-means on any orthonormal basis of that eigenspace separates communities cleanly. The adjacency matrix $A$ is a random perturbation of $B_\\sigma$, and the proof transfers the clean eigenspace of $B_\\sigma$ to the sample by a non-standard Davis-Kahan theorem that does not require the relevant eigenvalues of $A$ to be simple; it only requires the $k-1$ target eigenvalues to be separated from the rest. The limiting-spectrum result shows the empirical spectral measure converges to a countably supported measure concentrated near the Fourier coefficients of the connectivity functions, which locates $\\lambda^*$ as the only cluster carrying community information.","core_discovery":"Under the SGBM on the $d$-dimensional flat torus, with $k$ equal-size communities and $\\mu_{in} > \\mu_{out} > 0$, the paper establishes that the $k-1$ eigenvalues of the adjacency matrix closest to $\\lambda^* = n(\\mu_{in}-\\mu_{out})/k$ are asymptotically almost surely separated by a linear gap from all remaining eigenvalues (Theorems 2.2 and 2.3(a)). If the columns of the matrix $V$ of corresponding orthonormal eigenvectors are used to embed the vertices in $\\mathbb{R}^{k-1}$, $k$-means clustering on the rows of $V$ produces an estimator with classification loss at most $\\tau \\log n / n$ asymptotically almost surely (Theorem 2.3(b)). Replacing each label by the majority community among its graph neighbors turns this into exact recovery, loss $0$, asymptotically almost surely (Theorem 2.3(c)). The quantitative engine is Theorem 2.4: for $U$ the eigenvectors of the population matrix $B_\\sigma$ with entries $\\mu_{in}$ within communities and $\\mu_{out}$ between communities, $\\min_{Q \\text{ orthogonal}} \\|VQ - U\\|_F \\le \\sqrt{12 k^5 \\log n}/(\\epsilon \\sqrt{n})$ asymptotically almost surely, and this bound is what lets a $(1+\\epsilon)$-approximate $k$-means solution have few mistakes.","pith_inferences":["We infer that a likely repair of the proof's row-independence gap is to condition on the random positions $X$ and then average, which would preserve the $O(\\log n/n)$ rate only if the variance of the unconditional mixture does not dominate; testing this directly with simulated row sums would show whether the theorem's rate is exactly right.","We infer that the central mechanism, targeting the mid-spectrum eigenvalue $\\lambda^*$ rather than extremal ones, suggests a general design principle for geometric network models: locate the eigenvalue of the population matrix whose eigenspace is constant on latent groups, and use that, not the largest eigenvalues, to embed.","We infer that the argument may extend to unequal community sizes by replacing the scalar $\\lambda^*$ with a per-community weighted eigenvalue and letting $U$ carry the block sizes; this is an open question the paper lists, and the eigenspace machinery seems adaptable.","We infer that if the proof gap is repaired, similar bounds should hold for other compact homogeneous spaces, such as spheres, since the Fourier analysis and the population matrix carry over."],"forward_implications":["For any fixed $k$ and any torus dimension $d$, picking the $k-1$ adjacency eigenvectors closest to $\\lambda^*$ and running $k$-means gives a weakly consistent community estimator, so the algorithm can be applied without knowing the top of the spectrum.","Adding one local majority-vote refinement upgrades weak consistency to strong consistency: after the refinement the partition is exactly the planted one asymptotically almost surely.","For the stochastic block model, the theorem reproduces classical spectral clustering: $\\lambda^*$ becomes the repeated eigenvalue of the block matrix, and the selected eigenvectors are the usual ones.","For the geometric block model with deterministic edge radii, the technical conditions hold except for a measure-zero set of radii, so the algorithm also applies to hard geometric partitions.","The Davis-Kahan variant and the auxiliary matrix lemmas are stated generically, so they can be reused for other random-matrix perturbations where the unperturbed eigenvalue is multiple."],"supporting_citations":[{"why":"The two-community SGBM spectral algorithm and proof template that this paper generalizes to arbitrary k.","marker":"[3]"},{"why":"Establishes the limiting empirical spectral measure for Euclidean random matrices, the method adapted here for Theorem 2.1.","marker":"[7]"},{"why":"The classical stochastic-block-model spectral clustering consistency result that supplies the baseline and the k-means-plus-eigenvector framing.","marker":"[20]"},{"why":"The relative perturbation (Davis-Kahan type) theorem used to bound eigenspace changes when the target eigenvalue is multiple.","marker":"[21]"},{"why":"Source of the Chernoff bound used to control row sums in the proof of Theorem 2.4.","marker":"[25]"},{"why":"The k-means approximation lemma that transfers eigenvector closeness to a bound on classification error.","marker":"[4]"},{"why":"Provides the (1+epsilon)-approximate linear-time k-means algorithm used in the consistency argument.","marker":"[18]"}],"fun_headline_variants":["k-1 middle eigenvalues recover all communities perfectly","Mid-spectrum embedding plus one vote pass = exact recovery","Spectral clustering on SGBM: from weak to strong consistency","Davis-Kahan trick tames non-simple eigenvalues for clustering","Geometric graphs: mid-eigenvalues give exact community labels"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that, in the unconditional SGBM, the entries of the adjacency matrix in a fixed row can be treated as independent Bernoulli variables with fixed means, even though independence actually holds only after conditioning on the random node positions; the proof's Chernoff bounds and the identification of $(A-B_\\sigma)U$ with $(A-\\mathbb{E}A)U$ depend on that premise.","fun_headline_variants_meta":{"raw":{"variants":["k-1 middle eigenvalues recover all communities perfectly","Mid-spectrum embedding plus one vote pass = exact recovery","Spectral clustering on SGBM: from weak to strong consistency","Davis-Kahan trick tames non-simple eigenvalues for clustering","Geometric graphs: mid-eigenvalues give exact community labels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000338,"raw_usage":{"total_tokens":1897,"prompt_tokens":1004,"completion_tokens":893,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":810}},"tokens_in":620,"tokens_out":893,"duration_ms":8818,"temperature":1.0,"reasoning_tokens":810,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:47:25.445119+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the SGBM with $k=3$, $n=1000,2000,4000$, and record the within-community degree of one fixed vertex over many position realizations; if its variance exceeds the binomial value $n\\mu_{in}(1-\\mu_{in})/k$, the Chernoff bound behind Theorem 2.4 cannot hold as written, and the simulation's Algorithm 1 loss will reveal whether the $O(\\log n/n)$ rate survives despite the gap.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The two-community SGBM spectral algorithm and proof template that this paper generalizes to arbitrary k."},{"cited_title":"4, 515–532","cited_arxiv_id":null,"evidence_quote":"Establishes the limiting empirical spectral measure for Euclidean random matrices, the method adapted here for Theorem 2.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The classical stochastic-block-model spectral clustering consistency result that supplies the baseline and the k-means-plus-eigenvector framing."},{"cited_title":"eigenspace and singular subspace variations, SIAM Journal on Matrix Analysis and Applications20(1998), no","cited_arxiv_id":null,"evidence_quote":"The relative perturbation (Davis-Kahan type) theorem used to bound eigenspace changes when the target eigenvalue is multiple."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the Chernoff bound used to control row sums in the proof of Theorem 2.4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The k-means approximation lemma that transfers eigenvector closeness to a bound on classification error."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the (1+epsilon)-approximate linear-time k-means algorithm used in the consistency argument."}],"review_version":2}