Pith. sign in

REVIEW 5 major objections 7 minor 34 references

Community Recovery on Noisy Stochastic Block Models

T0 review · 5 major / 7 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Two-stage spectral pipeline achieves exact community recovery in noisy latent-kernel stochastic block models at the classical sharp threshold, and lifts belief propagation's accuracy to 91.1% on Amazon.

desk verdict Novel algorithmic combination with two load-bearing proof gaps and a theory that never connects to the implemented methods; worth a serious referee, but not citable as proven. read the letter →

arxiv 2505.08251 v4 pith:UYZKDDRP submitted 2025-05-13 cs.SI math.PR

Washieu Anan , Gwyneth Liu This is my paper · ORCID
classification cs.SImath.PR
keywords communityrecoverystochasticblockmodellatent-spacegraphspectralclusteringgeometricdenoisingbeliefpropagationmotifattentionexact
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Community recovery—finding which nodes share a hidden group when edges also depend on unobserved geometric positions—is the task here. The paper proposes two linked tools: MASO, a spectral operator that weights edges by multi-hop co-occurrence and triangle support, and GeoDe, an iterative reweighting loop that alternately trusts community and geometry evidence. It claims that together they recover every label with high probability in a latent-kernel stochastic block model whenever $(\sqrt{c(\sigma)a}-\sqrt{c(\sigma)b})^2 > 2$, the sharp exact-recovery threshold of the underlying SBM. On a 2000-node Amazon product-metadata subgraph, using GeoDe+MASO as a denoising front end raises belief propagation's accuracy from 0.507 to 0.911, a 79.7% relative gain. A sympathetic reader would take the paper's central assertion to be that geometric noise can be stripped away algorithmically, not just absorbed into a noisier SBM.

What carries the argument

MASO (Motif-Attention Spectral Operator) builds random-walk PPMI embeddings, rescales adjacency weights by attention $A_{ij}\exp(\langle z_i,z_j\rangle/\sqrt{d})$, and mixes in triangle support $X_{ij}=\sum_{k\neq i,j}W_{ik}W_{kj}$ via $\tilde W_{ij}=(1-\beta)W_{ij}+\beta W_{ij}X_{ij}$, then spectrally clusters the normalized Laplacian $H=D^{-1/2}\tilde W D^{-1/2}$. GeoDe (Iterative Geometric Denoising) alternates a community-inference step and a geometry-inference step, shrinking low-confidence and boosting high-confidence edges under a decaying schedule until the weight matrix approaches a clean SBM. The load-bearing identity is the conditional expectation $\mathbb{E}[\tilde W_{ij}\mid z_i,z_j]$ from Lemma C.2, which shows the mixed weights concentrate around two values with an eigen-gap $\Theta(\log n)$; all recovery guarantees flow from that gap plus a matrix-Bernstein concentration bound and Davis–Kahan perturbation.

What would settle it

Take a latent-kernel SBM with parameters satisfying $(\sqrt{c(\sigma)a}-\sqrt{c(\sigma)b})^2>2$, compute the PPMI/SVD embeddings exactly as in Section 3.2, and measure the inner-product distributions for same-community versus different-community pairs. If those distributions overlap—so $\rho_{\mathrm{out}}$ is not strictly below $\rho_{\mathrm{in}}$—Theorem 3.1's precondition is violated, and a failure of MASO's exact recovery on graphs where the threshold holds would refute the claim that the guarantee covers the implemented algorithm.

Watch

Extended reading notes

Core claim

The paper's central claim is that exact community recovery in a latent-kernel SBM—where each edge probability is multiplied by a Gaussian kernel on latent positions—is achievable by a two-stage pipeline at the same sharp threshold as the classical SBM. The theorem states that if the embeddings entering MASO have a fixed cosine structure (inner product $\rho_{\mathrm{in}}$ for same-community pairs, $\rho_{\mathrm{out}}$ for different-community pairs), then the second eigenvector of the mixed motif-attention Laplacian followed by one local-flip pass recovers all labels with probability $1-o(1)$ whenever $(\sqrt{c(\sigma)a}-\sqrt{c(\sigma)b})^2>2$. It also claims GeoDe converges almost surely to the underlying SBM weight matrix under a stochastic-approximation schedule, provided the community and geometry edge sets are disjoint. Empirically the paper reports perfect recovery on synthetic graphs for noise $\sigma\ge 0.25$, and the Amazon validation shows the denoiser transfers to belief propagation.

