Graph Coarsening Enables Escaping Local Optima in Nonconvex MAX-CUT

MAX-CUT is highly sensitive to initialization because its binary optimization landscape contains exponentially many local optima. We study Particle Polynomial Relaxation (PPR), a moment-based nonconvex continuous reformulation possessing an advantageous optimization landscape. We warm-start PPR with Combinatorial Multigrid (CMG), a spectral graph-coarsening method that produces structure-aware initial solutions in near-linear time without training data. On $t2g20$ ($n=400$), the largest benchmark instance with a published exact optimum used in this study, the combined CMG+PPR pipeline reaches $97.5\%$ of optimum on average and $98.4\%$ on the best run. An extended variant with discrete local-search refinement reaches the published optimum on all sixty Biq Mac instances evaluated by a recent neural branch-and-bound method. Using a sparse CSR representation, the same approach scales to G-set instances with up to $20{,}000$ vertices, reducing memory requirements by up to $3333\times$ while maintaining a consistent improvement over the CMG warm start. These gains are largest on sparse weighted graphs; on dense graphs we complement the pipeline with optional spectral sparsification.