SBM With Multiple Samples: Improved Spectral Recovery

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$ independent samples before applying spectral partitioning reduces the error bound ${\hat{I}}^3$ exponentially in $m$: specifically, one can find a ${\hat{I}}^3$-correct partition with probability $1-o(1)$ whenever $\frac{(a-b{)}^2}{a+b}\ge \frac{C}{m}\log {\frac{2}{\hat{I}}}^3$, improving the single-sample requirement by a factor of $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$ up to $1000$) and sample counts ($m$ up to $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.

12 pages, 6 figures, accepted at ICANN 2026