Load-bearing premise

The load-bearing premise is that the embeddings fed into MASO have a fixed cosine geometry—same-community pairs always closer than different-community pairs—and the paper does not prove its random-walk PPMI plus SVD construction actually produces embeddings with that structure.

Editorial extensions

If this is right

  • If Theorem 3.1 holds, MASO achieves exact recovery exactly under the classical SBM threshold, so the asymptotic community-recovery limit is unaffected by geometric noise.
  • If Theorem 4.1 holds, GeoDe turns a latent-kernel SBM graph into a near-classical SBM, so downstream spectral or message-passing methods behave as if geometry were absent.
  • The Amazon experiment implies that real networks with latent-geometric edge formation can be preprocessed by GeoDe to unlock near-perfect label recovery in belief propagation without labeled data.
  • Because the threshold depends on $c(\sigma)$, geometric noise renormalizes the effective signal from $(a-b)$ to $c(\sigma)(a-b)$; denser graphs or larger bandwidths are then needed to compensate.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable extension the paper leaves implicit: the same two-stage denoiser should also boost non-spectral base algorithms, so running GeoDe before semidefinite-programming recovery would separate the denoising benefit from the base method.
  • The fixed-cosine-embedding assumption in Theorem 3.1 is strong enough that a direct empirical check—computing the inner-product distributions of PPMI/SVD embeddings on synthetic latent-kernel SBMs—would reveal whether the guarantee covers the implemented MASO or only an idealized version.
  • The reduction to a rescaled SBM suggests that latent-kernel versions of other recovery problems, including weak recovery and $K$-community models, should inherit the classical phase transitions with only $a,b$ replaced by $c(\sigma)a,c(\sigma)b$; the paper does not prove this extension.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 7 minor

Summary. The paper proposes two algorithms for community recovery in a latent-kernel stochastic block model with two communities: MASO, a motif-attention spectral operator built from PPMI embeddings and triangle-motif weighting, and GeoDe, an iterative geometric denoising scheme that alternately reweights edges based on community and geometry confidence. The main theoretical claims are that MASO achieves exact recovery when the classical SBM threshold (sqrt(c(σ)a) - sqrt(c(σ)b))^2 > 2 holds, and that GeoDe converges almost surely to the latent SBM weight matrix, yielding exact recovery under a spectral-gap condition. Empirical results are reported on synthetic latent-kernel SBMs and on a 2000-node Amazon co-purchasing subgraph, where GeoDe+MASO is said to improve belief propagation's accuracy from 0.507 to 0.911. The paper also states exact and weak recovery thresholds for the latent-kernel SBM based on a claimed contiguity reduction to the classical SBM.

Significance. If the theoretical claims were correct, the paper would be significant: it would provide a spectral method with exact-recovery guarantees in geometrically-noised SBMs and an unsupervised denoiser that substantially improves belief propagation on a real network. The empirical demonstration on the Amazon metadata subgraph is a useful data point, and the authors provide reproducible parameter tables and significance tests. However, the theoretical backbone is not sound: the two main theorems rest on unverified or circular assumptions, and a central concentration lemma contains a false independence claim. The claimed theoretical contributions are therefore not established, and the empirical evaluation alone is too limited to carry the paper.

