Nonconvex landscapes for ${\mathbf{Z}}_2$ synchronization and graph clustering are benign near exact recovery thresholds

We study the optimization landscape of a smooth nonconvex program arising from synchronization over the two-element group ${\mathbf{Z}}_2$, that is, recovering $z_1,\dots ,z_n\in \{\pm 1\}$ from (noisy) relative measurements $R_{ij}\approx z_i{z}_j$. Starting from a max-cut–like combinatorial problem, for integer parameter $r\ge 2$, the nonconvex problem we study can be viewed both as a rank-$r$ Burer–Monteiro factorization of the standard max-cut semidefinite relaxation and as a relaxation of $\{\pm 1\}$ to the unit sphere in ${\mathbf{R}}^r$. First, we present deterministic, non-asymptotic conditions on the measurement graph and noise under which every second-order critical point of the nonconvex problem yields exact recovery of the ground truth. Then, via probabilistic analysis, we obtain asymptotic guarantees for three benchmark problems: (1) synchronization with a complete graph and Gaussian noise, (2) synchronization with an Erdős–Rényi random graph and Bernoulli noise, and (3) graph clustering under the binary symmetric stochastic block model. In each case, we have, asymptotically as the problem size goes to infinity, a benign nonconvex landscape near a previously-established optimal threshold for exact recovery; we can approach this threshold to arbitrary precision with large enough (but finite) rank parameter $r$. In addition, our results are robust to monotone adversaries.