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

M. Harper Langston; Pierre-David Letourneau; Dalton Jones; Harris Teague; Peter Scott; Mingu Lee; Richard Lethin; Chris Lott

cs.LGOct 13, 2026

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

Authors: M. Harper Langston, Pierre-David Letourneau, Dalton Jones, Harris Teague, Peter Scott, Mingu Lee, Richard Lethin, Chris Lott,

Organizations: Qualcomm AI Research

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 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.

Figures & tables

Figure 1: Schematic comparison of random and structure-aware initialization. Left: random restarts are likely to terminate in different local optima of the flip landscape. Center: CMG coarsening summarizes the graph into larger structural units and returns a warm start. Right: PPR is then initialized in that basin and can make multi-node moves that are inaccessible to one-bit local search.

Family	$n$	CMG	P-16, $R=1$	P-32,8	Notes
t3g5	125	0.828	0.883	0.978	3-D toroidal
t2g20	400	0.830	0.832	0.907	2-D toroidal
Reference:				0.878	GW guarantee
g05_60	60	0.963	0.963	0.963	Expander (5/10); CMG already strong

Table 1: S-S

\to

CMG

\to

PPR, mean cut/OPT ratio over three seeds vs. known optima ( Rendl et al., 2010 ) ; g05_60 here is a 5-instance subset of the family, vs. the full 10-instance mean in Table 2 . P-32,8 denotes

L=32,R=8

Family	$n$	CMG	Pipeline	time (s)	Vanilla (s)	Neural (s)
		Ours (heuristic)			( Chen et al., 2026 ) B&B (s)
g05_60	60	0.975	1.000	23.9	53	9.5
g05_80	80	0.977	1.000	63.8	1170	156
g05_100	100	0.982	1.000	130.5	40930	4509
pm1s_80	80	0.817	1.000	8.5	610	81
pm1s_100	100	0.818	1.000	13.7	10382	1058

Table 2:

10

instances chosen from the

6

Biq Mac families ( Chen et al., 2026 ) ; full pipeline matches all

60

published optimum. Mean single-core per-instance wall clock used for timing comparisons; B&B times from ( Chen et al., 2026 ) , Tab.

3

Instance	$n$	mem	cmg	2opt	$\Delta_{\mathrm{2opt}}$	final	$\Delta_{\mathrm{final}}$	ratio-to-OPT (2opt/final)
G57	5000	833.3 $\times$	2600	3142	1.208	3460	1.331	–
G67	10000	1666.7 $\times$	5198	6258	1.204	6872	1.322	–
G77	14000	2333.3 $\times$	7454	9022	1.211	9810	1.316	0.908 / 0.9869
G81	20000	3333.3 $\times$	10574	12626	1.194	13922	1.317	0.898 / 0.9902

Table 3: Sparse CSR path, four of six G-set instances, single core. “mem”: dense/CSR storage ratio. “2opt”: cut after CMG

\to

PPR

\to

2-opt only, with its own gain over CMG,

\Delta_{\mathrm{2opt}}

(this is the configuration the pipeline name describes). “final”: cut after also appending the retuned discrete tail of Table 14 (KL/3-opt/GA/ILS), with

\Delta_{\mathrm{final}}

. ratio-to-OPT given at both stages, only where an externally verified optimum exists.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Strategy	Cut	Ratio	Time
Random-init PPR, best of 21	37	0.974	$21\times\!\sim\!7$ s
Random-init PPR, exact hits	0/21	–	–
CMG $+$ flip	38	1.000	$30\,\mu$ s
CMG $\to$ PPR warm start	38	1.000	$\sim$ 12s

Appendix

Table 4: Hard instance

n=15

, seed

=44

, known optimum

38

. “CMG” means CMG followed by local-flip refinement.

Figure 2: The composed pipeline: S-S sparsification (no-op if already sparse) feeds CMG coarsening to a directly-solvable coarsest level; the coarsest solution is projected back up with local-flip refinement; PPR then runs, warm-started from that projection, on the finest graph, followed by multi-pass restarts and a single closing 2-opt sweep.

Component	Count	Notes
Particle locations and weights	$O(LnR)$	linear in $n$ for fixed $L,R$
GW SDP variables	$O(n^{2})$	quadratic in $n$
Lasserre level $k$ SDP	$O\!\left(\binom{n+2k}{n}^{2}\right)$	grows rapidly with $n$

Appendix

Table 5: Variable-count scaling for PPR-MAX-CUT and standard relaxations.

Figure 3: Leverage-score distributions. Uniform-weight graphs have nearly flat leverage scores, while weighted structured graphs can have skewed scores that make sparsification useful.

Figure 4: CMG coarsening effectiveness versus graph density. Sparse structured graphs contract aggressively, while dense uniform graphs contract weakly.

Graph	Seed	OPT	CMG+Flip	Exact	ADMM	Exact	SQP	Exact
random-15	42	39	37	N	36	N	39	Y
random-15	44	38	38	Y	37	N	38	Y
random-20	43	62	62	Y	61	N	62	Y
random-20	44	70	65	N	65	N	69	N
planted-30-200	42-44	(exact)	exact	Y	exact	Y	exact	Y
Typical wall time			$<\!1$ ms		5-39 s		2-19 s