major comments (5)
  1. [Appendix C.3, Lemma C.3] The proof claims that 'Independent edges give independent matrices {Y_e}', but this is false. The definition of \tilde W_{ij} includes X_{ij} = \sum_{k \neq i,j} W_{ik} W_{kj}, so \tilde W_{ij} depends on the two-hop edge indicators A_{ik} and A_{kj}. Consequently Y_{ij} and Y_{i\ell} are dependent because they share the indicators A_{ik} for k \neq i,j,\ell. Tropp's matrix Bernstein inequality cannot be applied to E = \sum_e Y_e. The asserted bound \|E\|_2 = O(\sqrt{\log n}) is unsupported, and Lemma C.5 and Theorem 3.1, which rely on this concentration result, do not follow.
  2. [Section 3.3, Theorem 3.1] The theorem fixes normalized embeddings with \langle z_i,z_j\rangle = \rho_{\rm in} for same-community pairs and \rho_{\rm out} for different-community pairs. However, the MASO construction in Section 3.2 uses random-walk PPMI followed by truncated SVD, and the paper never proves that this construction produces embeddings with the assumed two-point inner-product structure under the latent-kernel SBM. As stated, the exact-recovery guarantee applies to an abstract embedding model, not to the implemented MASO operator.
  3. [Section 4.1, Theorem 4.1] The theorem assumes A = W^* + G^* with G^* \geq 0 and diagonal projectors C and G satisfying C G^* = 0 and G W^* = 0. These assumptions directly encode the desired conclusion: W^* is the latent SBM matrix and G^* is geometry noise that is orthogonal to it. The proof then shows that a linear recursion of the form W^{(t+1)} = (I - \lambda_C^{(t)} C - \lambda_G^{(t)} G)W^{(t)} + \lambda_C^{(t)} C W^* - \lambda_G^{(t)} G G^* converges to W^*. But Algorithm 1 does not implement this recursion: it applies multiplicative reweighting to the union sets S = S_C \cup S_G and B = B_C \cup B_G, with separate shrink and boost factors. The theorem therefore does not analyze GeoDe and does not establish convergence from a latent-kernel SBM.
  4. [Appendix C.1, Theorem C.1] The proof states that 'for fixed D the variables (\Delta_{ij})_{(i,j) \in D} are independent'. This is false whenever D contains pairs sharing a vertex, because \Delta_{ij} and \Delta_{i\ell} both depend on the latent position x_i. The Hoeffding bound and the subsequent union bound therefore do not establish the claimed contiguity between the latent-kernel SBM and the classical SBM. The reduction that underlies the recovery thresholds stated in Section 2.2 is not proven.
  5. [Appendix C.4, Lemma C.4] The rank-2 representation S = \alpha \mathbf{1}\mathbf{1}^\top + \beta^* g g^\top does not follow from the expressions in Lemma C.2. In Lemma C.2, the expected same-community weight contains (n_+ - 2) w_{\rm in}^2 + n_- w_{\rm out}^2 and the different-community weight contains (n-2) w_{\rm in} w_{\rm out}; substituting these into the claimed formula yields an identity only under additional balanced-size and small-w approximations that are not stated. The eigen-gap \gamma = \Theta(\log n) is therefore not established.
minor comments (7)
  1. [Section 2.2] The exact and weak recovery thresholds are stated in the main text as facts, but the contiguity result on which they depend (Theorem C.1) is flawed as noted in major comment 4.
  2. [Section 4.1, step-size schedule] The theorem requires \sum_t \lambda_C^{(t)} = \infty and \sum_t (\lambda_C^{(t)})^2 < \infty, but only \sum_t (\lambda_G^{(t)})^2 < \infty is imposed. The claimed contraction of the G-component is not justified by the stated conditions.
  3. [Appendix C.5, Lemma C.5] The proof identifies the second eigenvector of S with g/\|g\| and uses \|g\|^2 = n. This holds only for exactly balanced communities, whereas Definition 2.1 draws labels independently with equal probability, so n_+ is random and only approximately n/2.
  4. [Section 5.1] The claim that MASO maintains perfect recovery up to \sigma \geq 0.5 is based on Figure 1 without error bars; the numerical values and the definition of 'perfect' (exact labels up to permutation) should be stated explicitly.
  5. [Reference [15]] Reference [15] is dated 2025 but corresponds to a 2014 arXiv preprint (arXiv:1406.1880); please correct the bibliographic details.
  6. [Section 5.2] The p-values for the Amazon experiment are reported, but the procedure for computing them (test statistic, null model, number of trials) is not described.
  7. [Algorithm 1] The thresholds and strengths are defined in Algorithm 1 but default values appear only in Appendix E.3; the main text should summarize the default parameter choices to make the experiments reproducible without reading the appendix.

