REVIEW 4 major objections 4 minor 49 references
Strongly Consistent Community Detection in Popularity Adjusted Block Models
T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict Plausible and well-motivated, but the central strong-consistency theorem is asserted without proof and the one sketched route has a real technical gap. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Section 4 (Theorems 1–3) and Section 3.1 (Proposition 1), Section 6 (Proposition 2)] 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 3.3, Eqs. (8)–(9)] 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 4, Assumption 6, Eq. (13)] 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 3.2 and Section 5 (threshold d_n)] 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.
minor comments (4)
- [Section 2, Eq. (2)] 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 5, first paragraph] 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 3.3, Eq. (7)] 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.
- [Figures 7–9] 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.
Circularity Check
No significant circularity: Theorem 2 rests on pre-specified density and identifiability assumptions; the missing proof is a correctness concern, not a circular step.
full rationale
The load-bearing result, Theorem 2 (Eq. 14), asserts strong consistency of the one-step R-TCSC under Assumptions 1, 5 and 6. These assumptions are pre-specified identifiability, sparsity, and separability conditions on the PABM parameters; they are not outputs of the algorithm, nor are any fitted parameters renamed as predictions. The threshold in Algorithm 1 is set to d_n = φ_{1,n}/2 with φ_{1,n} appearing in Assumptions 3–4 as a signal-strength condition, so the threshold choice is part of the theoretical framework rather than a fitted quantity recycled as a conclusion. The refinement update (Eq. 9) uses the initial estimate ĉ^(0), but the theorem's claim is that a weakly consistent initializer can be upgraded to strong consistency by one refinement step; this is a substantive upgrade claim, not an equivalence-by-construction. The skeptical concern that Theorem 2 is asserted without a complete proof, and that the leave-one-out independence argument for the data-dependent initializer may fail, is a proof gap or correctness risk, not circularity: it does not show that the conclusion is identical to an input or that a self-citation carries the argument. The paper cites prior PABM work (Sengupta and Chen 2017; Noroozi et al. 2021a,b; Koo et al. 2023) for background, model origin, and comparisons; these citations are not load-bearing self-citations, and none of the authors' own prior work is invoked to forbid alternatives or to supply an unproved uniqueness theorem. The consistency results are candidate new theorems whose proofs are incomplete in the manuscript, but the derivation chain as written does not reduce to its own inputs.
Assumptions & free parameters
free parameters (2)
- Threshold d_n in TCSC =
adaptive, chosen as steepest drop in histogram
- Window width d in SVCP =
2
assumptions (7)
- domain assumption Theta has rank K^2, equivalently {lambda^(k,l)}_{l in [K]} linearly independent for each k
- domain assumption Assumption 1: balanced community sizes n/(CK) <= n_k(c*) <= Cn/K
- domain assumption Assumption 2: n rho_n^2 / K^2 >= C (log n)^2
- ad hoc to paper Assumptions 3-4: within-community rows non-orthogonal and eigenrow norms bounded below for most nodes
- domain assumption Assumption 5: |cos(lambda^(l,k), lambda^(l,k'))| <= 1 - delta for k != k'
- domain assumption Assumption 6: K log n / (n rho_n^4) = o(1), K <= n^{1/6}, plus strengthened versions of Assumptions 3-4
- ad hoc to paper Positivity lambda_{ik} != 0 for all i,k
Cite this review
Pith. "Pith review of Strongly Consistent Community Detection in Popularity Adjusted Block Models." pith.science (2026). https://pith.science/paper/OYIVULTU
@misc{pith2026250607224,
author = {Pith},
title = {Pith review of: Strongly Consistent Community Detection in Popularity Adjusted Block Models},
year = {2026},
howpublished = {\url{https://pith.science/paper/OYIVULTU}},
note = {Machine review of arXiv:2506.07224}
}
read the original abstract
The Popularity Adjusted Block Model (PABM) provides a flexible framework for community detection in network data by allowing heterogeneous node popularity across communities. However, this flexibility increases model complexity and raises key unresolved challenges, particularly in effectively adapting spectral clustering techniques and efficiently achieving strong consistency in label recovery. To address these challenges, we first propose the Thresholded Cosine Spectral Clustering (TCSC) algorithm and establish its weak consistency under the PABM. We then introduce the one-step Refined TCSC algorithm and prove that it achieves strong consistency under the PABM, correctly recovering all community labels with high probability. We further show that the two-step Refined TCSC accelerates clustering error convergence, especially with small sample sizes. Additionally, we propose a data-driven approach for selecting the number of communities, which outperforms existing methods under the PABM. The effectiveness and robustness of our methods are validated through extensive simulations and real-world applications.
Figures
Figures from the paper (8 more)
Reference graph
Works this paper leans on
-
[1]
Abbe, E. and Sandon, C. (2015). Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , page 670–688, Berkeley. IEEE Computer Society
work page 2015
-
[2]
Agarwal, A. and Xue, L. (2020). Model-based clustering of nonparametric weighted networks with application to water pollution analysis. Technometrics , 62(2):161--172
work page 2020
-
[3]
Amini, A. A., Chen, A., Bickel, P. J., and Levina, E. (2013). Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics , 41(4):2097--2122
work page 2013
-
[4]
Ariu, K., Proutiere, A., and Yun, S.-Y. (2023). Instance-optimal cluster recovery in the labeled stochastic block model. arXiv , page 2306.12968
work page Pith review arXiv 2023
-
[5]
Bickel, P. J. (1975). One-step huber estimates in the linear model. Journal of the American Statistical Association , 70(350):428--434
work page 1975
-
[6]
Chen, K. and Lei, J. (2018). Network cross-validation for determining the number of communities in network data. Journal of the American Statistical Association , 113(521):241--251
work page 2018
-
[7]
Chen, Q., Agarwal, A., Fong, D. K., DeSarbo, W. S., and Xue, L. (2024). Model-based co-clustering in customer targeting utilizing large-scale online product rating networks. Journal of Business & Economic Statistics , pages 1--13
work page 2024
-
[8]
Erd\"os, P. and R\'enyi, A. (1959). On random graphs I. Publicationes Mathematicae Debrecen , 6:290--297
work page 1959
Show all 49 references
-
[9]
Fan, J., Xue, L., and Zou, H. (2014). Strong oracle optimality of folded concave penalized estimation. The Annals of Statistics , 42(3):819--849
2014
-
[10]
Fortunato, S. (2010). Community detection in graphs. Physics Reports , 486(3):75--174
2010
-
[11]
and Hric, D
Fortunato, S. and Hric, D. (2016). Community detection in networks: A user guide. Physics Reports , 659:1--44
2016
-
[12]
Gao, C., Ma, Z., Zhang, A., and Zhou, H. (2017). Achieving optimal misclassification proportion in stochastic block model. Journal of Machine Learning Research , 18:1--45
2017
-
[13]
Y., and Zhou, H
Gao, C., Ma, Z., Zhang, A. Y., and Zhou, H. H. (2018). Community detection in degree-corrected block models . The Annals of Statistics , 46(5):2153--2185
2018
-
[14]
Gao, J., Liang, F., Fan, W., Sun, Y., and Han, J. (2009). Graph-based consensus maximization among multiple supervised and unsupervised models. In Advances in Neural Information Processing Systems , page 585–593, New York. Curran Associates Inc
2009
-
[15]
X., Fienberg, S
Goldenberg, A., Zheng, A. X., Fienberg, S. E., and Airoldi, E. M. (2010). A survey of statistical network models. Foundations and Trends in Machine Learning , 2(2):129--233
2010
-
[16]
W., Laskey, K
Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social Networks , 5(2):109--137
1983
-
[17]
Hu, J., Zhang, J., Qin, H., Yan, T., and Zhu, J. (2021). Using maximum entry-wise deviation to test the goodness of fit for stochastic block models. Journal of the American Statistical Association , 116(535):1373--1382
2021
-
[18]
Huang, S., Sun, J., and Feng, Y. (2024). Pcabm: Pairwise covariates-adjusted block model for community detection. Journal of the American Statistical Association , 119(547):2092--2104
2024
-
[19]
Ji, M., Sun, Y., Danilevsky, M., Han, J., and Gao, J. (2010). Graph regularized transductive classification on heterogeneous information networks. In Machine Learning and Knowledge Discovery in Databases , pages 570--586, Berlin. Springer Berlin Heidelberg
2010
-
[20]
Jin, J. (2015). Fast community detection by SCORE . The Annals of Statistics , 43(1):57--89
2015
-
[21]
T., and Luo, S
Jin, J., Ke, Z. T., and Luo, S. (2024). Mixed membership estimation for social networks. Journal of Econometrics , 239(2):105369
2024
-
[22]
T., Luo, S., and Wang, M
Jin, J., Ke, Z. T., Luo, S., and Wang, M. (2023). Optimal estimation of the number of network communities. Journal of the American Statistical Association , 118(543):2101--2116
2023
-
[23]
and Newman, M
Karrer, B. and Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Physical Review E , 83:016107
2011
-
[24]
H., Xue, L., and Niu, X
Kim, B., Lee, K. H., Xue, L., and Niu, X. (2018). A review of dynamic network models with latent variables. Statistics Surveys , 12:105--135
2018
-
[25]
Koo, J., Tang, M., and Trosset, M. W. (2023). Popularity adjusted block models are generalized random dot product graphs. Journal of Computational and Graphical Statistics , 32(1):131--144
2023
-
[26]
Kumar, A., Sabharwal, Y., and Sen, S. (2004). A simple linear time (1+ )-approximation algorithm for k-means clustering in any dimensions. In 45th Annual IEEE Symposium on Foundations of Computer Science , pages 454--462, Rome. IEEE Symposium on Foundations of Computer Science
2004
-
[27]
and Rinaldo, A
Lei, J. and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models . The Annals of Statistics , 43(1):215 -- 237
2015
-
[28]
Li, T., Levina, E., and Zhu, J. (2020). Network cross-validation by edge sampling. Biometrika , 107(2):257--276
2020
-
[29]
and White, D
Moody, J. and White, D. R. (2003). Structural cohesion and embeddedness: A hierarchical concept of social groups. American Sociological Review , 68:103--127
2003
-
[30]
Noroozi, M., Pensky, M., and Rimal, R. (2021a). Sparse popularity adjusted stochastic block model. Journal of Machine Learning Research , 22(193):1--36
2021
-
[31]
Noroozi, M., Rimal, R., and Pensky, M. (2021b). Estimation and clustering in popularity adjusted block model. Journal of the Royal Statistical Society Series B: Statistical Methodology , 83(2):293--317
2021
-
[32]
Rohe, K., Chatterjee, S., and Yu, B. (2010). Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics , 39:1878--1915
2010
-
[33]
F., Yu, Y., and Feng, Y
Saldana, D. F., Yu, Y., and Feng, Y. (2017). How many communities are there? Journal of Computational and Graphical Statistics , 26(1):171--181
2017
-
[34]
and Chen, Y
Sengupta, S. and Chen, Y. (2017). A block model for node popularity in networks with community structure . Journal of the Royal Statistical Society Series B: Statistical Methodology , 80(2):365--386
2017
-
[35]
and Mirny, L
Spirin, V. and Mirny, L. A. (2003). Protein complexes and functional modules in molecular networks. Proceedings of the National Academy of Sciences , 100(21):12123--12128
2003
-
[36]
Su, L., Wang, W., and Zhang, Y. (2020). Strong consistency of spectral clustering for stochastic block models. IEEE Transactions on Information Theory , 66(1):324--338
2020
-
[37]
L., Tang, M., Fishkind, D
Sussman, D. L., Tang, M., Fishkind, D. E., and Priebe, C. E. (2011). A consistent adjacency spectral embedding for stochastic blockmodel graphs. Journal of the American Statistical Association , 107:1119 -- 1128
2011
-
[38]
Wang, B., Pourshafeie, A., Zitnik, M., Zhu, J., Bustamante, C., Batzoglou, S., and Leskovec, J. (2018). Network enhancement as a general method to denoise weighted biological networks. Nature Communications , 9:3108
2018
-
[39]
Wang, J., Zhang, J., Liu, B., Zhu, J., and Guo, J. (2020). Fast network community detection with profile-pseudo likelihood methods. Journal of the American Statistical Association , 118:1359--1372
2020
-
[40]
and Faust, K
Wasserman, S. and Faust, K. (1994). Social Network Analysis: Methods and Applications . Cambridge University Press, Cambridge
1994
-
[41]
Xu, M., Jog, V., and Loh, P. (2020). Optimal rates for community estimation in the weighted stochastic block model. The Annals of Statistics , 48(1):183--204
2020
-
[42]
Yu, L., He, Y., Kong, X., and Zhang, X. (2022). Projected estimation for large-dimensional matrix factor models. Journal of Econometrics , 229(1):201--217
2022
-
[43]
Yuan, M., Liu, R., Feng, Y., and Shang, Z. (2022). Testing community structure for hypergraphs. The Annals of Statistics , 50(1):147--169
2022
-
[44]
and Proutiere, A
Yun, S.-Y. and Proutiere, A. (2016). Optimal cluster recovery in the labeled stochastic block model. In Advances in Neural Information Processing Systems , pages 973--981, New York. Curran Associates, Inc
2016
-
[45]
Zhang, A. Y. and Zhou, H. H. (2016). Minimax rates of community detection in stochastic block models . The Annals of Statistics , 44(5):2252--2280
2016
-
[46]
and Cao, J
Zhang, J. and Cao, J. (2017). Finding common modules in a time-varying network with application to the drosophila melanogaster gene regulation network. Journal of the American Statistical Association , 112(519):994--1008
2017
-
[47]
and Chen, Y
Zhang, J. and Chen, Y. (2017). A hypothesis testing framework for modularity based network community detection. Statistica Sinica , 27(1):437--456
2017
-
[48]
Zhao, Y., Hao, N., and Zhu, J. (2024). Variational estimators of the degree-corrected latent block model for bipartite networks. Journal of Machine Learning Research , 25(150):1--42
2024
-
[49]
Zhao, Y., Levina, E., and Zhu, J. (2011). Consistency of community detection in networks under degree-corrected stochastic block models. The Annals of Statistics , 40:2266--2292
2011
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.