Robust recovery for stochastic block models
  We develop an efficient algorithm for weak recovery in a robust version of
the stochastic block model. The algorithm matches the statistical guarantees of
the best known algorithms for the vanilla version of the stochastic block
model. In this sense, our results show that there is no price of robustness in
the stochastic block model. Our work is heavily inspired by recent work of
Banks, Mohanty, and Raghavendra (SODA 2021) that provided an efficient
algorithm for the corresponding distinguishing problem. Our algorithm and its
analysis significantly depart from previous ones for robust recovery. A key
challenge is the peculiar optimization landscape underlying our algorithm: The
planted partition may be far from optimal in the sense that completely
unrelated solutions could achieve the same objective value. This phenomenon is
related to the push-out effect at the BBP phase transition for PCA. To the best
of our knowledge, our algorithm is the first to achieve robust recovery in the
presence of such a push-out effect in a non-asymptotic setting. Our algorithm
is an instantiation of a framework based on convex optimization (related to but
distinct from sum-of-squares), which may be useful for other robust matrix
estimation problems. A by-product of our analysis is a general technique that
boosts the probability of success (over the randomness of the input) of an
arbitrary robust weak-recovery algorithm from constant (or slowly vanishing)
probability to exponentially high probability.