Circularity Check

2 steps flagged · score 6.0 of 10

MASO exact-recovery and GeoDe convergence guarantees each assume the target structure rather than deriving it from the latent-kernel SBM; the novel algorithmic components are not analyzed from the model.

  1. self definitional [Theorem 3.1, Section 3.3 (proof in Appendix C.6)]
    "Fix normalized embeddings zi ∈ Rd with ⟨zi,zj⟩ = ρin if zi = zj, and ρout otherwise, 0 < ρout < ρin < 1. Form fW and H as above with any fixed β ∈ (0,1]. If (√(c(σ)a)−√(c(σ)b))² > 2, then as n→∞, the two-step procedure (second eigenvector of H plus one local-flip pass) recovers the true labels {zi} exactly with probability 1−o(1)."

    The theorem's only link from the latent-kernel SBM to the MASO algorithm is the hypothesis that MASO's embeddings already have perfect community-aligned cosine structure (ρ_in for same block, ρ_out for different blocks). Section 3.2's random-walk PPMI plus truncated SVD construction is never shown to produce such embeddings under Definition 2.1. Given that hypothesis, E[fW] is a two-block matrix and the spectral-gap plus Davis–Kahan argument is the classical SBM argument; the novel MASO components enter only through an assumed input. The exact-recovery guarantee for the implemented operator is therefore the target spectral separation restated as a hypothesis, not a consequence derived from the model.

  2. self definitional [Theorem 4.1, Section 4.1 (proof in Appendix C.9)]
    "Assume the observed adjacency matrix decomposes as A = W⋆ + G⋆, G⋆ ⪰ 0. Let C and G be diagonal projectors onto the (disjoint) edge sets updated by the community and geometry rules, so that CG⋆ = 0 and GW⋆ = 0. ... Under these step sizes, W(t) a.s. −→ W⋆ and the true community partition is recovered exactly whenever the SBM eigen-gap satisfies the usual K-cluster signal condition."

    The projectors C and G are defined as the edge sets updated by the community and geometry rules and are assumed to annihilate exactly the opposite component (CG*=0 and GW*=0). This means the update rules are assumed to already know the W*/G* split—the very information GeoDe is supposed to learn from the noisy graph. Given this, the recursion contracts the G* component and leaves W* unchanged, so convergence to W* is built into the definition of C and G. The stochastic-approximation and Robbins–Siegmund argument verifies a consequence of the oracle assumption rather than the algorithm's ability to find the split. The theorem's conclusion is thus the assumption stated in different notation.

full rationale

Two load-bearing theoretical claims reduce to their own hypotheses rather than deriving the novel mechanism from the model. Theorem 3.1 assumes MASO's embeddings already have block-constant cosine inner products, which is exactly the community-aligned signal the PPMI/SVD stage is supposed to produce; no proof shows that stage yields ρ_in/ρ_out structure under the latent-kernel SBM. Theorem 4.1 assumes the community and geometry projectors are perfectly separated (CG*=0, GW*=0), i.e., that GeoDe's update rules already know which edges are geometry-induced; convergence to W* is then a consequence of that oracle separation. The classical SBM exact/weak recovery thresholds are external known results and the empirical comparisons are independent, which prevents a higher score. The manuscript also contains a serious non-circular proof defect: Lemma C.3's matrix-Bernstein argument treats Y_e as independent despite overlapping two-hop edge dependencies, but that is a correctness issue, not a circularity, so it is noted here rather than counted as a circular step. There are no load-bearing self-citations by the authors. Overall, the central algorithmic guarantees are partially circular because the target recovery is encoded in the assumptions.

Assumptions & free parameters 9 free parameters · 5 assumptions · 0 invented entities

The central claims rest on the latent-kernel SBM model, on an unverified embedding structure in Theorem 3.1, and on an additive decomposition with orthogonal projectors in Theorem 4.1. The algorithms also depend on a large set of hand-chosen hyperparameters.

