# Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT

arXiv: https://arxiv.org/abs/2610.19043 · HTML: https://mlsanity.com/paper/2610.19043/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 13 Oct 2026.

## Builds on (most cited first, 9 of 9)

- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints](https://mlsanity.com/paper/1706.00476/) (2017)
- [Learning-Augmented Streaming Algorithms for Approximating MAX-CUT](https://mlsanity.com/paper/2412.09773/) (2024)
- [An Efficient Framework for Global Non-Convex Polynomial Optimization over the Hypercube](https://mlsanity.com/paper/2308.16731/) (2023)
- [Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks](https://mlsanity.com/paper/2605.07113/) (2026)

## Abstract (arXiv)

Because its binary optimization landscape contains exponentially many local optima, MAX-CUT is highly sensitive to initialization. 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 textttt2g20 (n=400), benchmark instance with known exact optimum, 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× while maintaining a consistent improvement over the CMG warm start. Gains are largest on sparse weighted graphs; on dense graphs we complement the pipeline with spectral sparsification.