Appendix

Table 6: Coarse sweet-spot (

n_{\ell}\leq 20

) solver comparison, three seeds per size. “Exact” marks a cut matching the known or brute-force optimum.

Configuration	Mean	Best seed
CMG baseline	0.832	–
5-pass PPR	0.952	0.968
2-opt after every pass	0.957	0.970
5-pass $+$ single closing 2-opt	0.975	0.984
GW guarantee	0.878	–

Appendix

Table 7: t2g20 (

n=400

) configuration ladder, mean cut/OPT over three seeds. The first, second, and fourth rows are the cumulative ladder plotted in Figure 5 ; the third is the competing 2-opt after every pass configuration, which branches off pass 1 rather than extending the ladder and finishes

1.8

points behind.

Figure 5: Progressive improvement on t2g20 (

n=400

) across the cumulative stage ladder, mean over three seeds. The CMG warm start opens at

0.832

; five PPR passes carry it to

0.952

; a single closing 2-opt sweep gives the

0.975

headline of Table 7 ; and the discrete tail (KL, 3-opt,

200

-restart, memetic GA) closes to

0.994

. Every stage shown here is applied on top of the previous one. The competing 2-opt after every pass configuration is deliberately absent: it branches off pass 1 rather than extending the ladder, and is reported in Table 7 above and per-instance in Table 10 .

Figure 6: Ratio to known optimum versus pass number on t2g20 (

n=400

L{=}128

R{=}32

k{=}40

. Pass 2 yields the largest single gain (

+0.014

); the curve is essentially flat from pass 5 onward. Read against Table 9 , where quadrupling the restart count buys only

+0.004

in total: it is the multi-pass schedule, not raw restart breadth, that escapes the warm-start basin.

Panel of Figure 14 — (a) Sparse scaling on six G-set instances, $n=5000$ - $20{,}000$ (a superset of the four shown in Table 3 , which omits G65 and G66 ). Memory savings grow linearly with $n$ , exceeding $3300\times$ at $n=20{,}000$ . The right-hand panel shows the gain over the CMG warm start at both pipeline stages: the continuous-relaxation path alone (CMG $\to$ PPR $\to$ 2-opt, blue) holds a tight $1.194$ - $1.212\times$ band, and appending the discrete tail (KL/3-opt/GA/ILS, red) carries this to $1.316$ - $1.331\times$ ; neither band decays at the largest instance. Both panels are plotted against a common $n$ axis; the right-hand panel’s vertical axis is anchored at $1.0$ , the no-gain line, so that the flatness of the bands is not exaggerated by a magnified scale.

Max-Cut

See all 10 papers

Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
May 8, 2026Hao Chen, Chendi Qian, Christopher Morris +2Max-Cut Semidefinite Programming
1Davidson School of Chemical Engineering, Purdue University · Faculty of Computer Science, RWTH Aachen University · 3Jacobs Technion-Cornell Institute, Cornell Tech
Dual-GNN Multilevel Coarsening for Maximum Independent Set
Sep 21, 2026Tianfeng Chen, Xianyue LiGraph Coarsening Combinatorial Optimization
School of Mathematics and Statistics Lanzhou University
Accelerated Relax-and-Round for Concave Coverage Problems
May 7, 2026Matthew Fahrbach, Mehraneh Liaee, Morteza ZadimoghaddamSubmodular Optimization Approximation Algorithms
Google Research

May 8, 2026J/K move · Enter open · S save

Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks

Hao Chen, Chendi Qian, Christopher Morris, Andrea Lodi+1

1Davidson School of Chemical Engineering, Purdue University · Faculty of Computer Science, RWTH Aachen University · 3Jacobs Technion-Cornell Institute, Cornell Tech

Max-Cut Semidefinite Programming Graph Neural Networks Branch and Bound Combinatorial Optimization Global Optimization+2

Open paper AskPDF arXiv

Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm can be prohibitively expensive. Hence, we consider this challenge for Max-Cut, where branch and bound commonly uses semidefinite programming (SDP) relaxations to bound subproblems. We propose a Max-Cut-specific graph neural network that serves as a principled, lightweight neural proxy for these SDP solvers and can be plugged directly into an exact branch-and-bound framework. The proposed architecture has update steps of complexity

\mathcal{O}(n^2 + ne)

, and predicts both primal- and dual-feasible SDP solutions. The primal SDP solutions yield feasible Max-Cut solutions via the Goemans--Williamson algorithm. In addition, it is trained in a self-supervised fashion without requiring solved SDP relaxations as labels. Empirically, we show that our architecture can substantially reduce the cost of bounding in exact Max-Cut solving by up to

10.6 \times

compared with using the state-of-the-art SDP solver Mosek. Our work highlights the potential of learned, validity-preserving surrogates for accelerating exact optimization over structured convex relaxations.

Abstract

Max-Cut

Explore similar work

Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks

Dual-GNN Multilevel Coarsening for Maximum Independent Set

Accelerated Relax-and-Round for Concave Coverage Problems