On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models

Aditya Bhaskara, Agastya Vibhuti Jha, Michael Kapralov +3

In a graph bisection problem, we are given a graph $G$ with two equally-sized unlabeled communities, and the goal is to recover the vertices in these communities. A popular heurist…