Graph coarsening improves max cut solutions under compute limits
Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT
Machine LearningArtificial IntelligenceComputation and Language
Summary
The problem MAX-CUT is very hard to solve because it has many tricky spots that can trap algorithms before they find the best solution. The authors studied a mathematical approach called Particle Polynomial Relaxation (PPR) that helps navigate this tough landscape better. They use a fast graph simplification method called Combinatorial Multigrid (CMG) to start PPR off from a smart position, which improves results efficiently. Their combined method performs very well on benchmark problems and scales to large graphs while saving a lot of memory.
What this means in practice
- •For network engineers: Optimize network designs and partitions by efficiently solving large MAX-CUT-like problems with limited computing resources.
- •For machine learning practitioners: Improve kernel clustering and graph-based data analysis through scalable MAX-CUT approximations using graph coarsening and moment relaxations.
Authors
M. Harper Langston, Pierre-David Letourneau, Dalton Jones, Harris Teague, Peter Scott, Mingu Lee, Richard Lethin, Chris Lott, Roland Memisevic, Fatih Porikli
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\times$ 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.