Source-linked AI summary
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, Roland Memisevic, Fatih Porikli
TL;DR
MAX-CUT’s binary landscape can contain exponentially many local optima, so local search is sensitive to initialization. The paper combines CMG graph coarsening with Particle Polynomial Relaxation (PPR), a moment-based continuous reformulation. The pipeline reaches near-optimal results across reported instance sizes, including 97.5% mean and 98.4% best-seed of the exact optimum on t2g20.
Problem
MAX-CUT’s binary flip neighborhood may contain exponentially many local optima, making a local method’s terminal cut sensitive to its initial point.
Source: §1 · p. 1Method
The method warm-starts a moment-based continuous PPR refinement with CMG graph coarsening, using sparsification when needed and a closing 2-opt sweep.
Source: §1 · p. 2, §2.3 · p. 4Results
Takeaways & Limitations
The combined approach provides a robust advantage in compute-constrained regimes, while its gains naturally diminish on graph families with little exploitable structure.
Source: §5 · p. 7With sufficient restarts, solution quality is often determined more by the discrete polishing stage than by the warm start, and extending the approach beyond n = 20,000 under fixed compute remains open.
Source: §4 · p. 7
Abstract
from arXiv · showhide
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.
1. Introduction
MAX-CUT’s flip landscape can contain exponentially many local optima, making local search sensitive to initialization. This paper combines a structure-aware graph-coarsening warm start with continuous refinement, addressing structured instances that worst-case approximation guarantees do not characterize.
1. Introduction
- Exponentially many local optima in the binary flip neighborhood can make a local method’s terminal cut depend more on initialization than on subsequent search.The classical Goemans-Williamson 0.878 worst-case ratio does not describe performance on structured instances where initialization captures useful graph information.Source: §1 · pp. 1–2
- Figure 1 contrasts random restarts that can end in different local optima with CMG’s structure-aware warm start followed by PPR’s multi-node moves.The caption contrasts PPR’s multi-node moves with one-bit local search.Source: §1 · p. 1, Figure 1 · p. 2
- CMG coarsening supplies a graph-driven warm start for PPR, combining graph structure with a continuous reformulation that has zero escape barrier at every suboptimal point when its mixing weight is free.The paper reports effectiveness on sparse, weighted, structured instances and scaling to n = 20,000 with sparse coupling storage; it also identifies little or no improvement on dense or nearly homogeneous graphs.Source: §1 · p. 2
- Unlike learned MAX-CUT solvers that use training, input-graph spectral coarsening requires no labels, training distribution, or neural inference hardware.The full heuristic pipeline reaches the same published optima on all 60 instances across six Biq Mac families evaluated by Chen et al. (2026).Source: §1 · p. 2
2. Method: moment relaxation with a graph-coarsening warm start
The method combines a moment-based continuous reformulation of MAX-CUT with CMG graph coarsening for initialization. PPR refines the warm start through one or more passes and a final 2-opt sweep, with optional sparsification and discrete polishing.
2.1. Continuous Reformulation through Discrete/Particle Product Measures
- The continuous reformulation is equivalent to MAX-CUT and, despite being nonconvex, every suboptimal point has zero escape barrier when the mixing weight is free to move.It represents coordinate marginals with particle atoms and optimizes mixtures across levels; the implementation uses softmax weights and tanh-parameterized locations.Source: §2.1 · p. 3
- For fixed L and R, the reformulation uses O(LnR) variables, and the implementation solves over w with L-BFGS across a penalty-continuation schedule while holding β at the uniform average.The passage contrasts the variable count with O(n^2) for the Goemans-Williamson SDP.Source: §2.1 · pp. 3–4
2.2. Graph-coarsening initialization
- CMG builds a coarsen–solve–uncoarsen hierarchy by grouping vertices with their strongest neighbor when the weight-to-degree ratio reaches 1/8, then projects the coarsest solution back with local-flip refinement.Its total cost is O(|E| log n); when edge weights are nearly uniform, the hierarchy compresses poorly and the warm-start advantage diminishes.Source: §2.2 · p. 4
2.3. The composed pipeline
- PPR starts from CMG’s binary solution, which has already been refined by single-bit flips, and can make simultaneous multi-node changes; the stronger configuration warm-starts each pass from the prior pass’s best binary solution.A single 2-opt sweep follows the final PPR pass because applying it after every pass tends to lock the solution into a two-bit local basin too early.Source: §2.3 · p. 4
- When needed, spectral sparsification feeds the CMG warm start, followed by PPR on the finest graph and one closing 2-opt sweep; an optional discrete tail can then be appended.The optional tail includes Kernighan–Lin, 3-opt, restarts, and a memetic genetic algorithm.Source: §2.3 · p. 4
3. Experiments
Experiments evaluate the pipeline on structured toroidal Ising instances with exact optima and real G-set instances, reporting results from small cases through n = 20,000. The full pipeline matches published optima across sixty Biq Mac instances, while sparse storage supports large-graph runs.
3. Experiments
- On the n = 15 instance, CMG finds the optimum in 30 µs, while 21 random PPR restarts use five orders of magnitude more time and top out one cut short.None of the 21 restarts finds the exact optimum.Source: §3 · p. 5
- On structured toroidal families, R ≥ 2 lifts every tested instance 4–15 points past CMG alone; on g05 60, no configuration improves CMG’s 0.96.Table 1 reports mean cut/OPT ratios over three seeds; its g05 60 subset contains five instances.Source: §3 · p. 5, Table 1 · p. 5
- On t2g20, five PPR passes and one closing 2-opt sweep raise CMG’s 0.832 to 0.975 mean and 0.984 best-seed cut/optimum ratios.Applying 2-opt after every pass instead finishes at 0.957.Source: §3 · p. 5
- The full pipeline matches the published optimum on all 60 Biq Mac instances, with per-instance times of 8.5–130.5s.Table 2 shows 10 selected instances; its caption states that the full pipeline matches all 60.Source: §3 · p. 5, Table 2 · p. 6
- Across eight instances, identical discrete tails reduce the up-to-7.4% pre-tail spread among L-BFGS, Adam, GD, and stochastic optimization to ≤0.7% per instance.L-BFGS reaches the pre-tail solution most cheaply.Source: §3 · p. 6
- For six G-set instances with n = 5K–20K, CSR storage reduces memory by 833–3333×, while the continuous-relaxation path gains 1.19–1.21× over CMG.Adding a discrete tail raises the final gain to 1.32–1.33×.Source: §3 · p. 6
4. Discussion: comparison and limitations
The discussion frames the method as a reusable combination of nonconvex relaxation and spectral coarsening, while identifying limits in reference assumptions, graph structure, and high-budget polishing.
4. Discussion: comparison and limitations
- Optimality ratios rely on the same type of external exact-solver reference used by Cosm, and the paper does not claim runtime parity.Cosm reports optimality on G77 and G81 using an external exact solver rather than an internal proof.Source: §4 · p. 6
- On G1, L-BFGS outperforms Adam by up to 6.2%, while gradient descent stalls at the CMG warm start and runs 11–30× slower per instance.Source: §4 · p. 6
- The framework combines reusable nonconvex-relaxation and spectral-coarsening components rather than a solver tailored only to MAX-CUT.The G-set table covers four of six instances and distinguishes the CMG→PPR→2-opt configuration from a version with a discrete tail.Source: §4 · p. 7, Table 3 · p. 7
- Dense, well-conditioned graphs and uniform-weight Erdős–Rényi graphs offer little benefit because they provide little exploitable structure for coarsening.For uniform-weight Erdős–Rényi graphs, the CMG grouping criterion rarely holds once n > 16.Source: §4 · p. 7
- With a large discrete-polishing budget, a random-start baseline matches or exceeds the CMG-seeded pipeline on roughly half the hardest cases, and polishing often determines final quality.Extending the approach beyond n = 20,000 under fixed compute remains an open direction.Source: §4 · p. 7
5. Conclusion
The conclusion reports near-optimal results across varied graph sizes, with gains limited on graphs lacking exploitable structure. The appendix describes PPR’s penalty-based solver and its restart-and-refinement procedure.
5. Conclusion
- 97.5% mean and 98.4% best-seed of the exact optimum on t2g20 (n = 400), with 98.7–99.0% on the two largest G-set instances with externally verified optima.The conclusion reports gains through 20,000 vertices without observable degradation, but says they diminish on graph families with little exploitable structure.Source: §5 · p. 7
- A structure-aware CMG warm start with particle-based continuous relaxation reaches 97.5% mean (98.4% best-seed) of exact optimum on t2g20 (n = 400), and 98.7–99.0% on two largest G-set instances with externally verified optima.Source: §5 · p. 7
Appendix A. Particle Polynomial Relaxation (PPR) for MAX-CUT: full algorithm
- The MAX-CUT solver uses a binary/box penalty that drives each marginal’s second moment to one, with K restarts following a fixed penalty-continuation schedule.The penalty is zero exactly when every marginal is supported on {−1, +1}; the algorithm has no equality-constraint dual loop.Source: Appendix A · p. 11
- Each restart initializes one particle slot from the warm start and the others randomly, runs L-BFGS, converts particles to binary cuts, and applies local-flip refinement.Source: Appendix A · p. 11
A.1. Theory and Proofs
The appendix establishes a zero escape barrier for every suboptimal point when the PPR mixing weights can move, then distinguishes that result from the fixed-weight solver actually used. It also explains why structured CMG initialization and the ordered CMG–PPR pipeline matter in compute-constrained settings.
A.1. Theory and Proofs
- For free mixing weights, every suboptimal feasible point has a path to the optimum whose maximum rise is at most δC, so its escape barrier is zero.At an optimal point, the barrier is infinite; the result does not imply that every local minimum is globally optimal.Source: §A.1 · p. 13
- With the solver’s fixed uniform weights, the proven guarantee is only a C/L escape-barrier bound, not the zero barrier for freely moving weights.The paper’s solver holds β_l = 1/L fixed and does not implement the weight movement required for the stronger result.Source: §A.1 · pp. 14–15
B.1. Existing approaches
- MAX-CUT exact methods can scale exponentially in the worst case, while semidefinite moment matrices grow quickly; the paper instead supplies structure through graph coarsening rather than learning.The appendix contrasts this with learned approaches and established SDP-based methods.Source: §B.1 · p. 15
B.2. Why structured initialization is necessary
- Random initialization can miss a useful basin: on a hard n = 15 instance, 21 random PPR restarts all missed the optimum, while CMG found it directly.The paper uses this result to motivate treating initialization as central to the solver.Source: §B.2 · p. 15
B.3. Three complementary tools
- The pipeline combines sparsification when needed, CMG’s graph-derived warm start, and PPR’s continuous search; the composed order performs strongest, while removing stages generally reduces quality on hard instances.Sparsification is typically unnecessary on graphs that are already sparse.Source: §B.3 · p. 16
B.4. The pipeline end to end
- The end-to-end pipeline coarsens to a directly solvable graph, projects the solution back with local-flip refinement, then runs multi-pass PPR and one closing 2-opt sweep.The small-coarse-level SQP solve can substitute at a level with nℓ ≤ 20.Source: §B.4 · p. 16
B.5. Further Contributions and Additional Results
The section summarizes the paper’s contributions: combining CMG and PPR, testing refinement variants, and evaluating quality and scaling. The accompanying pipeline figure shows the sequence of stages used in the approach.
B.5. Further Contributions and Additional Results
- The reported t2g20 result is 0.975 mean and 0.984 best cut/OPT, and the sparse CSR implementation scales to n = 20,000 without observed decay in gain over CMG.The contribution summary also identifies a dense homogeneous regime where the method adds little.Source: §B.5 · p. 16
- The contribution summary identifies CMG and PPR as complementary in the compute-constrained regime and reports that PPR can improve beyond CMG’s one-flip local optimum on structured instances.It notes that the advantage narrows when a large discrete-tail budget is affordable.Source: §B.5 · p. 16
- Figure 2 depicts sparsification feeding CMG coarsening, projection with local-flip refinement, finest-graph PPR, multi-pass restarts, and a closing 2-opt sweep.Sparsification is a no-op when the graph is already sparse.Source: Figure 2 · p. 17
B.5.1. The binary-constraint derivation
The appendix outlines the binary-constraint formulation, solver scaling, sparsification rationale, CMG coarsening, and refinement branches. It explains how graph structure informs sparsification and coarsening, and how the coarse solution is refined before PPR.
B.5.1. The binary-constraint derivation
- The binary-constraint derivation recasts the problem as minimizing the negative objective over the binary-constraint variety.The supplied passage gives only this equivalence, not the derivation steps.Source: §B.5.1 · p. 18
B.5.2. Problem dimensions and scaling
- For fixed L and R, PPR uses O(LnR) parameters, linear in n, whereas the Goemans–Williamson SDP uses O(n^2) variables.The supplied table caption identifies a variable-count comparison across PPR-MAX-CUT and standard relaxations.Source: §B.5.2 · p. 18, Table 5 · p. 18
B.5.3. Sparsification and leverage scores
- Dense uniform graphs have nearly flat leverage scores and gain little from sparsification, while weighted structured graphs can have skewed scores that allow smaller cut-preserving approximations.The cited discussion describes sampling edges according to effective-resistance leverage scores.Source: §B.5.3 · p. 18, Figure 3 · p. 19
B.5.4. CMG coarsening
- CMG profiles and contracts graph structure, then solves the coarsest graph and projects its solution back with local-flip refinement to form a warm start.Unlike balanced multilevel partitioners, CMG does not force balanced partitions.Source: §B.5.4 · p. 18, Figure 4 · p. 19
B.5.5. Refinement branches and multi-pass polishing
- At levels with nℓ ≤ 20, the method can use an SLSQP coarse solve; headline results instead use finest-graph PPR, chained passes, and one final 2-opt sweep.The table caption says “Exact” marks a cut matching the known or brute-force optimum.Source: §B.5.5 · p. 20, Table 6 · p. 20
B.5.6. Additional refinement and scaling results
The additional results track refinement on t2g20, compare multi-pass behavior, and show sparse scaling on G-set instances. The figures report improving solution ratios across refinement stages and sustained gains over CMG as graph size grows.
B.5.6. Additional refinement and scaling results
- Table 7 compares t2g20 configurations by mean cut/OPT over three seeds; its competing 2-opt-after-every-pass configuration finishes 1.8 points behind the cumulative ladder.The figure’s cumulative ladder excludes that branch because it starts after pass 1.Source: Table 7 · p. 20, Figure 5 · p. 21
- On t2g20, five PPR passes raise the CMG warm start from 0.832 to 0.952, a closing 2-opt sweep reaches 0.975, and the discrete tail reaches 0.994.Each plotted stage is cumulative; the 2-opt-after-every-pass configuration branches off pass 1 rather than extending the ladder.Source: Figure 5 · p. 21
- Pass 2 yields the largest single gain (+0.014), and the curve is essentially flat from pass 5 onward.The passage contrasts the multi-pass schedule with quadrupling restarts, which buys only +0.004 in total.Source: Figure 6 · p. 21
- Across six G-set instances from n = 5,000 to 20,000, memory savings exceed 3,300× at n = 20,000, while gains over CMG remain 1.194–1.212× for CMG→PPR→2-opt and 1.316–1.331× with the discrete tail.Neither gain band decays at the largest instance; both panels share an n axis and the gain panel is anchored at 1.0.Source: Figure 7 · p. 22
B.5.7. Pass and restart saturation
On t2g20, additional PPR passes improve the CMG warm start more than simply increasing random restarts. A single 2-opt sweep after the final pass gives the strongest reported result; applying it after every pass performs worse.
B.5.7. Pass and restart saturation
- Pass 2 delivers the largest single gain (+0.014), while five passes capture essentially all achievable gain (0.952) on t2g20.The pass-count sweep uses a fixed restart budget.Source: §B.5.7 · p. 23, Table 8 · p. 23
- Increasing single-pass restarts from k=40 to 80 to 160 gains +0.003 then +0.001, while one additional pass is worth roughly five times a doubling of k.The restart sweep holds pass count at one.Source: §B.5.7 · p. 23, Table 9 · p. 23
B.5.8. The full t2g20 stage ladder and 2-opt ordering
- 0.975 mean and 0.984 best of the exact optimum follow five PPR passes and one final 2-opt sweep on t2g20.Interleaving 2-opt after every pass finishes at 0.957.Source: §B.5.8 · p. 23, Table 10 · p. 24
- A single final 2-opt sweep raises the five-pass mean from 0.952 to 0.975 with only 12–19 accepted flips.A single-pass run with 2-opt reaches 0.962, exceeding five passes without 2-opt (0.952).Source: §B.5.8 · p. 23, Table 10 · p. 24
B.5.9. Tail ablation on the heavy set, and where the G81 budget goes
The discrete-tail ablation shows that added search time is not uniformly productive, and a random-seeded GA can match or beat the CMG+PPR pipeline on some instances. The appendix also contrasts cut quality with proof times, gives a mechanical walkthrough, and describes a controlled optimizer swap.
B.5.9. Tail ablation on the heavy set, and where the G81 budget goes
- On three of eight heavy-set instances the random-seeded GA beats the full pipeline, and on a fourth it ties.The control uses the same GA budget without CMG or PPR; Table 13 reports absolute cuts.Source: §B.5.9 · p. 25, Table 13 · p. 26, Figure 8 · p. 26
- The first five G81 stages take 75.7 s (1.53% of the original budget) and deliver most of the gain; 200 restarts take 2782 s for 30 cut units.Removing that stage and retuning reduces runtime from 4951 s to 261 s while improving the cut.Source: §B.5.9 · p. 25, Table 14 · p. 27
B.5.10. Biq Mac families: cut quality against wall time
- Every Biq Mac family reaches 1.000 cut/published optimum, but the comparison is heuristic cut quality versus branch-and-bound proof of optimality, not a like-for-like solver ranking.Figure 9 covers six families of ten instances each.Source: Figure 9 · p. 28, §B.5.10 · p. 28
B.5.11. Pipeline Walkthrough Example
- The Karate Club walkthrough illustrates sparsification, CMG grouping, warm-start projection, and PPR on the finest graph, rather than benchmarking performance.CMG already reaches the best cut found by later stages in this example; its SDP estimate is not a certified upper bound.Source: §B.5.11 · p. 28
B.5.12. The continuous-phase optimizer swap in full
- The optimizer swap holds the CMG warm start, restart budget, continuation schedule, and downstream tail fixed while comparing L-BFGS, Adam, GD, and a level-stochastic variant.The supplied passage describes the controlled setup, not the swap’s results.Source: §B.5.12 · p. 28
B.5.13. Internal optimality certificate for G81
The appendix reports a G81 cut of 13962, or 99.3% of the externally reported 14060, and checks it through exact repairs of connected residual cores. It also documents pipeline component implementations and cautions that the internal checks do not prove global optimality.
B.5.13. Internal optimality certificate for G81
- 13962 on G81 is 99.3% of the externally reported value 14060; exact repair found no improving solution in 40 connected residual cores of at most 200 vertices.This certifies the reported cut on those cores, not that 14060 is the global optimum.Source: §B.5.13 · pp. 28, 30
Appendix C. Pseudocode for every pipeline component
- The appendix pseudocode is transcribed from the reference implementation that produced the reported numerical results.It omits repeated boxes for the continuous solver and CMG coarsening, provided elsewhere.Source: Appendix C · p. 31
C.1. Stage 1: Spielman-Srivastava sparsification
- Sparsification uses exact effective resistances for n ≤ 500 and a degree-proxy approximation above that size, and runs only when |E| > 3n.It is a no-op on the already-sparse toroidal instances dominating the benchmarks.Source: §C.1 · p. 31
C.2. Stage 3: coarse sweet-spot SQP solve
- The coarse-level solve uses dense SLSQP only at hierarchy levels with nℓ≤20, enforcing binary marginals through an explicit moment equality.Larger levels use the penalty schedule instead.Source: §C.2 · p. 31, §C.3 · p. 32
C.3. Stage 4: one particle pass, multi-pass, and 2-opt
- The multi-pass driver chains warm-started particle passes, while the 2-opt sweep is used as a closing polish; applying it once at the end adds +0.023 in mean ratio.Applying 2-opt after every pass is worse.Source: §C.3 · pp. 31–32, §C.4 · p. 33
C.4. Stage 5 (optional discrete tail): Kernighan-Lin and 3-opt
- The optional tail combines joint 2-opt/Kernighan-Lin/3-opt local optimization, a memetic GA, and a Mixing Method relax-and-reround estimate that is not a certified bound.The rank threshold is not verified by the Mixing Method’s convergence check.Source: §C.4 · pp. 34–36