  We investigate a class of general combinatorial graph problems, including
MAX-CUT and community detection, reformulated as quadratic objectives over
nonconvex constraints and solved via the alternating direction method of
multipliers (ADMM). We propose two reformulations: one using vector variables
and a binary constraint, and the other further reformulating the Burer-Monteiro
form for simpler subproblems. Despite the nonconvex constraint, we prove the
ADMM iterates converge to a stationary point in both formulations, under mild
assumptions. Additionally, recent work suggests that in this latter form, when
the matrix factors are wide enough, local optimum with high probability is also
the global optimum. To demonstrate the scalability of our algorithm, we include
results for MAX-CUT, community detection, and image segmentation benchmark and
simulated examples.
