Exact Community Recovery under Side Information: Optimality of Spectral Algorithms

We study the problem of exact community recovery in general, two-community block models, in the presence of node-attributed side information. We allow for a very general side information channel for node attributes, and for pairwise (edge) observations, consider both Bernoulli and Gaussian matrix models, capturing the Stochastic Block Model, Submatrix Localization, and mathbbZ2-Synchronization as special cases. A recent work of Dreveton et al. 2024 characterized the information-theoretic limit of a very general exact recovery problem with side information. In this paper, we show algorithmic achievability in the above important cases by designing a simple but optimal spectral algorithm that incorporates side information (when present) along with the eigenvectors of the pairwise observation matrix. Using the powerful tool of entrywise eigenvector analysis of Abbe et al. 2020, we show that our spectral algorithm can mimic the so called genie-aided estimators, where the ith genie-aided estimator optimally computes the estimate of the ith label, when all remaining labels are revealed by a genie. This perspective provides a unified understanding of the optimality of spectral algorithms for various exact recovery problems in a recent line of work.