{"id":"b9689e83-a371-41e8-9923-c6433f4a6ef8","arxiv_id":"2506.07224","paper_version":1,"verdict":"REJECT","confidence":"LOW","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"TCSC and its one-step refinement R-TCSC are claimed to achieve strong consistency, exact recovery of all community labels with high probability, under the Popularity Adjusted Block Model.","lead":"This paper proposes two spectral clustering algorithms for the Popularity Adjusted Block Model and claims that the one-step refinement achieves exact community recovery with high probability. The claims are new, but the preprint states all theorems without proofs, so the central result cannot currently be verified.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's strong-consistency claim is asserted without proof, and the one proof route sketched relies on independence that fails for the data-dependent initializer \\hat c^{(0)}.","rationale":"The reader's rejection is on the right track. The strongest part of the paper is the constructive spectral characterization (Proposition 1) and the numerical evidence, but the central advertised contribution—strong consistency of one-step R-TCSC—rests entirely on Theorem 2, and that theorem is unproved. I did not find a demonstration that Assumption 6 by itself implies the required initializer accuracy or the required score separation; the text asserts it. The leave-one-out independence issue is not a cosmetic detail because exact recovery requires an n^{-(2+C_2)} per-node failure rate, which cannot be obtained by applying a fixed-partition lemma to a random partition unless one has uniform control over all plausible partitions. I therefore keep the reader's verdict: the claim is currently unsupported. I partially agree with the reader's identification of Assumption 6: the sparsity condition is one facet, but the more load-bearing difficulty is the missing uniform concentration for the refinement step.","tokens_in":19840,"tokens_out":8040,"duration_ms":92660,"concrete_test":"Obtain or reconstruct the proof of Theorem 2 and check the single decisive step: a concentration bound for the refinement score S_{cos,ik}(\\hat c^{(0)}) that holds uniformly over the data-dependent initializer \\hat c^{(0)}, with failure probability n^{-(2+C_2)} per node. The check should exhibit the exact event on which \\hat c^{(0)} is well behaved, prove the score separation with the leave-one-out remainder in the denominator of Eq. (9) controlled, and give an explicit initial-error rate under Assumption 6. If the only available argument treats \\hat c^{(0)} as fixed or conditions on it without a uniform-control step, the proof of Eq. (14) fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing claim is Theorem 2 (Eq. 14): with probability at least 1 - C_1 n^{-(1+C_2)}, the one-step R-TCSC estimate exactly equals c* up to permutation. No proof of Theorem 2 is given anywhere in the manuscript or an appendix, and the surrounding discussion does not make it a corollary of Theorem 1: the refinement step needs a quantitative, node-wise bound on the score separation, not merely ℓ(c*, \\hat c^{(0)}) = o(1). The sketch in Section 3.3 contains a specific unresolved point. It defines the leave-one-out average \\bar A^{(k,l)}_{-i}(\\tilde c) and says it is independent of A_i^{(l)}(\\tilde c) “for any fixed \\tilde c ∈ [K]^n”. However, the actual initializer \\hat c^{(0)} is random and is a function of the same adjacency matrix A, so conditioning on \\hat c^{(0)} does not make it independent of A_i^{(l)}(\\hat c^{(0)}). A union bound over all K^n possible initializers is not available without additional structure. Moreover, Eqs. (8)–(9) use the leave-one-out center only in the numerator, while the denominator is the full \\bar A^{(k,l)}(\\hat c^{(0)}), so the claimed independence simplification is incomplete even for a fixed partition. Consequently, Assumption 6 (K log n/(n ρ_n^4)=o(1) and K ≤ n^{1/6}) may be sufficient or not, but the theorem's conclusion is not established by the text.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two spectral clustering procedures under the Popularity Adjusted Block Model (PABM): a Thresholded Cosine Spectral Clustering (TCSC) initializer and a one-step Refined TCSC (R-TCSC) that is claimed to upgrade weak consistency to strong consistency. It further claims that a two-step refinement accelerates error convergence for finite samples and introduces a singular-value-based method (SVCP) for selecting the number of communities. The main theoretical results are Theorem 1 (weak consistency of TCSC), Theorem 2 (strong consistency of one-step R-TCSC), and Theorem 3 (rates for two-step R-TCSC), supported by Proposition 1 on the eigenspace structure of the PABM edge probability matrix and Proposition 2 on the identifiability of the number of communities. The paper also contains simulations and two real-data analyses. The central claims are plausible and the algorithmic ideas are interesting, but the current manuscript does not include proofs of any of the main theorems or propositions, and the proof sketch for the refinement step contains a specific independence issue that is load-bearing for Theorem 2.","tokens_in":20232,"tokens_out":3824,"duration_ms":42668,"significance":"If the strong-consistency result in Theorem 2 were fully established, the paper would provide a meaningful advance: it would give the first spectral-clustering-based method with exact label recovery under the PABM without i.i.d. assumptions on the popularity vectors, and the proposed TCSC and R-TCSC algorithms are natural and computationally appealing. The eigenspace characterization in Proposition 1 is a useful structural contribution, and the numerical study suggests that the methods perform well relative to existing baselines. However, the significance is conditional because none of the theoretical statements are accompanied by proofs, and the one proof sketch that is provided for the refinement step appears to contain a gap. The paper would be strengthened by a complete appendix with rigorous arguments and by a clearer connection between the theoretical threshold conditions and the data-driven implementation choices.","major_comments":[{"comment":"No proofs are provided for Proposition 1, Proposition 2, Theorem 1, Theorem 2, or Theorem 3 anywhere in the manuscript or an appendix. Since the central claims of the paper are these theorems, the derivations cannot be audited. In particular, Eq. (14) of Theorem 2 is the main advertised result, but the text only states it and refers to a proof that is not present. This is a load-bearing omission that must be addressed before the claims can be evaluated.","section":"Section 4 (Theorems 1–3) and Section 3.1 (Proposition 1), Section 6 (Proposition 2)"},{"comment":"The proof sketch for the refinement step contains a specific independence issue. The text says that the leave-one-out average \\bar A^{(k,l)}_{-i}(\\tilde c) is independent of A_i^{(l)}(\\tilde c) 'for any fixed \\tilde c', but the actual initializer \\hat c^{(0)} is random and depends on the same adjacency matrix A. Conditioning on \\hat c^{(0)} does not make it independent of A_i^{(l)}(\\hat c^{(0)}), and no union bound over all K^n possible initializers is supplied. Moreover, Eqs. (8)–(9) use the leave-one-out center only in the numerator while the denominator uses the full \\bar A^{(k,l)}(\\hat c^{(0)}), so the claimed independence simplification is incomplete even for a fixed partition. This gap directly affects the proof of Theorem 2 and must be resolved with a rigorous argument that handles the randomness of \\hat c^{(0)}.","section":"Section 3.3, Eqs. (8)–(9)"},{"comment":"Assumption 6 requires K log n / (n \\rho_n^4) = o(1) and K \\le n^{1/6}. The text calls this 'quite mild', but under the common sparse scaling \\rho_n^2 \\asymp (\\log n)/n the condition fails. Thus Theorem 2 only covers relatively dense regimes, and the paper's claim of strong consistency under the PABM is not established for sparse real-world networks. The authors should either prove the theorem under a weaker density condition, or clearly state the dense-regime limitation in the abstract and introduction. As written, the scope of the main result is substantially narrower than the narrative suggests.","section":"Section 4, Assumption 6, Eq. (13)"},{"comment":"The theoretical results, including Theorem 1 and the initialization step of Algorithm 2, assume that the threshold is set to d_n = \\phi_{1,n}/2 for a sequence \\phi_{1,n} that is not observable. In the simulations, however, the threshold is chosen as the point of steepest drop in the histogram of the estimated similarities. No result connects this data-driven choice to the theoretical condition d_n = \\phi_{1,n}/2, so the practical algorithm is not covered by the stated theorems. This gap should be addressed either by proving that the histogram rule satisfies the required condition with high probability or by treating the threshold as an additional tuning parameter whose range is covered by the theory.","section":"Section 3.2 and Section 5 (threshold d_n)"}],"minor_comments":[{"comment":"The sentence 'for any true label vector c* ... we evaluate an estimator c*' appears to contain a typo: the estimator should be denoted \\hat c, not c*, and the objective should be stated as evaluating \\hat c against the true c*.","section":"Section 2, Eq. (2)"},{"comment":"The description of the baseline 'EP' is misattributed: the likelihood modularity method that optimizes the PABM likelihood was introduced by Sengupta and Chen (2017), not by Chen and Lei (2018). The reference list already contains the correct source, and the citation in the text appears to be an error.","section":"Section 5, first paragraph"},{"comment":"The leave-one-out estimator \\bar A^{(k,l)}_{-i}(\\hat c^{(0)}) is defined with a denominator n_k(\\hat c^{(0)}) but excludes node i; if the intent is a true leave-one-out average, the denominator should be n_k(\\hat c^{(0)}) - 1 when node i is in community k. As written, the definition is inconsistent with the usual leave-one-out construction.","section":"Section 3.3, Eq. (7)"},{"comment":"The captions for Figures 7–9 are incomplete or grammatically clipped ('in case of balanced communities', etc.); they should be expanded to describe the comparison between R-TCSC-1 and R-TCSC-2 and the parameter settings used.","section":"Figures 7–9"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about arXiv:2506.07224. First, the paper contains a genuinely new structural result: Proposition 1 gives an explicit characterization of the eigenspace of the PABM edge probability matrix, showing why ordinary spectral clustering fails and why a thresholded cosine similarity is the right tool. Second, the headline claim—strong consistency via one-step refinement (Theorem 2)—is not supported by what is actually written: the theorems appear without proofs, and the proof sketch in Section 3.3 contains a real gap. The independence of the leave-one-out average from the data-dependent initializer does not follow from the fixed-label argument. Since \\hat c^{(0)} is a function of the same adjacency matrix, conditioning on it does not restore independence, and the denominator uses the full average, not the leave-one-out version. The stress-test note identifies this correctly. So the central promise is currently unverified.\n\nWhat the paper does well: it is clearly written, and Example 1 is a useful correction to Koo et al.'s orthogonality claim. The TCSC algorithm is well motivated, and the simulations—though without code—are fairly extensive and show gains over SSC-A, OSC, and SSC-ASE in the plotted settings. The K-selection method (SVCP) is a nice addition and beats the LP method in the reported table.\n\nSoft spots beyond the missing proofs: Assumption 6 is strong, requiring n rho_n^4 to diverge faster than K log n, so the strong-consistency result only covers fairly dense networks; that limitation is not highlighted in the abstract or conclusion. The practical threshold d_n is chosen by a histogram heuristic, not linked to the theoretical phi_{1,n}. Minor: positivity of lambda_ik is used in Section 3.3 but never appears in the formal assumptions.\n\nOn balance, I would not rely on Theorem 2 as stated, but I would not dismiss the paper either. The eigenspace characterization and the algorithmic ideas are worth taking seriously. If this crosses your desk, send it to a careful referee with a clear instruction: complete proofs of Theorems 1–3, or at least a verifiable proof of Theorem 2, are required before acceptance. The referee time is justified because the contribution, if correct, would be a meaningful advance for PABM community detection.","headline":"Plausible and well-motivated, but the central strong-consistency theorem is asserted without proof and the one sketched route has a real technical gap.","tokens_in":709,"tokens_out":1435,"would_cite":false,"duration_ms":40131,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a single refinement pass after thresholded cosine spectral clustering recovers every community label exactly, with high probability, under the Popularity Adjusted Block Model.","keywords":["Popularity Adjusted Block Model","community detection","spectral clustering","cosine similarity","strong consistency","one-step refinement","number of communities","network data"],"falsifier":"Simulate the PABM with $n\\rho_n^4\\asymp \\log n$ and $K=n^{1/6}$ so Assumption 6 barely fails, then run one-step R-TCSC over many replications; if the fraction of runs with at least one mislabeled node does not fall as $n^{-(1+C_2)}$ or even remains positive, the claimed high-probability bound would be contradicted in that regime.","tokens_in":19674,"feed_emoji":"🕸️","tokens_out":6067,"duration_ms":53588,"temperature":0.7,"pith_summary":"The paper tackles community detection in the Popularity Adjusted Block Model (PABM), a network model where each node's popularity toward each community is a free parameter, so nodes in the same community are neither identical nor proportional in the spectral embedding. The authors propose a two-stage strategy: Thresholded Cosine Spectral Clustering (TCSC) uses the absolute cosine similarity between eigenvector rows to build thresholded vectors that approximate one-hot community indicators, then applies K-means; this gives weak consistency. They then prove that one refinement step, in which each node is reassigned by maximizing the sum of cosine similarities between its observed edge vector and estimated community centers, upgrades the weak estimate to strong consistency: with probability at least $1-C_1 n^{-(1+C_2)}$, every node is labeled correctly. A two-step version is shown to accelerate the error convergence rate in finite samples, and a data-driven singular-value-change-point rule is proposed for choosing the number of communities. A sympathetic reader should care because exact label recovery is the input needed for downstream tests and community-counting procedures, and the method does not rely on distributional assumptions on the popularity parameters.","feed_headline":"One refinement step recovers every community label under the PABM","feed_subtitle":"Spectral initialization plus a cosine-similarity refinement achieves exact community recovery in networks with heterogeneous node…","key_machinery":"The machinery is the angle-based similarity $\\tau_{ij} = |\\cos(\\xi_{i\\cdot}, \\xi_{j\\cdot})|$ on rows of the $n \\times K^2$ eigenvector matrix of the edge probability matrix. Proposition 1 and Corollary 1 show that $\\tau_{ij}=0$ for nodes in different communities and $\\tau_{ij}$ equals a Mahalanobis-type cosine of popularity vectors for nodes in the same community, so angles, not Euclidean distance, carry the label information. TCSC thresholds these estimated cosines to form vectors near one-hot community indicators and clusters them with $(1+\\varepsilon)$-approximate K-means. The one-step refinement then rescues the few misclassified nodes: for each node it computes the cosine between the node's observed row of adjacency entries restricted to each current community and the corresponding community centers (with a leave-one-out correction), and reassigns the node to the community with the largest summed similarity. That cosine-maximization identity is what upgrades weak to strong consistency.","core_discovery":"The central claim is Theorem 2: under Assumptions 1, 5, and 6, the one-step Refined TCSC estimator $\\hat{c}^{(1)}$ satisfies $\\mathbb{P}(\\cup_{\\pi} \\{\\hat{c}^{(1)}=\\pi[c^*]\\}) > 1 - C_1 n^{-(1+C_2)}$, meaning that with high probability it recovers every community label exactly, up to a permutation. The proof rests on a population-level structural result (Proposition 1) showing that the eigenvector matrix of the edge probability matrix factors as $\\Xi^{(k)} = \\Lambda^{(k,\\cdot)} Z_k$, so rows of nodes in different communities are orthogonal while rows in the same community have positive angular similarity. The refinement maximizes, for each node, the aggregated cosine similarity between its edge counts to the current communities and the estimated community centers; the paper shows one such pass is enough to turn a weakly consistent initializer into an exactly correct labeling.","pith_inferences":["If the density condition $K\\log n/(n\\rho_n^4)\\to 0$ can be weakened, the same one-step cosine refinement could plausibly deliver exact recovery in the sparse regime $\\rho_n^2\\asymp(\\log n)/n$, where the current proof does not reach; this is a testable extension rather than a claim of the paper.","Because the population eigenspace factorization in Proposition 1 is explicit, the angle-based similarity should transfer to directed or bipartite variants of the PABM, where the same block rank-one structure appears.","The theorem requires only a weakly consistent initializer with a mild error condition, so other cheap initializers could replace TCSC and the one-step cosine refinement would still be expected to yield strong consistency.","A direct empirical check of the theory: run one-step versus two-step refinement on the DBLP and butterfly networks while tracking which nodes are corrected at each pass; the predicted pattern is that the first pass corrects almost all errors when $n$ is small, and the second pass adds little when $n$ is large."],"forward_implications":["TCSC provides a weakly consistent spectral initialization for the PABM, so standard spectral clustering machinery becomes usable in a model where within-community spectral rows are neither identical nor proportional.","One pass of the angle-based refinement gives exact recovery of all community labels with probability at least $1-C_1 n^{-(1+C_2)}$, so downstream tests and community-count estimators can be built on an exactly labeled network.","A second refinement step improves the finite-sample error rate to $o(1/(n\\rho_n^2))$, which is especially visible for small $n$.","The estimated number of communities from the singular-value change-point rule equals the true $K$ with probability at least $1-n^{-C}$, and it stays accurate for larger $K$ where the loss-plus-penalty baseline degrades.","The procedures require no i.i.d. assumption on the popularity rows $\\Lambda$, so they remain reliable under within-community heterogeneity that breaks competing spectral methods."],"supporting_citations":[{"why":"Introduces the PABM and establishes weak consistency for a modularity-based estimator; the model and loss function here follow it.","marker":"Sengupta and Chen (2017)"},{"why":"Shows that the PABM's row structure enables subspace-clustering estimation, establishes weak consistency, and provides the loss-plus-penalty baseline for selecting K whose failure at larger K motivates SVCP.","marker":"Noroozi et al. (2021b)"},{"why":"Supplies the spectral clustering consistency framework and the (1+epsilon)-approximate K-means guarantee used in TCSC.","marker":"Lei and Rinaldo (2015)"},{"why":"Provides the sparsity parameterization rho_n and the density condition n rho_n^4 >> (log n)^2 that the paper relaxes to Assumption 6.","marker":"Chen and Lei (2018)"},{"why":"Precedent that a refinement step upgrades a reasonable initializer in DCSBM; the PABM refinement adapts that idea to angle-based similarity.","marker":"Gao et al. (2018)"},{"why":"Analyzes the PABM as a generalized random dot product graph and applies SSC to the spectral embedding; the paper contrasts its orthogonality theorem with Example 1 and benchmarks against its algorithm.","marker":"Koo et al. (2023)"}],"fun_headline_variants":["One refinement step turns weak spectral clustering into exact recovery","Exact community detection with a single cosine refinement pass","Strong consistency achieved by one-step refined spectral clustering","Refined TCSC: one pass to perfectly recover all community labels","PABM: one-step refinement gives exact label recovery with high probability"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The strong-consistency proof assumes the network is dense enough that $K\\log n/(n\\rho_n^4)$ is small and $K\\le n^{1/6}$, so the signal in the adjacency matrix is strong enough for a single refinement pass to reclassify every node.","fun_headline_variants_meta":{"raw":{"variants":["One refinement step turns weak spectral clustering into exact recovery","Exact community detection with a single cosine refinement pass","Strong consistency achieved by one-step refined spectral clustering","Refined TCSC: one pass to perfectly recover all community labels","PABM: one-step refinement gives exact label recovery with high probability"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000213,"raw_usage":{"total_tokens":1399,"prompt_tokens":897,"completion_tokens":502,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":513,"completion_tokens_details":{"reasoning_tokens":420}},"tokens_in":513,"tokens_out":502,"duration_ms":5257,"temperature":1.0,"reasoning_tokens":420,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:39:47.008794+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the PABM with $n\\rho_n^4\\asymp \\log n$ and $K=n^{1/6}$ so Assumption 6 barely fails, then run one-step R-TCSC over many replications; if the fraction of runs with at least one mislabeled node does not fall as $n^{-(1+C_2)}$ or even remains positive, the claimed high-probability bound would be contradicted in that regime.","supporting_citations":[{"cited_title":"and Chen, Y","cited_arxiv_id":null,"evidence_quote":"Introduces the PABM and establishes weak consistency for a modularity-based estimator; the model and loss function here follow it."},{"cited_title":"and Lei, J","cited_arxiv_id":null,"evidence_quote":"Provides the sparsity parameterization rho_n and the density condition n rho_n^4 >> (log n)^2 that the paper relaxes to Assumption 6."},{"cited_title":"Y., and Zhou, H","cited_arxiv_id":null,"evidence_quote":"Precedent that a refinement step upgrades a reasonable initializer in DCSBM; the PABM refinement adapts that idea to angle-based similarity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Analyzes the PABM as a generalized random dot product graph and applies SSC to the spectral embedding; the paper contrasts its orthogonality theorem with Example 1 and benchmarks against its algorithm."}],"review_version":1}