SBM With Multiple Samples: Improved Spectral Recovery
Sie Hendrata Dharmawan, Peter Chin · 2026
Read SBM With Multiple Samples: Improved Spectral Recovery by Sie Hendrata Dharmawan, Peter Chin (2026) 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-2606-24141.txt.
Introduction
Dharmawan and Chin show that several networks sampled from the same community structure make those communities provably easier to find. Community detection in the two-block stochastic block model asks an algorithm to recover two hidden groups from a random graph. Links within a group are likelier than links between groups. Their 2026 setting assumes multiple independent graph samples from the same distribution. That fits data arriving as repeated snapshots.
Averaging the samples before spectral partitioning shrinks the error sharply. The signal needed for reliable recovery falls by a factor equal to the sample count, so the error bound improves fast as samples grow. Tests on graphs up to a thousand nodes, with up to nine samples, confirm the bounds are sharp. Even two or three samples transform recovery accuracy.
Catalog record
| CREATOR | Sie Hendrata Dharmawan, Peter Chin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.24141
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SBM With Multiple Samples: Improved Spectral Recovery Sie Hendrata Dharmawan, Peter Chin Abstract We study community detection in the two-block stochastic block model under the setting where multiple independent graph samples drawn from the same distribution are available. Building on a recently simplified spectral algorithm that preserves the independence of adjacency matrix entries throughout, we show that averaging m m independent samples before applying spectral partitioning reduces the error bound γ \gamma exponentially in m m : specifically, one can find a γ \gamma -correct partition with probability 1 − o ( 1 ) 1-o(1) whenever ( a − b ) 2 a + b ≥ C m log 2 γ \frac{(a-b)^{2}}{a+b}\geq\frac{C}{m}\log\frac{2}{\gamma} , improving the single-sample requirement by a factor of m m . The key technical contribution is a multi-sample analogue of the spectral norm bound on the noise matrix, which propagates through the Davis–Kahan subspace angle analysis to yield the improved recovery guarantee. We provide experimental validation across a range of graph sizes ( n n up to 1000 1000 ) and sample counts ( m m up to 9 9 ), demonstrating that the derived bounds are sharp and that even two or three samples yield dramatic improvements in recovery accuracy. Our results offer a rigorous theoretical foundation for graph data augmentation strategies used in modern graph representation learning. 1 Introduction Community detection in graphs has emerged as a foundational subroutine in modern graph-based learning systems, including graph neural networks (GNNs). The stochastic block model provides a canonical generative framework for benchmarking such systems: the ability of a GNN or spectral embedding layer to recover planted community structure is increasingly used as a proxy for its representational power and generalization behavior. Moreover, the multi-sample setting studied in this paper has a direct analogue in graph learning pipelines, where multiple snapshots of a dynamic network — or multiple augmented views of a graph in contrastive self-supervised learning — are aggregated before being passed to a downstream classifier. Our theoretical analysis of how averaging independent graph samples improves spectral recovery can therefore be understood as a rigorous characterization of a data augmentation strategy widely employed in graph representation learning, providing the kind of theoretical grounding that the neural network community increasingly seeks for empirically successful techniques. The stochastic block model (SBM) serves as a prominent theoretical framework for analyzing this problem. In its simplest form, the model consists of two equal-sized blocks V_{1} and V_{2} , each containing n vertices. A random graph is generated according to the following distribution: edges between vertices within the same block occur with probability \frac{a}{n} , while edges between vertices in different blocks occur with probability \frac{b}{n} , where a>b>0 . Given such a graph, various algorithms exist for block recovery [ 3 ] , [ 2 ] , [ 7 ] , [ 10 ] , [ 4 ] . In particular, Chin et al. introduced a spectral algorithm that achieves exponential bounds on the incorrect recovery rate in the case of a sparse graph [ 3 ] . The original spectral algorithm includes a preprocessing step in which certain rows and columns of the adjacency matrix (specifically, those corresponding to vertices whose degree deviates significantly from its expectation) are deleted or modified before the eigendecomposition is performed. While this step is analytically convenient for controlling the spectral norm of the noise matrix, it introduces a subtle but consequential complication: once rows and columns are modified based on observed degree, the entries of the resulting matrix are no longer independently distributed, because whether a given entry is retained depends on the degrees of its incident vertices, which are functions of the entire row and column. This loss of independence makes it difficult to apply standard probabilistic tools (such as concentration inequalities for sums of independent random variables) to the modified matrix, and it considerably complicates any analysis that must track the joint behavior of entries across multiple samples. In [ 6 ] , Dharmawan and Chin show that this deletion-and-modification step is in fact unnecessary: the same asymptotic recovery guarantees, including the exponential bound on the incorrect recovery rate, are achievable by running the spectral algorithm directly on the unmodified adjacency matrix. By removing the preprocessing step, [ 6 ] preserves the independence of matrix entries throughout the entire algorithm, and it is precisely this independence that makes the multi-sample analysis of the present paper tractable. In this paper, we investigate the scenario that involves multiple samples (graphs) drawn from an identical distribution. We show that each additional sample reduces the incorrect recovery rate, establish the asymptotic relationship between recovery accuracy and sample size, and provide experimental evidence for the sharpness of this relationship. In the sparse graph case, with high probability, the linear fraction of isolated vertices [ 1 ] makes exact recovery impossible with high probability. In denser regimes, isolated vertices vanish and exact recovery becomes attainable, as our experiments confirm. In sparse regimes, although we cannot guarantee perfect recovery, we can still accurately recover a substantial portion of each block. Formally, we would like to find a partition of V_{1}^{\prime},V_{2}^{\prime} of V=V_{1}\cup V_{2} such that V_{i} and V_{i}^{\prime} are very close to each other. To quantify the recovery accuracy, we introduce the following definition: Definition 1 . A collection of subsets V_{1}^{\prime},V_{2}^{\prime} of V_{1}\cup V_{2} is \gamma -correct if |Vi\cap V_{i}^{\prime}|\geq(1-\gamma)n,i=1,2 . We would like to devise an algorithm that can guarantee \gamma -correctness for small \gamma with high probability in polynomial time. In [ 4 ] , Coja-Oghlan proved Theorem 1.1 For any constant \gamma>0 , there exist constants C_{1},C_{2}>0 such that if a,b>C_{1} and \frac{(a-b)^{2}}{a+b}>C_{2}\log(a+b) , one can find a \gamma -correct partition using a polynomial time algorithm. Coja-Oghlan proved Theorem 1.1 as part of a more general problem, and his algorithm was rather involved. In [ 3 ] , Chin et. al. proved Theorem 1.2 There are constants C_{1},C_{2}>0 such that the following holds. For any constants a>b>C_{1} and \gamma>0 satisfying \frac{(a-b)^{2}}{a+b}\geq C_{2}\log\frac{2}{\gamma} (1) one can find a \gamma -correct partition with probability 1-o(1) using a simple spectral algorithm. Theorem 1.2 improves the relation between the accuracy \gamma and the ratio \frac{(a-b)^{2}}{a+b} . Moreover, this bound is asymptotically sharp because according to [ 11 ] , there exists a constant c>0 such that when \frac{(a-b)^{2}}{a+b}\leq c\log\frac{1}{\gamma} (2) one cannot recover a \gamma -correct partition (in expectation), regardless of the algorithm. However, the spectral algorithm presented in [ 3 ] and the corresponding proof have several steps that are rather complex. In [ 6 ] , a simpler version of the spectral algorithm is established that maintains the bound in Theorem 2. And in this paper we extend that simplified algorithm to the multi-sample setting. We show that when we draw m independent samples from the same distribution, we can dramatically improve the recovery rate. Theorem 1.3 (Main Result) There exist constants C_{1},C_{2}>0 such that the following holds. For any constants a>b>C_{1} and \gamma>0 satisfying \frac{(a-b)^{2}}{a+b}\geq\frac{C_{2}}{m}\log\frac{2}{\gamma} (3) given m independently-sampled graphs, one can find a \gamma -correct partition with probability 1-o(1) . Theorem 1.3 allows us to dramatically improve the recovery rate by drawing additional samples from the same distribution, because Equation 3 implies