Community Recovery on Noisy Stochastic Block Models
Gwyneth Liu†, Washieu Anan†, † denotes equal contribution · 2025
Read Community Recovery on Noisy Stochastic Block Models by Gwyneth Liu†, Washieu Anan†, † denotes equal contribution (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08251.txt.
Introduction
Washieu Anan and Gwyneth Liu improved group finding in networks blurred by geometry noise. Their paper, from twenty twenty-five, deals with stochastic block models, a base frame for networks with group structure. Noise in node spots can hide those groups. The team gave two tools. One is a spectral operator with an attention step that beats plain spectral ways. The other is a denoising routine that can be set to the task.
Joined, the two tools beat past group finders on noisy models by a wide gap. Used as a clean up step, they lifted a belief based method's score by a large share on a real Amazon data set. Readers in network science get a fix for group reads in messy data.
Catalog record
| CREATOR | Gwyneth Liu†, Washieu Anan†, † denotes equal contribution |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-08251
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Community Recovery on Noisy Stochastic Block Models Gwyneth Liu†, Washieu Anan†, † denotes equal contribution 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 demonstrate that using GeoDe + MASO as a denoising step improves belief propagation’s community recovery by 79.7% on the Amazon Metadata dataset. 1 Introduction Community recovery, the task of identifying groups of nodes that are more densely connected internally than externally, is a fundamental problem in network analysis. It plays a critical role in diverse applications, including uncovering social circles, inferring biological processes, and mapping collaborative or transactional structures [ 1 ] . The stochastic block model (SBM) provides a well-established probabilistic framework for studying community structure [ 2 ] . However, traditional SBMs assume that edge formation depends solely on community membership, neglecting latent geometric or attribute-driven interactions that often influence real-world networks. For instance, in social or recommendation systems, connections frequently depend on unobserved features such as user interests or product similarities, which induce geometric noise in the observed graph [ 3 ] . To capture this complexity, latent-space SBMs extend the classical model by embedding nodes in an unobserved metric space, where edge probabilities decay with latent distance via a kernel function. While this model better reflects real-world phenomena, it significantly complicates the community recovery task, especially in sparse or noisy regimes. Early work on spectral clustering showed that the leading eigenvectors of the adjacency or Laplacian matrices, followed by k -means, achieve both partial and exact recovery of community labelings down to the information-theoretic thresholds in balanced two-block SBMs [ 4 , 5 ] . Belief propagation (BP) and its linearized or non-backtracking variants are known to attain the Kesten–Stigum threshold for weak recovery in sparse SBMs, and more recent analyses establish their near-optimal performance (both in accuracy and computational cost) in multi-block settings [ 6 , 5 ] . Convex relaxation approaches, semidefinite programs (SDPs) and spectral-norm minimizations, provide alternative exact recovery guarantees, often with robustness to slight model misspecifications [ 7 , 8 , 9 ] . Geometric SBMs models that incorporate latent-space geometry or kernel functions generalize the SBM to settings where proximity in an unobserved feature space influences edge formation. Triangle-counting and local clustering coefficient tests achieve near-optimal detection in the geometric block model [ 10 ] , while recent spectral embedding methods reconstruct both community labels and latent positions by smoothing the observed adjacency with kernel estimates [ 11 ] . This paper addresses the challenge of robust community recovery in geometrically-noised networks through two key contributions: • Motif Attention Spectral Operator (MASO) : A spectral method that enhances robustness by combining multi-hop co-occurrence embeddings with triangle-motif–based attention weighting, improving community signal under noise and degree variability. • GeoDe (Geometric Denoising) : An iterative, unsupervised reweighting scheme that alternates between community inference and geometry-aware updates, progressively aligning the graph structure with latent block organization. We provide theoretical guarantees showing that MASO and GeoDe achieve exact recovery under sharp thresholds for latent-kernel SBMs. Empirical evaluations on both synthetic and real-world networks demonstrate significant improvements over existing baselines, establishing our methods as effective tools for community recovery in noisy, structured networks. The remainder of the paper is organized as follows. Section 2 formalizes the latent-kernel SBM and establishes its connection to classical SBM recovery thresholds. Section 3 introduces the MASO operator, detailing its construction and theoretical recovery guarantees. In Section 4 , we present the GeoDe algorithm, including its iterative reweighting scheme and convergence analysis. Section 5 reports empirical evaluations on synthetic and real-world networks, demonstrating the effectiveness of our methods. Finally, Section 6 summarizes our findings and outlines directions for future work. 2 Frameworks This section introduces the Latent-Kernel SBM, which models networks where edge formation depends on both community membership and latent geometric proximity. We formally define the model, show its asymptotic equivalence to a classical SBM, and derive recovery thresholds that account for geometric noise. 2.1 Latent-Kernel SBM The latent-kernel SBM leverages an exponential kernel in edge formation between intra- and inter-community vertices, and is defined as follows: Definition 2.0 (Latent-Kernel SBM) . Let n\in\mathbb{N} , latent dimension d>0 , constants a,b>0 , and kernel bandwidth \sigma>0 . The latent-kernel SBM generates a graph G=(V,E) with V=\{1,\ldots,n\} and two communities via: 1. Latent positions: For each i\in V , draw x_{i}\sim\text{Unif}([0,1]^{d}) independently. 2. Community labels: Assign labels z_{i}\in\{+1,-1\} independently with equal probability. 3. Kernel constant: c(\sigma)=\mathbb{E}_{x,y\sim\text{Unif}([0,1]^{d})}\left[\exp\left(-\frac{\|x-y\|^{2}}{2\sigma^{2}}\right)\right]. 4. Edge probabilities: For each unordered pair \{i,j\}\subset V , p_{ij}=\begin{cases}a\cdot\frac{\log n}{n}\cdot c(\sigma),&\text{if }z_{i}=z_{j},\\ b\cdot\frac{\log n}{n}\cdot c(\sigma),&\text{if }z_{i}\neq z_{j},\end{cases} and include edge \{i,j\} independently with probability p_{ij} . p_{\text{in}}=p_{ij} if z_{i}=z_{j} and p_{\text{out}}=p_{ij} otherwise. This model combines block structure with latent similarity, where the exponential kernel attenuates edge probabilities based on distance. In fact, the latent-kernel SBM reduces to the original SBM where p_{\text{in}}=c(\sigma)\frac{a\log n}{n} and p_{\text{out}}=\frac{b\log n}{n} . This reduction is proved in Appendix C.1 . 2.2 Weak and Exact Recovery Because our latent-kernel SBM reduces to the classical SBM under the rescaling p_{\text{in}}=c(\sigma)\frac{a\log n}{n} and p_{\text{out}}=c(\sigma)\frac{b\log n}{n} where a>b>0 , we can apply SBM recovery thresholds to determine recover-ability in our model. We define exact recovery of the community labels if there exists an estimator \hat{z} that matches the true labeling z perfectly with high probability and define weak recovery of the community labels if there exists an estimator \hat{z} where the overlap between \hat{z} and z exceeds random guessing by a fixed margin \epsilon , with probability tending to one. Exact definitions are provided in Appendix B.1 . The proof of the latent-kernel SBM reducing to a classical SBM is provided in Appendix C.3 . The exact and weak recovery thresholds for the SBM are: • Exact Recovery: \bigl(\sqrt{c(\sigma)\,a}-\sqrt{c(\sigma)\,b}\bigr)^{2}>2. • Weak Recovery: \left(c(\sigma)a-c(\sigma)b\right)^{2}>2\bigl(c(\sigma)a+c(\sigma)b\bigr). Both the proofs for the exact and weak recovery thresholds are provided in the Appendix sections C.7 and C.8 ). 3 Motif Attention Spectral Operator (MASO) This section introduces the Motif Attention Spectral Operator (MASO), a spectral method designed to enhance community detection in networks perturbed by latent geometric noise. MASO leverages motif-based attention to selectively amplify informative structural signals, enabling robust recovery in sparse and geometrically contaminated graphs. 3.1 Motivation One-hop spectral methods such as the Bethe–Hessian attain the Kesten–Stigum threshold in sparse SBMs but collapse under heavy-tailed degrees and kernel-induced geometric noise, which shrink spectral gaps and introduce spurious edges [ 4 ] . Motif-Laplacians bolster community signals by counting triangles, but they incur high computational cost, break down when motif occurrences are sparse or uneven, and may overemphasize dense subgraphs at the expense of broader structure [ 12 ] , [ 13 ] . To overcome these limitations, MASO first builds multi-hop positive-pointwise mutual information (PPMI) embeddings and applies Transformer-style attention to smooth one-hop affinities, then reinforces each weight by its two-hop (triangle) support—balancing local motif denoising with global community structure [ 14 ] . 3.2 Description of MASO The