SBM With Multiple Samples: Improved Spectral Recovery
For researchers in community detection and graph representation learning, this provides a rigorous theoretical foundation for multi-sample spectral methods and graph data augmentation, demonstrating exponential improvement in recovery guarantees.
The paper studies community detection in the two-block stochastic block model with multiple independent graph samples, showing that averaging m samples before spectral partitioning reduces the error bound exponentially in m, achieving a γ-correct partition when (a-b)^2/(a+b) ≥ (C/m) log(2/γ). Experiments on graphs up to n=1000 and m up to 9 confirm sharp bounds and dramatic improvements with even 2-3 samples.
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 $γ$ exponentially in $m$: specifically, one can find a $γ$-correct partition with probability $1 - o(1)$ whenever $\frac{(a-b)^2}{a+b} \geq \frac{C}{m} \log \frac{2}γ$, 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.