free parameters (9)
  • rho_in, rho_out (embedding inner products in Theorem 3.1) = unspecified; 0 < rho_out < rho_in < 1 assumed
    The theorem fixes these constants and assumes the embeddings have the exact separation needed for a rank-two signal. No derivation from the PPMI step is provided.
  • MASO mixing weight beta = 0.3
    Hand-chosen in Table 3; controls the balance between one-hop attention and triangle-reinforced weights.
  • MASO PPMI/embedding parameters = dim=64 (Amazon/synthetic), dim=1 (Karate); walk_len=40 or 2; window=5; num_walks=10 or 2; clip_max=1e-2
    Hand-chosen in Table 3; the embedding geometry these produce is never analyzed, yet it is the input to Theorem 3.1.
  • GeoDe geometry cluster count B = 32 (Amazon/synthetic), 6 (Karate)
    Hand-chosen in Table 2; B controls how geometric formations are separated from community structure.
  • GeoDe percentile thresholds tau_C, tau_G, tau_C+, tau_G+ = 0.90, 0.90, 0.97, 0.97 (default); 0.96, 0.96, 0.995, 0.995 for noise-run
    Hand-chosen in Table 2; these thresholds entirely determine shrink and boost edge sets.
  • GeoDe shrink/boost strengths = shrink_comm=1.00, shrink_geo=0.80, boost_comm=0.60, boost_geo=0.40
    Hand-chosen in Table 2; these set the multiplicative edge-weight update magnitudes.
  • GeoDe weight bounds w_min, w_cap = 5e-2, 4.0
    Hand-chosen in Table 2; caps guarantee spectral stability but distort the claimed convergence to W*.
  • GeoDe iteration and stopping parameters = T=100/50/100, anneal_steps=20/6/20, warmup_rounds=2, patience=10/7/10, seed=42/0/42
    Hand-chosen in Table 2; no sensitivity analysis is provided, so the reported gains may depend on these choices.
  • Theorem 4.1 step-size sequences lambda_C, lambda_G = positive sequences with sum lambda_C = infinity, sum lambda_C^2 < infinity, lambda_G <= gamma lambda_C
    The theorem requires these schedule conditions, but experiments state a linear decay schedule, which does not meet the asymptotic sum condition.
assumptions (5)
  • domain assumption Latent positions x_i are iid Uniform([0,1]^d) and community labels are balanced and independent.
    Definition 2.1 defines the model; all theorems inherit this.
  • domain assumption Edge probabilities conditional on latent positions follow the exponential kernel exp(-||x_i-x_j||^2/(2 sigma^2)) with constants a and b.
    Definition 2.1; the claimed reduction to a classical SBM and all thresholds depend on this kernel.
  • ad hoc to paper Theorem 3.1 takes fixed normalized embeddings with <z_i,z_j> = rho_in for same-block pairs and rho_out for different-block pairs.
    No proof is given that the PPMI+SVD embeddings in Section 3.2 satisfy this structure; the signal in E[W_tilde] is essentially assumed.
  • ad hoc to paper Theorem 4.1 assumes A = W* + G* with G* >= 0 and diagonal projectors C, G satisfying C G* = 0 and G W* = 0.
    This decomposition is not implied by the latent-kernel SBM and is not how GeoDe's data-dependent edge sets are generated.
  • standard math Standard results used include SBM recovery thresholds, matrix Bernstein, Davis-Kahan, and Robbins-Siegmund theorems.
    The paper relies on these tools; no formal verification is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Community Recovery on Noisy Stochastic Block Models." pith.science (2026). https://pith.science/paper/UYZKDDRP

@misc{pith2026250508251,
  author       = {Pith},
  title        = {Pith review of: Community Recovery on Noisy Stochastic Block Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UYZKDDRP}},
  note         = {Machine review of arXiv:2505.08251}
}
read the original abstract

We study the problem of community recovery in geometrically-noised stochastic block models (SBM). This work presents two primary contributions: (1) Motif--Attention Spectral Operator (MASO), an attention-based spectral operator that improves upon traditional spectral methods; and (2) Iterative Geometric Denoising (GeoDe), a configurable denoising algorithm that boosts spectral clustering performance. We demonstrate that the fusion of GeoDe+MASO significantly outperforms existing community detection methods on noisy SBMs. Furthermore, we show that using GeoDe+MASO as a denoising step improves belief propagation's community recovery by 79.7% on the Amazon Metadata dataset.

