Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT
Abstract
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 \texttt{t2g20} (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.
Related
- Compute-Constrained Safety Filters with Neuromorphic Event Triggering
- A constraint dissolving method for generally constrained optimization over a nonconvex set
- Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
- Constrained Nonconvex Stochastic Optimization with One Projection
- lapanda: A Matrix-Free Differentiable Solver for Nonconvex Constrained Optimization Layers
BibTeX
@misc{langston2026graph,
title = {{Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT}},
author = {M. Harper Langston and Pierre-David Letourneau and Dalton Jones and Harris Teague and Peter Scott and Mingu Lee and Richard Lethin and Chris Lott and Roland Memisevic and Fatih Porikli},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19043},
eprint = {2610.19043},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19043},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT
AU - M. Harper Langston
AU - Pierre-David Letourneau
AU - Dalton Jones
AU - Harris Teague
AU - Peter Scott
AU - Mingu Lee
AU - Richard Lethin
AU - Chris Lott
AU - Roland Memisevic
AU - Fatih Porikli
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.19043
UR - https://arxiv.org/abs/2610.19043
AB - 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 \texttt{t2g20} (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.
ER -