{"id":"arxiv/2610.19043","url":"https://arxiv.org/abs/2610.19043","tags":["cs.LG","cs.AI","cs.CL","math.NA","math.OC"],"score":0,"title":"Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT","domain":"cs.LG","source":"arxiv","authors":["M. Harper Langston","Pierre-David Letourneau","Dalton Jones","Harris Teague","Peter Scott","Mingu Lee","Richard Lethin","Chris Lott","Roland Memisevic","Fatih Porikli"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-13","reactions":{}}