Figures

Figures reproduced from arXiv: 2505.08251 by the authors.

Figure 1
Figure 1. Left: Average clustering accuracy of four spectral operators as a function of the geometric– noise parameter σ;“MASO” denotes our Motif–Attention Spectral Operator; “Non–Backtracking (Control)” uses the non–backtracking matrix; “Bethe–Hessian (Control)” is the classical Bethe– Hessian operator; and “Motif–Laplacian (Control)” is the unmodified motif Laplacian. Right: End–to–end community–recovery accuracy of the Geo… view at source ↗
Figure 2
Figure 2. (a) Ablation on MASO+GeoDe vs. σ. (b) We show that GeoDe adjusts weights so to capture geometric properties. We calculate a noise metric N k via fitting a linear model to predict edge weights from distance and finding the mean-squared residual. Our noise metric captures how the edge weights in GeoDe capture geometric features (see Appendix E.2 for details). 5.2.2 Future Work: Feasibility of GeoDe for Large Networks … view at source ↗
Figure 3
Figure 3. Empirical Recovery Threshold Validation D.4 Runtimes For graphs with n vertices and m ≈ O(n) edges, the algorithms utilized in this paper demonstrate the following asymptotic runtimes and memory footprints: Method Time Complexity Memory Footprint MASO O(Lm) + O(m3/2 ) O(Lm) Bethe-Hessian [15] O(k(n + m)) O(n + m) Non-Backtracking [23] O(km) O(m) Motif-Laplacian [16] O(m3/2 ) + O(k(n + m)) O(m3/2 Belief-Propagation [… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 17 canonical work pages

  1. [1]

    Community detection in graphs

    Santo Fortunato. Community detection in graphs. Physics Reports, 486:75–174, 02 2010. doi: 10.1016/j.physrep.2009.11.002. URL https://arxiv.org/pdf/0906.0612.pdf

    arXiv 2010

  2. [2]

    Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt

    Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5:109–137, 06 1983. doi: 10.1016/0378-8733(83)90021-7

    doi:10.1016/0378-8733(83)90021-7 1983

  3. [3]

    Latent space approaches to social network analysis

    Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association, 97:1090–1098, 12 2002. doi: 10.1198/016214502388618906

    doi:10.1198/016214502388618906 2002

  4. [4]

    Spectral clustering and the high-dimensional stochastic blockmodel

    Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the high-dimensional stochastic blockmodel. Annals of Statistics, 39, 08 2011. doi: 10.1214/11-aos887

    doi:10.1214/11-aos887 2011

  5. [5]

    Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

    Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84, 12 2011. doi: 10.1103/physreve.84.066106

    doi:10.1103/physreve.84.066106 2011

  6. [6]

    Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms

    Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms, 2015. URL https://arxiv.org/abs/ 1503.00609

    work page Pith review arXiv 2015

  7. [7]

    Improved graph clustering

    Yudong Chen, Sujay Sanghavi, and Huan Xu. Improved graph clustering. IEEE Transactions on Information Theory, 60:6440–6455, 08 2014. doi: 10.1109/tit.2014.2346205

    arXiv 2014

  8. [8]

    Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

    Bruce Hajek, Yihong Wu, and Jiaming Xu. Achieving exact cluster recovery threshold via semidefinite programming, 2016. URL https://arxiv.org/abs/1412.6156

    work page Pith review arXiv 2016

Show all 34 references
  1. [9]

    On semidefinite relaxations for the block model, 2016

    Arash A Amini and Elizaveta Levina. On semidefinite relaxations for the block model, 2016. URL https://arxiv.org/abs/1406.5647

    2016 arXiv

  2. [10]

    The geometric block model, 2017

    Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Barna Saha. The geometric block model, 2017. URL https://arxiv.org/abs/1709.05510

    2017 arXiv

  3. [11]

    V ogelstein, and Carey E

    Shangsi Wang, Jesus Arroyo, Joshua T. V ogelstein, and Carey E. Priebe. Joint embedding of graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43:1324–1336, 04

  4. [12]

    Brian Karrer and M. E. J. Newman. Stochastic blockmodels and community structure in networks. Physical Review E, 83, 01 2011. doi: 10.1103/physreve.83.016107

    2011 doi

  5. [13]

    Regularized spectral clustering under the degree-corrected stochastic blockmodel

    Tai Qin and Karl Rohe. Regularized spectral clustering under the degree-corrected stochastic blockmodel. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2...

    2013

  6. [14]

    Attention is all you need, 06 2017

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 06 2017. URL https://arxiv. org/abs/1706.03762

    2017 arXiv

  7. [15]

    Spectral clustering of graphs with the bethe hessian, 2025

    Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the bethe hessian, 2025. URL https://arxiv.org/abs/1406.1880

    2025 arXiv

  8. [16]

    A. R. Benson, D. F. Gleich, and J. Leskovec. Higher-order organization of complex networks. Science, 353:163–166, 07 2016. doi: 10.1126/science.aad9029

    2016 doi

  9. [17]

    Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing, 2019

    Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing, 2019. URL https://arxiv.org/abs/ 1905.00067. 10

    2019 arXiv

  10. [18]

    The dynamics of viral marketing

    Jure Leskovec, Bernardo A Huberman, and Hp Labs. The dynamics of viral marketing. ACM Trans. Web ACM Transactions on the Web, 1, 2007. doi: 10.1145/1232722.1232727. URL https://www.cs.cmu.edu/~jure/pubs/viral-tweb.pdf

    2007

  11. [19]

    Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Compu- tational Mathematics, 12:389–434, 08 2011. doi: 10.1007/s10208-011-9099-z

    2011 doi

  12. [20]

    The rotation of eigenvectors by a perturbation

    Chandler Davis and Kahan W M. The rotation of eigenvectors by a perturbation. iii. SIAM Journal on Numerical Analysis, 7:1–46, 1970. doi: 10.2307/2949580. URL https://www. jstor.org/stable/2949580

    1970

  13. [21]

    Reconstruction and estimation in the planted partition model

    Elchanan Mossel, Joseph Neeman, and Allan Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162:431–461, 07 2014. doi: 10.1007/ s00440-014-0576-6

    2014

  14. [22]

    Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs, 2015

    Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs, 2015. URL https: //arxiv.org/abs/1501.06087

    2015 arXiv

  15. [23]

    A unified framework for spectral clustering in sparse graphs

    Lorenzo Dall’Amico, Romain Couillet, and Nicolas Tremblay. A unified framework for spectral clustering in sparse graphs. arXiv (Cornell University), 01 2020. doi: 10.48550/arxiv.2003. 09198

    2020 doi

  16. [24]

    Belief propagation, robust reconstruction and optimal recovery of block models

    Elchanan Mossel, Joe Neeman, and Allan Sly. Belief propagation, robust reconstruction and optimal recovery of block models. The Annals of Applied Probability , 26, 08 2016. doi: 10.1214/15-aap1145

    2016 doi

  17. [25]

    Community recovery in the geometric block model

    Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Barna Saha. Community recovery in the geometric block model. Journal of Machine Learning Research, 24:1–53, 2023. URL https://www.jmlr.org/papers/v24/22-0572.html. 11 7 Appendix A Helper functions described in GeoDe 1 Funct...

    2023

  18. [27]

    For every unordered edgee ={i,j} set Ye = fWij− EfWij eie⊤ j +eje⊤ i , soE =P eYe and EYe = 0.4 Independent edges give independent matrices{Ye}

    WritingE as a sum of independent matrices. For every unordered edgee ={i,j} set Ye = fWij− EfWij eie⊤ j +eje⊤ i , soE =P eYe and EYe = 0.4 Independent edges give independent matrices{Ye}. 4ei is the i-th standard basis vector in Rn. 14

  19. [28]

    Letwin/out =pin/out exp(ρin/out/ √ d) = Θ (logn)/n

    Uniform bound on∥Ye∥2. Letwin/out =pin/out exp(ρin/out/ √ d) = Θ (logn)/n . Because Aij≤ 1,|Wij|≤ C1 logn n for some constantC1 =C1(a,b,σ,ρ in/out). For anyi̸=j,|WikWkj|≤ C 2 1(logn/n)2, and there are at mostn− 2 summands inXij; hence |Xij| ≤C 2 1 (logn)2 n . Multiplying,|WijX...

  20. [29]

    DefineV =P e E[Y 2 e ]

    Variance proxy. DefineV =P e E[Y 2 e ]. BecauseYe has only two non-zero entries in rowsi,j , ∥V∥2 ≤ max u∈V X v̸=u E (fWuv− EfWuv)2 . Any pair (u,v ) is intra-block with probability n+(n+−δuv)+n−(n−−δuv) n(n−1) and inter-block otherwise, but (fWuv− EfWuv)2≤L2. Hence ∥V∥2 ≤ nL ...

  21. [30]

    Tropp’s matrix Bernstein inequality [19] gives for any t> 0 Pr ∥E∥2≥t ≤ 2n exp − t2/2 σ2+Lt/3

    Matrix Bernstein. Tropp’s matrix Bernstein inequality [19] gives for any t> 0 Pr ∥E∥2≥t ≤ 2n exp − t2/2 σ2+Lt/3 . InsertL andσ2 from (1)–(2) and chooset =κ√logn withκ> 3√Cv. ThenLt/3≤σ2/2 for alln large, and Pr ∥E∥2≥κ p logn ≤ 2n exp −(κ2/4) =n− κ2/4−1 . Takingκ> 4 makes the e...

  22. [31]

    With probability at least 1−O(n−2),∥E∥2≤κ√logn, i.e.∥E∥2 =O(√logn) as claimed

    Conclusion. With probability at least 1−O(n−2),∥E∥2≤κ√logn, i.e.∥E∥2 =O(√logn) as claimed. C.4 Proof of Lemma C.4 Lemma C.4 (Eigen-gap of the signal) . Define S = E[fW ]. Then S has rank 2, and its second eigenvalue γ = λ2(S) = 1 2 (win−wout) 1−β +βκn n = Θ(logn). Proof of Lem...

  23. [32]

    BecauseS is symmetric,λ3(S) = 0 andγ =λ2(S)−λ3(S)> 0

    Davis–Kahan angle bound. BecauseS is symmetric,λ3(S) = 0 andγ =λ2(S)−λ3(S)> 0. The sin–Θ form of the Davis–Kahan theorem [20, Theorem 4] states sin ∠(ˆv,v 2) ≤ ∥E∥2 γ . (1) By Lemma C.3,∥E∥2 =O(√logn), and Lemma C.4 givesγ = Θ(logn); hence sin ∠(ˆv,v 2) =O (logn)−1/2 . (2)

  24. [33]

    Letgi =±1 be the planted labels and notev2 =g/∥g∥ with∥g∥2 =n+ +n− =n

    Translating angle to Hamming error. Letgi =±1 be the planted labels and notev2 =g/∥g∥ with∥g∥2 =n+ +n− =n. Write ˆv = cosθv 2 + sinθu whereθ = ∠(ˆv,v 2) andu⊥v2,∥u∥ = 1. Then for each vertexi ˆvi−v2,i ≤ 2 sinθ. A sign mistake occurs only if ˆviv2,i < 0, which requires|ˆvi−v2,i...

  25. [34]

    Combining (1)–(3) we have sin ∠(ˆv,v 2)≤∥E∥2 γ =O (logn)−1/2 , #{errors} =o(n), completing the proof

    Conclusion. Combining (1)–(3) we have sin ∠(ˆv,v 2)≤∥E∥2 γ =O (logn)−1/2 , #{errors} =o(n), completing the proof. C.6 Proof of Theorem 3.1 Proof. By Lemma C.2 the signal gap ∆ = E[fWij | zi = zj]E[fWij | zi ̸= zj] is amplified to Θ(logn). Lemma C.3 shows the noise satisfies∥E∥...

  26. [2021]

    doi: 10.1109/tpami.2019.2948619

    2019

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.