SBM With Multiple Samples: Improved Spectral Recovery (opens in new tab)

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 $\gamma$ exponentially in $m$: specific...