Paper deep dive
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
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 10/15/2026, 4:53:08 AM
Summary
This paper introduces a pipeline for solving the MAX-CUT problem by combining Combinatorial Multigrid (CMG) for structure-aware warm-starting with Particle Polynomial Relaxation (PPR), a nonconvex continuous reformulation. The method effectively escapes local optima, achieving near-optimal results on benchmark instances (97.5% average on t2g20) and scaling to 20,000 vertices with significant memory reduction via sparse CSR representation. It outperforms or matches learned neural solvers without requiring training data.
Entities (10)
Relation Signals (7)
Particle Polynomial Relaxation → solves → Max-Cut
confidence 95% · We study Particle Polynomial Relaxation (PPR)... reformulation... equivalent to the original MAX-CUT problem
Combinatorial Multigrid → warmstarts → Particle Polynomial Relaxation
confidence 95% · We warm-start PPR with Combinatorial Multigrid (CMG)
Pipeline (CMG+PPR) → achievesperformanceon → Biq Mac
confidence 90% · reaches the published optimum on all sixty Biq Mac instances
Pipeline (CMG+PPR) → achievesperformanceon → t2g20
confidence 90% · On t2g20... the combined CMG+PPR pipeline reaches 97.5% of optimum
Combinatorial Multigrid → uses → spectral graph-coarsening
confidence 90% · Combinatorial Multigrid (CMG), a spectral graph-coarsening method
Spielman-Srivastava → preprocesses → dense graphs
confidence 85% · on dense graphs we complement the pipeline with spectral sparsification... Spielman-Srivastava
Particle Polynomial Relaxation → usesoptimizer → L-BFGS
confidence 85% · We solve this problem over w with L-BFGS
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.19043v1
- Canonical: https://arxiv.org/abs/2610.19043v1
Trouble viewing inline? Open PDF directly →
Full Text
86,548 characters extracted from source content.
Expand or collapse full text
Qualcomm AI Research Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT M. Harper Langston Email: hlangsto@qti.qualcomm.com Pierre-David Letourneau Email: pletourn@qti.qualcomm.com Dalton Jones Email: daltjone@qti.qualcomm.com Harris Teague Email: hteague@qti.qualcomm.com Peter Scott Email: peter.scott@nyu.edu Mingu Lee Email: mingul@qti.qualcomm.com Richard A. Lethin Email: rlethin@qti.qualcomm.com Christopher Lott Email: clott@qti.qualcomm.com Roland Memisevic Email: rmemisev@qti.qualcomm.com Fatih Porikli Email: fporikli@qti.qualcomm.com Affiliation: 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=400n=400), a benchmark instance with known exact optimum, the combined CMG+PPR pipeline reaches 97.5%97.5\% of optimum on average and 98.4%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,00020,000 vertices, reducing memory requirements by up to 3333×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. 1 Introduction MAX-CUT asks for a partition of a graph’s vertices that maximizes the total weight of crossing edges (Karp, 1972; Garey and Johnson, 1979). With xi∈−1,+1x_i∈\-1,+1\, it can be written as the nonconvex quadratic program minx∈−1,+1n−14∑(i,j)∈Ewij(1−xixj), _x∈\-1,+1\^n- 14 _(i,j)∈ Ew_ij(1-x_ix_j), (1.1) equivalently as a ground-state search for the associated Ising energy (Barahona, 1982; Lucas, 2014). We first note that the flip neighborhood on −1,+1n\-1,+1\^n may contain exponentially many local optima; so, a local method’s terminal cut can be determined more by the initial point than by the amount of search performed afterward. Second, the classical Goemans-Williamson 0.8780.878 approximation ratio (Goemans and Williamson, 1995), tight under the Unique Games Conjecture in the worst case (Khot et al., 2007), does not describe how close a nonconvex solver can get on structured instances when initialization already captures useful graph information. 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. We investigate whether two complementary ideas can be combined effectively. First: a continuous moment-based reformulation which possesses a highly-advantageous optimization landscape, namely, every suboptimal point has zero escape barrier when its mixing weight is free to move (Appendix A.1 and (Letourneau et al., 2023)). Second: a graph coarsening warm start that places the finite-particle solver in a useful basin. We find that this combination is effective on sparse and weighted structured instances and that it scales to n=20,000n=20,000 when the coupling matrix is stored sparsely. The same experiments also identify a clear boundary: on dense or nearly homogeneous graphs, CMG often has little structure to exploit, and the pipeline provides little or no improvement over the warm start. Appendix B gives additional background, mechanical details, and a small end-to-end walkthrough. The main text focuses on the solver, initialization, and empirical behavior of the composed pipeline. Relation to learned combinatorial solvers. Recent learned MAX-CUT methods supply structural information through training. OptGNN (Yau et al., 2024) learns an overparameterized Burer-Monteiro (Burer and Monteiro, 2003) update, while Chen et al. (Chen et al., 2026) train a GNN to predict SDP certificates used inside branch-and-bound. Our approach uses a different source of structure: spectral graph coarsening on the input graph itself. This requires no labels, no training distribution, and no neural inference hardware. We do not claim uniform superiority, but on the six Biq Mac families evaluated by (Chen et al., 2026), our full heuristic pipeline reaches the same published optima on all 6060 instances without their training setup (Table 2). 2 Method: moment relaxation with a graph-coarsening warm start 2.1 Continuous Reformulation through Discrete/Particle Product Measures Our proposed PPR method is inspired by the work of Lasserre (Lasserre, 2001) and Letourneau et al. (Letourneau et al., 2023) which both address the problem of global polynomial optimization through a moment-based reformulation. In this case, consider a level-l discrete product measure to be defined as, μ(l)(⋅)=⨂i=1D(∑r=1Rwi(l,r)δx¯i(r)),wi(l,⋅)∈ΔR−1,μ^(l)(·)\;=\; _i=1^D ( _r=1^Rw_i^(l,r)\, _ x_i^(r) ), w_i^(l,·)∈ ^R-1, (2.1) where ΔR−1:=w∈ℝ≥0R:∑rwr=1 ^R-1:=\w _≥ 0^R: _rw_r=1\ is the probability simplex; R is thus the number of particles (point masses, or atoms) used to represent each coordinate’s marginal, and l=1,…,Ll=1,…,L indexes one of L independently optimized such mixtures (levels), combined below through a mixing weight β. Its degree-n marginal moment in coordinate i is an,i(l):=∫Tn(xi)dμ(l)(x)=∑r=1Rwi(l,r)Tn(x¯i(r)),a_n,i^(l)\;:=\; T_n(x_i)\,dμ^(l)(x)= _r=1^Rw_i^(l,r)\,T_n ( x_i^(r) ), (2.2) where Tn(x)\T_n(x)\ is a one-dimensional graded polynomial basis. Given a polynomial p(x)=∑∈supp(p)pT(x)p(x)= _n (p)p_n\,T_n(x),11 1 ∈ℕn is a multi-index. supp(p)supp(p) is the set of nonzero coefficients of p(⋅)p(·) (in this specific basis) and T(x):=∏i=1DTni(x)T_n(x):= _i=1^DT_n_i(x) is a multi-dimensional polynomial. define the single-level functional g(w):=μ(w)[p(x)]=∑∈supp(p)p∏i=1Dani,i(wi),w∈(ΔR−1)D,g(w)\;:=\;E_μ(w)[p(x)]\;=\; _n (p)p_n _i=1^Da_n_i,i(w_i), w∈( ^R-1)^D, (2.3) and, for L≥1L≥ 1 levels with a free mixing weight β∈ΔL−1β∈ ^L-1, the objective F(w,β):=∑l=1Lβlg(w(l))onℱ:=(ΔR−1)D×L×ΔL−1.F(w,β)\;:=\; _l=1^L _l\,g(w^(l)) \;:=\;( ^R-1)^D× L× ^L-1. (2.4) Call level l present if βl>0 _l>0, and write Vl:=g(w(l))V_l:=g(w^(l)) for its value. We prove in Appendix A.1 that the continuous optimization problem,22 2 Our implementation parametrizes w through softmax to enforce its simplex constraint with no fundamental differences to conclusions; β is not parametrized or optimized at all, held fixed at the uniform average. min(w,β)∈ℱF(w,β) _(w,β) \,F(w,β) (2.5) is equivalent to the original MAX-CUT problem (Eq. 1.1); despite being nonconvex, every suboptimal point has zero escape barrier when β is free to move33 3 Can be strictly improved through a feasible path originating at this point. In this case, the objective polynomial p(x)p(x) is the max-cut objective of Eq. 1.1, and the particles’ support is −1,1\-1,1\. Each μi(l) _i^(l) is represented by R atoms with softmax weights and tanh -parameterized locations, making moment-matrix positivity guaranteed and leaving an unconstrained problem with O(LnR)O(LnR) variables (linear in n for fixed L,RL,R, versus O(n2)O(n^2) for the GW SDP (Appendix B.5.2)). We solve this problem over w with L-BFGS (Liu and Nocedal, 1989) across a penalty-continuation schedule, holding β fixed at the uniform average βl=1/L _l=1/L rather than optimizing it. 44 4 App. A, Prop. 4 gives the weaker barrier bound this restriction leaves intact (details of the w-only solve in Alg. A) 2.2 Graph-coarsening initialization At larger scales, finite-particle relaxation benefits from a strong initialization; we use Combinatorial Multigrid (CMG) (Langston et al., 2019; Koutis et al., 2011) to construct a structure-aware warm start. CMG builds a coarsen→ → graph hierarchy: at each level, vertex i joins the cluster of its strongest neighbor B[i]=argmaxj∼iwijB[i]= _j iw_ij when M[i]/D[i]≥1/8M[i]/D[i]≥ 1/8, where M[i]=maxj∼iwijM[i]= _j iw_ij and D[i]=∑j∼iwijD[i]= _j iw_ij; otherwise it remains a singleton. We directly solve the coarsest graph, and the solution is projected back to the original graph with local-flip refinement at each level (total cost O(|E|logn)O(|E| n)). The resulting initialization is entirely graph-driven and requires no training data. Its value comes from exposing large-scale structure before continuous refinement. When edge weights are nearly uniform, however, little structure is available to exploit, the hierarchy compresses poorly, and the warm-start advantage diminishes. This behavior appears in the experiments and is consistent with the mechanism of the method. 2.3 The composed pipeline CMG returns a binary warm start xcmgx_cmg that is already refined by single-bit flips. From there, PPR searches over a continuous particle representation that can make simultaneous multi-node changes. In the stronger configuration, the best binary solution from pass p is used to initialize pass p+1p+1. A single 2-opt (Croes, 1958) sweep is applied after the final PPR pass (applying 2-opt after every pass tends to lock the solution into a two-bit local basin too early (Table 7)). For dense graphs with more than 3n3n edges, we first apply the Spielman-Srivastava (S-S) effective-resistance sparsification (Spielman and Srivastava, 2011); this step is a no-op for the already-sparse structured instances that dominate our results. This is the pipeline we evaluate in Section 3: Spielman-Srivastava spectral sparsification (Spielman and Srivastava, 2011) (when needed) feeds a CMG warm start, which PPR refines on the finest graph across one or more passes, closed by a single 2-opt sweep; an optional discrete tail (Kernighan-Lin, 3-opt, restarts, and a memetic GA) can be appended afterward. Figure 2 (Appendix B.4) draws this end to end, and Appendix B.3 summarizes how the three main stages complement each other. 3 Experiments We evaluate our pipeline (Section 2.3 with details in Appendix B) on structured toroidal Ising instances from the Biq Mac library (Rendl et al., 2010) (branch-and-cut exact optima as ground truth) and on real G-set instances up to n=20,000n=20,000; ratios are cut/optimum. We report 0.8780.878 as the poly.-time worst-case guarantee (Goemans and Williamson, 1995) (not GW’s typical achieved cut, which is far higher on structured instances); where we do contrast against an achieved GW cut we use a measured SDP-plus-rounding solve. Structural warm start dominates raw search on the hard small instance. The n=15n=15 instance shows that CMG finds the optimum in 30μ30\, , five orders of magnitude less time than the 2121 random PPR restarts consume, and the best of those restarts still reaches a cut of only 3737 (one short of the optimal 3838); none of the 2121 restarts finds the exact optimum. No additional restart budget closes the gap. The instance is small, but it isolates the failure mode of random initialization: once the solver enters the wrong basin, further local optimization does not recover the optimum. Rank R>1R>1 is necessary for the composed pipeline to improve on the warm start. Table 1 reports the pipeline on two toroidal families with published exact optima (of six tested; the other four follow the same pattern), together with a dense expander contrast. The R=1R=1 configuration barely moves off CMG; R≥2R≥ 2 lifts every structured instance 44-1515 points past CMG alone, well past the 0.8780.878 worst-case line. On the expander g05_60, by contrast, CMG is already at 0.960.96 and no configuration improves it, as the dense-regime failure mode described above predicts. Table 1: S-S→ → , 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=8L=32,R=8. Family n CMG P-16,R=1R=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 Pushed further, on the largest exact-optimum instance in this comparison the pipeline reaches 97.5%97.5\% mean and 98.4%98.4\% best. t2g20 (n=400n=400) is the largest instance in Table 1 with a published exact optimum, and the weakest single-shot result above. Chaining five PPR passes lifts CMG’s 0.8320.832 to 0.9520.952; a single closing 2-opt sweep lifts this to 0.9750.975 mean, 0.9840.984 best seed (Table 7 and Figure 5, both in Appendix B.5.6). Interleaving 2-opt after every pass instead locks the solution into a 2-opt basin after pass 1, finishing at only 0.9570.957, so the ordering (search, then polish once) matters. Restart count saturates quickly (k=40→80→160k=40→ 80→ 160 buys +0.003+0.003 then +0.001+0.001), confirming that the quality of the warm-start basin, not restart breadth, is the bottleneck (Figure 6). With a discrete polish tail, our pipeline reaches the published optimum on all sixty Biq Mac instances. Chen et al. (Chen et al., 2026) train a GNN to accelerate B&B to a proven optimum on 66 Biq Mac families (6060 instances). Our pipeline with a discrete tail (multi-pass PPR → 2-opt (Croes, 1958) → Kernighan-Lin (Kernighan and Lin, 1970) → 3-opt (Lin and Kernighan, 1973) → 200200-restart → memetic GA (Moscato and Cotta, 2003; Chu and Beasley, 1998)) matches the published optimum on every one of the 6060 (Table 2, Figure 9) in 8.58.5-130.5130.5s per instance, against B&B times up to 40,93040,930s (Mosek SDP bound) or 4,5094,509s (learned proxy). While they prove optimality, we report a heuristic cut that matches a published one. However, it answers the comparison the learned solvers set up, with no training data or inference hardware. The g05 expanders also confirm Table 1’s dense-regime pattern: warm start alone already sits at 0.970.97-0.980.98, so light PPR closes most of the gap. Table 2: 1010 instances chosen from the 66 Biq Mac families (Chen et al., 2026); full pipeline matches all 6060 published optimum. Mean single-core per-instance wall clock used for timing comparisons; B&B times from (Chen et al., 2026), Tab. 33. Ours (heuristic) (Chen et al., 2026) B&B (s) Family n CMG Pipeline time (s) Vanilla (s) Neural (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 w01_100 100 0.881 1.000 12.7 11349 1074 At the continuous phase, L-BFGS beats Adam; but, the discrete tail sets the final cut, not the optimizer. PPR solves each penalty-continuation stage with a single L-BFGS call; we swapped that inner solve for Adam (Kingma and Ba, 2015), full-batch gradient descent (GD), and a level-subsampled stochastic variant based on stochastic approximation (Robbins and Monro, 1951) on eight instances, with the warm start, restarts, continuation schedule, and downstream discrete tail held fixed (full per-instance table in Appendix B.5.12). Pre-tail, the four disagree by up to 7.4%7.4\%55 5 L-BFGS’s curvature edge leaves Adam up to 6.2%6.2\% behind, and GD, with neither momentum nor curvature, stalls at the CMG warm start on G1 and is 1111-30×30× slower per instance., but the identical discrete tail collapses that spread to ≤0.7%≤ 0.7\% on every instance: L-BFGS just gets there the cheapest. The warm start’s advantage persists to n=20,000. A dense coupling matrix requires 8n28n^2 bytes (3.23.2 GB at n=20,000n=20,000), impractical for sparse-signed graphs (|E|≈2n|E|\!≈\!2n). CSR representations storing only 2|E|2|E| nonzeros resolve this. Running CMG → light PPR → 2-opt on 66 real G-set instances, n=5Kn=5K–20K20K (Table 3), reduces memory by 833833–3333×3333× with linear scaling in n. Gains over CMG warm start through the continuous-relaxation path alone, Δ2opt _2opt, remain in a tight 1.191.19–1.21×1.21× band, matching the behavior at n=125n=125–10001000 (Figure 8(a)). Adding a discrete tail66 6 Kernighan-Lin, 3-opt, a memetic GA, and an iterated local search: the retuned configuration of Table 14. raises the final gain to Δfinal=1.32 _final=1.32–1.33×1.33×, again with no observable decay. For G77 and G81, the full pipeline reaches 98.7%98.7\% and 99.0%99.0\% (the continuous-relaxation path alone reaches 90.8%90.8\% and 89.8%89.8\%) of the externally verified reported optima (Cosm’s (Zick et al., 2026) 99409940 and 1406014060). A tabu-diversified tail (Glover, 1986; Glover and Laguna, 1997) reaches 1396213962 (99.3%99.3\% of 1406014060) on G81 in ∼ 213 s and provides the study’s only internal optimality certificate, verified in a further ∼ 2.4 s across 4040 connected cores (Appendix B.5.13). Table 3: Sparse CSR path, four of six G-set instances, single core. “mem”: dense/CSR storage ratio. “2opt”: cut after CMG→ → 2-opt only, with its own gain over CMG, Δ2opt _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 Δfinal _final. ratio-to-OPT given at both stages, only where an externally verified optimum exists. Instance n mem cmg 2opt Δ2opt _2opt final Δfinal _final ratio-to-OPT (2opt/final) G57 5000 833.3× 2600 3142 1.208 3460 1.331 – G67 10000 1666.7× 5198 6258 1.204 6872 1.322 – G77 14000 2333.3× 7454 9022 1.211 9810 1.316 0.908 / 0.9869 G81 20000 3333.3× 10574 12626 1.194 13922 1.317 0.898 / 0.9902 4 Discussion: comparison and limitations Comparable assumptions to bespoke heuristics. Cosm (Zick et al., 2026) reports optimality on G77 and G81 using an external exact solver rather than an internal proof. Our ratio-to-optimum results rely on the same type of reference. We do not aim to match Cosm’s runtime performance; our contribution is a general framework that combines reusable structure-aware components (nonconvex relaxation and spectral coarsening) with a broader class of constraints rather than a solver tailored to MAX-CUT. When the method provides little benefit. On dense, well-conditioned graphs, CMG coarsening succeeds almost everywhere, so the warm start is already near the local-flip limit and PPR yields no measurable improvement (Table 1). On uniform-weight Erdős-Rényi graphs, the CMG grouping criterion M[i]/D[i]≥1/8M[i]/D[i]≥ 1/8 rarely holds once n>16n>16, preventing meaningful coarsening. In both cases, the pipeline exploits weight heterogeneity, so these graph families provide little structure to exploit. This behavior is consistent with our design goal of a structure-aware method. Open questions. A discrete polishing stage (Kernighan–Lin, 3-opt, or a memetic GA) closes most of the remaining gap on the hardest instances. However, a random-start baseline with the same polishing budget matches or exceeds the CMG-seeded pipeline on roughly half of these cases. Once sufficient restarts are available, final solution quality is often determined more by the polishing stage than by the warm start (Table 13; see also Table 12). Understanding this trade-off and extending the approach beyond n=20,000n=20,000 under fixed compute remain promising directions. 5 Conclusion A structure-aware CMG warm start combined with a particle-based continuous relaxation achieves near-optimal MAX-CUT solutions across a wide range of problem sizes. The approach reaches 97.5%97.5\% mean (best-seed 98.4%98.4\%) of the exact optimum on t2g20 (n=400n=400), and 98.798.7–99.0%99.0\% of the exact optimum on the two largest G-set instances with externally verified optima. These gains persist up to 20,00020,000 vertices without observable degradation, although they naturally diminish on graph families with little exploitable structure. Appendix A.1 discusses the theoretical motivation that continuous relaxation eliminates escape barriers under free mixing, while the CMG warm start escapes the limitations of purely local search. In compute-constrained regimes, this combination provides a robust advantage; however, when large discrete-search budgets become available, the polishing stage increasingly determines final solution quality. Consistent with the tail-ablation study (Table 13), a random start carried through the same high-budget discrete tail can match or exceed the CMG-seeded pipeline on roughly half of the hardest instances tested. References Barahona (1982) F. Barahona On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General 15 (10), p. 3241–3253. Cited by: §1. Boumal et al. (2016) N. Boumal, V. Voroninski, and A. S. Bandeira The non-convex burer-monteiro approach works on smooth semidefinite programs. Advances in Neural Information Processing Systems 29. Cited by: §B.5.9, §C.5. Burer and Monteiro (2003) S. Burer and R. D. C. Monteiro A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming 95 (2), p. 329–357. Cited by: §B.5.11, §C.2, §C.5, §1. Chen et al. (2026) H. Chen, C. Qian, C. Morris, A. Lodi, and C. Li Solving Max-Cut to global optimality via feasibility-preserving graph neural networks. Note: arXiv:2605.07113 Cited by: Figure 9, Figure 9, §B.1, §1, Table 2, Table 2, Table 2, §3. Chu and Beasley (1998) P. C. Chu and J. E. Beasley A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics 4 (1), p. 63–86. Cited by: §C.5, §3. Croes (1958) G. A. Croes A method for solving traveling-salesman problems. Operations Research 6 (6), p. 791–812. Cited by: §C.3, §C.5, §2.3, §3. Dhillon et al. (2007) I. S. Dhillon, Y. Guan, and B. Kulis Weighted graph cuts without eigenvectors: a multilevel approach. IEEE Transactions on Pattern Analysis and Machine Intelligence 29 (11), p. 1944–1957. Cited by: §B.5.4. Dong et al. (2025) Y. Dong, P. Peng, and A. Vakilian Learning-augmented streaming algorithms for approximating MAX-CUT. In Innovations in Theoretical Computer Science (ITCS), Note: arXiv:2412.09773 Cited by: §B.1. Garey and Johnson (1979) M. R. Garey and D. S. Johnson Computers and intractability: a guide to the theory of np-completeness. W. H. Freeman. Cited by: §1. Glover and Laguna (1997) F. Glover and M. Laguna Tabu search. Kluwer Academic Publishers. Cited by: §B.5.13, §3. Glover (1986) F. Glover Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13 (5), p. 533–549. Cited by: §B.5.13, §3. Goemans and Williamson (1995) M. X. Goemans and D. P. Williamson Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42 (6), p. 1115–1145. Cited by: §B.1, §1, §3. Huangfu and Hall (2018) Q. Huangfu and J. A. J. Hall Parallelizing the dual revised simplex method. Mathematical Programming Computation 10 (1), p. 119–142. Note: HiGHS solver, https://highs.dev/ Cited by: §B.5.13. Karp (1972) R. M. Karp Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (Eds.), p. 85–103. Cited by: §1. Karypis and Kumar (1998) G. Karypis and V. Kumar A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20 (1), p. 359–392. Cited by: §B.5.4. Kernighan and Lin (1970) B. W. Kernighan and S. Lin An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal 49 (2), p. 291–307. Cited by: §C.4, §C.5, §3. Khot et al. (2007) S. Khot, G. Kindler, E. Mossel, and R. O’Donnell Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?. SIAM Journal on Computing 37 (1), p. 319–357. Cited by: §1. Kingma and Ba (2015) D. P. Kingma and J. Ba Adam: a method for stochastic optimization. In International Conference on Learning Representations (ICLR), Note: arXiv:1412.6980 Cited by: §3. Koutis et al. (2011) I. Koutis, G. L. Miller, and D. Tolliver Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. Computer Vision and Image Understanding 115 (12), p. 1638–1646. Cited by: §B.3, §2.2. Kraft (1988) D. Kraft A software package for sequential quadratic programming. Technical report Technical Report DFVLR-FB 88-28, DFVLR, German Aerospace Center. Cited by: §B.5.5, §C.2. Langston et al. (2019) M. H. Langston, M. T. Harris, P. Letourneau, R. Lethin, and J. Ezick Combinatorial multigrid: advanced preconditioners for ill-conditioned linear systems. In IEEE High Performance Extreme Computing Conference (HPEC), Cited by: §B.3, §2.2. Lasserre (2001) J. B. Lasserre Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization 11 (3), p. 796–817. Cited by: §B.1, §2.1. Letourneau et al. (2023) P. Letourneau, D. Jones, M. Morse, and M. H. Langston An efficient framework for global non-convex polynomial optimization over the hypercube. Note: arXiv:2308.16731 Cited by: Appendix A, §1, §2.1. Lin and Kernighan (1973) S. Lin and B. W. Kernighan An effective heuristic algorithm for the traveling-salesman problem. Operations Research 21 (2), p. 498–516. Cited by: §C.4, §C.5, §3. Liu and Nocedal (1989) D. C. Liu and J. Nocedal On the limited memory BFGS method for large scale optimization. Mathematical Programming 45 (1–3), p. 503–528. Cited by: §2.1. Lucas (2014) A. Lucas Ising formulations of many NP problems. Frontiers in Physics 2, p. 5. Cited by: §1. Moscato and Cotta (2003) P. Moscato and C. Cotta A gentle introduction to memetic algorithms. In Handbook of Metaheuristics, F. Glover and G. A. Kochenberger (Eds.), p. 105–144. Cited by: §C.5, §3. Rendl et al. (2010) F. Rendl, G. Rinaldi, and A. Wiegele Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Mathematical Programming 121 (2), p. 307–335. Note: Biq Mac Library, https://biqmac.aau.at/ Cited by: §B.1, Table 1, Table 1, §3. Robbins and Monro (1951) H. Robbins and S. Monro A stochastic approximation method. The Annals of Mathematical Statistics 22 (3), p. 400–407. Cited by: §3. Spielman and Srivastava (2011) D. A. Spielman and N. Srivastava Graph sparsification by effective resistances. SIAM Journal on Computing 40 (6), p. 1913–1926. Cited by: §B.3, §B.5.3, §C.1, §2.3, §2.3. Wang et al. (2017) P. Wang, W. Chang, and J. Z. Kolter The mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints. In arXiv preprint arXiv:1706.00476, Cited by: §B.5.9, §C.5. Yau et al. (2024) M. Yau, N. Karalias, E. Lu, J. Xu, and S. Jegelka Are graph neural networks optimal approximation algorithms?. In Advances in Neural Information Processing Systems (NeurIPS), Note: arXiv:2310.00526 Cited by: §B.1, §1. Zachary (1977) W. W. Zachary An information flow model for conflict and fission in small groups. Journal of Anthropological Research 33 (4), p. 452–473. Cited by: §B.5.11. Zick et al. (2026) K. M. Zick, N. Shukla, and A. Marakov Cosm: collective switched motion for fast and accurate sparse Ising optimization. Note: arXiv:2605.30355 Cited by: §B.5.13, Table 14, §3, §4. Appendix A Particle Polynomial Relaxation (PPR) for MAX-CUT: full algorithm Algorithm A specializes the particle-parameterization solver of Letourneau et al. (2023) to the MAX-CUT setting. The only constraint is the binary/box penalty ρ2‖meanl(a2l)−‖2 ρ2\|mean_l(a2_l)-1\|^2 appearing in the objective below, which drives each marginal’s second moment to one and is therefore zero exactly when every marginal is supported on −1,+1\-1,+1\. There is no equality-constraint dual loop; instead, K independent restarts are run through a fixed penalty-continuation schedule ρ1<⋯<ρS _1<·s< _S. Pseudocode for the rest of the pipeline is presented in Appendix C. algorithm2e [htbp!] for MAX-CUT (n×n× n, normalized); warm start x0x_0; L,R,kL,R,k; sat; penalty schedule ρ1<⋯<ρS _1<·s< _S ±1± 1 cut found best←−∞best←-∞ =1,…,k=1,…,k ul,0,i←atanh(sat⋅x0,i)+(0,0.02)u_l,0,i (sat· x_0,i)+N(0,0.02) for all l *warm-started slot all other ul,r,i∼(0,0.02)u_l,r,i (0,0.02) *unwarmed particles ρ=ρ1,…,ρSρ= _1,…, _S form marginals al=∑rwrtanh(ul,r,⋅)a_l= _rw_r\, (u_l,r,·), a2l=∑rwrtanh(ul,r,⋅)2a2_l= _rw_r\, (u_l,r,·)^2 F(u)←−12L∑lal⊤Jal+ρ2∥meanl(a2l)−∥2F(u)←- 12L _la_l Ja_l+ ρ2 \|mean_l(a2_l)-1 \|^2 run L-BFGS on F(u)F(u) to convergence (l,r)(l,r) x^i←sign(tanh(ul,r,i)) x_i ( (u_l,r,i)) for all i local-flip refine x x on G keep x x if Cut(x^)>bestCut( x)>best x x found across all restarts and (l,r)(l,r) A.1 Theory and Proofs In this appendix, we demonstrate that the proposed continuous reformulation for the MAX-CUT problem possesses an advantageous optimization landscape. Namely, we show that for every non-optimal feasible point, there exists a path of descent (not necessarily strict). In other words, the reformulated objective does not possess any strict local minima other then global minima (which may or may not be strict either). The arguments are processed without the softmax parametrization for simplicity. It can be shown that the results still hold following such parametrization. Weights, levels, and the objective Recall that level-l discrete product measure is μ(l)(⋅)=⨂i=1D(∑r=1Rwi(l,r)δx¯i(r)),wi(l,⋅)∈ΔR−1,μ^(l)(·)\;=\; _i=1^D ( _r=1^Rw_i^(l,r)\, _ x_i^(r) ), w_i^(l,·)∈ ^R-1, (A.1) where ΔR−1:=w∈ℝ≥0R:∑rwr=1 ^R-1:=\w _≥ 0^R: _rw_r=1\ is the probability simplex. Its degree-n marginal moment in coordinate i is an,i(l):=∑r=1Rwi(l,r)Tn(x¯i(r)),a_n,i^(l)\;:=\; _r=1^Rw_i^(l,r)\,T_n ( x_i^(r) ), (A.2) so a0,i(l)≡1a_0,i^(l)≡ 1 is pinned by the simplex constraint. Define the single-level functional g(w):=μ(w)[p(x)]=∑∈supp(p)p∏i=1Dani,i(wi),w∈(ΔR−1)D,g(w)\;:=\;E_μ(w)[p(x)]\;=\; _n (p)p_n _i=1^Da_n_i,i(w_i), w∈( ^R-1)^D, (A.3) and, for L≥1L≥ 1 levels with a free mixing weight β∈ΔL−1β∈ ^L-1, the objective F(w,β):=∑l=1Lβlg(w(l))onℱ:=(ΔR−1)D×L×ΔL−1.F(w,β)\;:=\; _l=1^L _l\,g(w^(l)) \;:=\;( ^R-1)^D× L× ^L-1. (A.4) Call level l present if βl>0 _l>0, and write Vl:=g(w(l))V_l:=g(w^(l)) for its value. Oscillation Let C:=maxx¯∈X¯p(x¯)−minx¯∈X¯p(x¯)=maxx¯∈X¯p(x¯)−p∗C\;:=\; _ x∈ Xp( x)- _ x∈ Xp( x)\;=\; _ x∈ Xp( x)-p^* (A.5) be the (finite) oscillation of p over the grid. Since g(w)g(w) in (A.3) is an expectation of p under a probability measure supported on X¯ X, every feasible w satisfies p∗≤g(w)≤p∗+Cp^*≤ g(w)≤ p^*+C, hence |g(w)−g(w′)|≤Cfor all feasible w,w′.|g(w)-g(w )|\;≤\;C all feasible w,w . (A.6) Definition 1 (Escape barrier). For L≥1L≥ 1 let F and ℱF be as in (A.4). The escape barrier at a feasible point (w,β)(w,β) is B(w,β):=infπ[maxt∈[0,1]F(π(t))−F(π(0))],B(w,β):= _π\ [\ _t∈[0,1]F(π(t))\;-\;F(π(0))\ ], (A.7) the infimum taken over all continuous feasible paths π:[0,1]→ℱπ:[0,1] with π(0)=(w,β)π(0)=(w,β) and F(π(1))<F(π(0))F(π(1))<F(π(0)) (so B:=+∞B:=+∞ when no such path exists). Note B≥0B≥ 0 always, since t=0t=0 is admissible in the maximum. The barrier dichotomy needs one elementary fact in both of its directions, so we record it first. Theorem 2 (Value equivalence). π∗:=min(w,β)∈ℱF(w,β)=p∗ π^*:= _(w,β) F(w,β)=p^*. Proof. Step 1 (π∗≤p∗π^*≤ p^*). Let x¯∗∈X¯ x^*∈ X be a global minimizer of p over the grid (which exists since X¯ X is finite). For each i let ri∗r_i^* be the index with x¯i(ri∗)=x¯i∗ x_i^(r_i^*)= x_i^*, and set wi(1,r):=[r=ri∗]w_i^(1,r):=I[r=r_i^*] (one-hot), with β1=1 _1=1. This is feasible, and F evaluates exactly to p(x¯∗)=p∗p( x^*)=p^* term by term. Hence π∗≤p∗π^*≤ p^*. Step 2 (π∗≥p∗π^*≥ p^*). For any feasible w, each level’s contribution μ(l)(w)[p]E_μ^(l)(w)[p] is, by definition (A.1), the expectation of p under a genuine probability measure supported on X¯ X, a convex combination of point masses at grid points, since μ(l)μ^(l) is a product of finitely supported marginals. Every such expectation is ≥minx¯∈X¯p(x¯)=p∗≥ _ x∈ Xp( x)=p^*. Any convex combination of these expectations77 7 In particular, a free β∈ΔL−1β∈ ^L-1, not merely a uniform average preserves the bound, so F(w,β)≥p∗F(w,β)≥ p^* for every feasible (w,β)(w,β), giving π∗≥p∗π^*≥ p^*. Combining, π∗=p∗π^*=p^*. ∎ Theorem 3 (Lateral-escape: zero barrier at every suboptimal point). Let L≥2L≥ 2 and let (w,β)∈ℱ(w,β) satisfy F(w,β)>p∗F(w,β)>p^*. Then for every δ∈(0,1]δ∈(0,1] there is a continuous feasible path π:[0,1]→ℱπ:[0,1] with π(0)=(w,β)π(0)=(w,β) such that F(π(1))=p∗andmaxt∈[0,1]F(π(t))≤F(w,β)+δC.F(π(1))=p^* _t∈[0,1]F(π(t))\;≤\;F(w,β)+δ\,C. (A.8) Consequently B(w,β)=0B(w,β)=0: the net descent F(w,β)−p∗>0F(w,β)-p^*>0 is a fixed positive quantity independent of δ, while the barrier that must be crossed to realize it is at most δCδ C and hence arbitrarily small. Conversely, if F(w,β)=p∗F(w,β)=p^* then F≥p∗F≥ p^* everywhere on ℱF (Step 2 of Theorem 2) rules out any feasible path reaching a lower value, so B(w,β)=+∞B(w,β)=+∞. Together the two directions give the full dichotomy: B(w,β)=0B(w,β)=0 iff F(w,β)>p∗F(w,β)>p^*, and B(w,β)=+∞B(w,β)=+∞ if and only if F(w,β)=p∗F(w,β)=p^*, with no intermediate case (no suboptimal point is protected by a barrier of positive height. Proof. Let x¯∗∈X¯ x^*∈ X be a global minimizer of p over the grid and let e(x¯∗)∈(ΔR−1)De( x^*)∈( ^R-1)^D be the corresponding one-hot weight vector, so g(e(x¯∗))=p(x¯∗)=p∗g(e( x^*))=p( x^*)=p^* (this is the only place a specific weight vector is needed, and it requires nothing of R beyond x¯∗∈X¯ x^*∈ X; no Vandermonde or rank hypothesis enters). Write Vl:=g(w(l))V_l:=g(w^(l)) and call level l present if βl>0 _l>0. Two cases. Case 1: some level l1l_1 is absent (βl1=0 _l_1=0). Phase A (exactly flat). Holding β and every other level fixed, move w(l1)w^(l_1) to e(x¯∗)e( x^*) along the straight line (1−t)w(l1)+te(x¯∗)(1-t)w^(l_1)+t\,e( x^*), feasible for all t by convexity of each ΔR−1 ^R-1. Since F depends on w(l1)w^(l_1) only through the product βl1g(w(l1)) _l_1g(w^(l_1)) and βl1=0 _l_1=0, F is constant along the whole of Phase A: the rise is exactly 00. Phase B (exactly affine, strictly decreasing). Now move βl1 _l_1 from 00 to 11, taking the removed mass from the other levels proportionally, i.e. βl1(t)=t _l_1(t)=t and βl(t)=(1−t)βl _l(t)=(1-t) _l for l≠l1l≠ l_1. This stays in ΔL−1 ^L-1, and since every VlV_l is now fixed, F(t)=(1−t)F(w,β)+tp∗F(t)=(1-t)F(w,β)+t\,p^* is exactly affine with constant slope p∗−F(w,β)<0p^*-F(w,β)<0: strictly decreasing, ending at p∗p^*. The path never rises at all, so (A.8) holds with room to spare, for every δ. Case 2: every level is present (βl>0 _l>0 for all l). Fix δ∈(0,1]δ∈(0,1], choose l1∈argmaxlVll_1∈ _lV_l (so Vl1≥∑lβlVl=F(w,β)V_l_1≥ _l _lV_l=F(w,β)), and set δ′:=min(δ,βl1)>0δ := (δ, _l_1)>0. Phase A (lateral: non-increasing, and exactly flat at a critical point). Holding all w(l)w^(l) fixed, decrease βl1 _l_1 from βl1 _l_1 to δ′δ , redistributing the removed mass βl1−δ′≥0 _l_1-δ ≥ 0 proportionally among the other levels: βl(t) _l(t) interpolates affinely, remaining in ΔL−1 ^L-1 throughout. Mass is thereby moved out of a level of maximal value Vl1V_l_1 and into a convex combination of levels each of value ≤Vl1≤ V_l_1, so F is non-increasing along Phase A; the rise is ≤0≤ 0.88 8 When all present levels share a common value, exactly the situation forced at any critical point by Step 2 of Theorem 2, Phase A is identically flat: it is a genuine lateral move, neither ascending nor descending, and it is available regardless of how deeply each individual level is trapped. Phase B (the only ascent, bounded by δ′Cδ C). With β now fixed at βl1=δ′ _l_1=δ , move w(l1)w^(l_1) to e(x¯∗)e( x^*) along the straight line as in Case 1. Only the term βl1g(w(l1))=δ′g(w(l1)) _l_1g(w^(l_1))=δ g(w^(l_1)) varies, so for every t F(π(t))−F(π(tA))=δ′[g(w(l1)(t))−Vl1]≤δ′C≤δC,F(π(t))-F(π(t_A))=δ [g(w^(l_1)(t))-V_l_1 ]\;≤\;δ C\;≤\;δ C, (A.9) where tAt_A is the end of Phase A and the bound uses |g(w)−g(w′)|≤C|g(w)-g(w )|≤ C from (A.6). Since Phase A did not raise F, the running maximum over Phases A-B is at most F(w,β)+δCF(w,β)+δ C. Phase C (exactly affine, strictly decreasing). Now Vl1=p∗V_l_1=p^* and all VlV_l are again fixed; move βl1 _l_1 from δ′δ to 11, taking mass from the others proportionally as in Case 1’s Phase B. F is exactly affine in the interpolation parameter with endpoint value p∗p^*, hence non-increasing (strictly decreasing unless the starting value already equals p∗p^*, in which case the endpoint is reached immediately), and F(π(1))=p∗F(π(1))=p^*. Phase C therefore adds no new maximum, and (A.8) holds. In both cases the path satisfies (A.8), and F(π(1))=p∗<F(w,β)F(π(1))=p^*<F(w,β) makes π admissible in Definition 1; letting δ↓0δ 0 gives B(w,β)=0B(w,β)=0. The converse direction stated above needs no further argument beyond F≥p∗F≥ p^* everywhere. ∎ The zero-barrier statement is deliberately weaker than “local minimum ⇒ global minimum,” and the reason is not an artifact of the fixed grid. The stronger statement would require a path whose derivative is strictly negative immediately at t=0t=0, hence a mechanism for spawning fresh mass at x¯∗ x^* inside a level that already carries mass without first emptying it. Here the level to be repositioned is first emptied to mass δ′δ (otherwise repositioning it would cost O(1)O(1) rather than O(δ)O(δ)), and the emptying is lateral, not descending. The result is a path that descends overall but not from the outset, which is exactly the distinction between B=0B=0 (proved here) and “not a local minimum” (false here). The operative consequence survives: p∗p^* is reachable from anywhere at arbitrarily small cost, so a solver willing to accept a transient increase of size δCδ C is never blocked by a genuine energy barrier, only by the difficulty of finding the lateral direction. What this buys the deployed algorithm. Theorem 3’s mechanism needs β to move: Case 1 needs an absent level (βl1=0 _l_1=0) and Case 2 needs βl1 _l_1 shrunk to a small δ′δ before the repositioning move. Algorithm A, and every solver run in this paper, never varies β at all: it always averages all L levels uniformly, βl=1/L _l=1/L. Eq. (A.4) is stated for a general, possibly free β∈ΔL−1β∈ ^L-1 because the construction and Theorem 2 hold at that generality (Step 2’s bound is proved for any convex combination, uniform included), but Theorem 3’s zero barrier is specific to a β that is free to move, and so does not, by itself, describe what Algorithm A is guaranteed. The following proposition states what survives when β is pinned at the uniform average. Proposition 4 (Barrier bound under the fixed uniform weighting). Let βl=1/L _l=1/L for every l, held fixed, and let w be feasible with F(w,1L)>p∗F(w, 1L1)>p^*. Define the fixed-β escape barrier Bfix(w)B_fix(w) exactly as in Definition 1, but with the infimum restricted to continuous paths that vary only w (as Algorithm A does; β is not a free coordinate of its search). Then Bfix(w)≤C/L.B_fix(w)\;≤\;C/L. Proof. Write Vl:=g(w(l))V_l:=g(w^(l)) as before and choose l1∈argmaxlVll_1∈ _lV_l, so Vl1≥∑l1LVl=F(w,1L)V_l_1≥ _l 1LV_l=F(w, 1L1), exactly as in Theorem 3’s Case 2. Move w(l1)w^(l_1) along the straight line (1−t)w(l1)+te(x¯∗)(1-t)w^(l_1)+t\,e( x^*) to the global minimizer’s one-hot weight, holding β (hence βl1=1/L _l_1=1/L) and every other level fixed throughout; there is no Phase A here, since redistributing β is unavailable. Only the term 1Lg(w(l1)) 1Lg(w^(l_1)) varies, so for every t F(π(t))−F(w,1L)=1L[g(w(l1)(t))−Vl1]≤1LC,F(π(t))-F(w, 1L1)= 1L [g(w^(l_1)(t))-V_l_1 ]\;≤\; 1LC, using g(w(l1)(t))≤p∗+Cg(w^(l_1)(t))≤ p^*+C and Vl1≥p∗V_l_1≥ p^* (Eq. (A.6)), so the running maximum over the whole path is at most F(w,1L)+C/LF(w, 1L1)+C/L. At t=1t=1, F(π(1))−F(w,1L)=1L(p∗−Vl1)<0F(π(1))-F(w, 1L1)= 1L(p^*-V_l_1)<0, a strict decrease since Vl1≥F(w,1L)>p∗V_l_1≥ F(w, 1L1)>p^*. Hence π is admissible in the (restricted) Definition 1, giving Bfix(w)≤C/LB_fix(w)≤ C/L. ∎ As L→∞L→∞ this recovers Theorem 3’s B=0B=0: it is exactly the freedom to shrink βl1→0 _l_1→ 0 in Cases 1-2 that pinning β at 1/L1/L forecloses, leaving δ′=1/Lδ =1/L (not driveable →0→ 0 at fixed L) as the best available discount on the oscillation bound. Algorithm A is therefore guaranteed only the weaker C/LC/L barrier of Proposition 4, not the zero barrier of Theorem 3; realizing the stronger guarantee would require implementing a solver that actually moves β, which this paper does not do. Appendix B Extended background, related work, pipeline mechanics, further results and contributions This appendix records additional material compressed in the main text: related approaches, the need for structured initialization, the roles of the three pipeline stages, the binary-constraint derivation, and the mechanics of coarsening and refinement. It is included for completeness and does not change any claims in the main text. B.1 Existing approaches MAX-CUT algorithms fall into several broad categories. Exact methods such as branch-and-bound (B&B) and dynamic programming provide certificates but scale exponentially in the worst case. The Biq Mac library (Rendl et al., 2010) uses exact methods to provide optima for the structured instances used as ground truth here. The Lasserre hierarchy (Lasserre, 2001) gives a sequence of increasingly tight semidefinite relaxations, but its moment matrices grow quickly with n. Goemans-Williamson (Goemans and Williamson, 1995) solves an SDP relaxation and rounds by random hyperplanes, giving the classical 0.8780.878 worst-case approximation ratio. Learned solvers form a more recent category: OptGNN (Yau et al., 2024) learns updates in a Burer-Monteiro relaxation, Chen et al. (Chen et al., 2026) learn SDP certificates for branch-and-bound, and Dong et al. (Dong et al., 2025) study streaming algorithms with an oracle-like learned labeling. Our method supplies the structural prior through graph coarsening instead of learning. B.2 Why structured initialization is necessary The finite-particle PPR solver is still an iterative nonconvex method. The exact moment formulation gives a useful theoretical target, but it does not ensure that a finite number of particles and restarts will find the right basin. The hard n=15n=15 instance illustrates the issue: random initialization misses the exact optimum in all 2121 restarts, while CMG finds it directly (Table 4). This motivates treating initialization as a central part of the solver rather than as an implementation detail. Table 4: Hard instance n=15n=15, seed =44=44, known optimum 3838. “CMG” means CMG followed by local-flip refinement. Strategy Cut Ratio Time Random-init PPR, best of 21 37 0.974 21×∼721×\! \!7s Random-init PPR, exact hits 0/21 – – CMG++flip 38 1.000 30μ30\, CMG→ warm start 38 1.000 ∼ 12s B.3 Three complementary tools The pipeline combines three stages. Spielman-Srivastava sparsification (Spielman and Srivastava, 2011) reduces dense graphs to sparse spectral approximations when appropriate. CMG (Langston et al., 2019; Koutis et al., 2011) builds a hierarchy from the graph’s own edge weights and returns a binary warm start. PPR then uses that warm start inside a continuous particle representation that can make multi-node changes. The composition is G→S-SG′⏟sparsify→G′→CMGxcmg⏟warm start→xcmg→PPRx′⏟fine-level polish→x′→2-optx∗⏟refine, G S-SG _sparsify→ G CMGx_cmg_warm start→ x_cmg PPRx _fine-level polish→ x 2-optx^*_refine, matching Figure 2. In our experiments, the strongest performance is obtained when the stages are composed in this order; removing individual stages generally reduces solution quality on the hardest instances; however, on graphs that are already sparse, the first stage is typically unnecessary. B.4 The pipeline end to end Figure 2 draws the composed architecture: S-S sparsification (a no-op on already-sparse graphs) feeds CMG coarsening to a directly-solvable coarsest level, with the SQP sweet-spot solve substituted in at any level with nℓ≤20n_ ≤ 20; the coarsest solution is projected back up through local-flip refinement; PPR then runs once, warm-started from that projection, on the finest graph; and multi-pass restarts followed by a single 2-opt sweep close the gap to the exact optimum. This is the pipeline used for every headline result in Section 3, traced end to end on a real graph in Appendix B.5.11. 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. B.5 Further Contributions and Additional Results The main contributions are: (1) applying the particle moment framework to the MAX-CUT binary constraint; (2) showing that CMG and PPR play complementary roles in the compute-constrained regime, with the heavy-tail ablation (Table 13) showing this advantage narrows, and a random start can match or exceed it on about half the instances tested, once a large discrete-tail budget is affordable; (3) demonstrating that PPR can improve beyond CMG’s one-flip local optimum on structured instances; (4) reporting the t2g20 result of 0.9750.975 mean and 0.9840.984 best cut/OPT; (5) identifying the dense homogeneous regime where the method adds little; (6) evaluating the effect of a stronger discrete tail; and (7) scaling the sparse CSR implementation to n=20,000n=20,000 with no observed decay in the gain over CMG across the tested size range. We follow below with more details on the problem formulation, pipeline details, and additional results to strengthen and highlight our findings. B.5.1 The binary-constraint derivation With xi∈−1,+1x_i∈\-1,+1\, MAX-CUT is maxx14∑(i,j)∈Ewij(1−xixj), _x 14 _(i,j)∈ Ew_ij(1-x_ix_j), or equivalently the minimization of its negative over the algebraic variety =x∈[−1,1]n:xi2=1∀iV=\x∈[-1,1]^n:x_i^2=1\ ∀ i\. B.5.2 Problem dimensions and scaling With degree-SOS =2=2, L levels, and R particles per factor, the particle solver uses O(LnR)O(LnR) parameters. For fixed L and R, this is linear in n, whereas the GW SDP uses O(n2)O(n^2) variables and Lasserre relaxations grow much faster. Table 5: Variable-count scaling for PPR-MAX-CUT and standard relaxations. Component Count Notes Particle locations and weights O(LnR)O(LnR) linear in n for fixed L,RL,R GW SDP variables O(n2)O(n^2) quadratic in n Lasserre level k SDP O((n+2kn)2)O\! ( n+2kn^2 ) grows rapidly with n B.5.3 Sparsification and leverage scores Effective-resistance sparsification samples edges according to leverage scores ℓe=weRe _e=w_eR_e, where Re=Lii†+Ljj†−2Lij†R_e=L _i+L _j-2L _ij is the effective resistance of edge e=(i,j)e=(i,j). High-leverage edges are structurally important, while low-leverage edges can often be removed while approximately preserving cuts (Spielman and Srivastava, 2011). Dense uniform graphs have nearly flat leverage scores, so sparsification gives little benefit. Weighted structured graphs can have highly skewed leverage distributions, allowing a much smaller graph to preserve the relevant cut structure. 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. B.5.4 CMG coarsening One CMG coarsening level consists of profiling the graph, splitting long or poorly connected forest paths, isolating weakly attached vertices, and contracting the resulting components. Algorithm B.5.4 gives one level of this procedure. algorithm2e [htbp!] graph coarsening, one level =(V,E,w)G=(V,E,w) G′G and cluster map B GraphProfile: B[i]←argmaxj∼iwijB[i]← _j iw_ij, M[i]←maxj∼iwijM[i]← _j iw_ij, D[i]←∑j∼iwijD[i]← _j iw_ij SplitForest: cut edges in B where path length is too large or conductance is low UpdateGroups: if M[i]/D[i]<1/8M[i]/D[i]<1/8, set B[i]←iB[i]← i ForestComponents: label components of B as clusters C1,…,Cnc\C_1,…,C_n_c\ Coarsen: wc1c2′←∑(i,j)∈E,i∈Cc1,j∈Cc2wijw _c_1c_2← _(i,j)∈ E,\,i∈ C_c_1,\,j∈ C_c_2w_ij G′G and cluster map B Solving the coarsest graph directly and projecting the solution back down with local-flip refinement gives the warm start xcmgx_cmg. Unlike balanced multilevel partitioners such as METIS (Karypis and Kumar, 1998) and Graclus (Dhillon et al., 2007), CMG does not force balanced partitions. This is useful for weighted Ising graphs whose cut structure is not balanced. Figure 4: CMG coarsening effectiveness versus graph density. Sparse structured graphs contract aggressively, while dense uniform graphs contract weakly. B.5.5 Refinement branches and multi-pass polishing At very small coarsened levels (nℓ≤20n_ ≤ 20), we can solve a rank-2, degree-2-SOS objective with SLSQP (Kraft, 1988) and then apply local-flip refinement. This branch is useful only because it runs on a small coarse graph. The headline Biq Mac and G-set results use the other branch: PPR runs directly on the finest graph, initialized from the CMG projection. Multiple PPR passes are then chained by feeding the best binary solution from one pass into the next, and the final result is polished by a single 2-opt sweep on the original graph. Table 6: Coarse sweet-spot (nℓ≤20n_ ≤ 20) solver comparison, three seeds per size. “Exact” marks a cut matching the known or brute-force optimum. 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<\!1 ms 5-39 s 2-19 s B.5.6 Additional refinement and scaling results Additional experimental results complement the summary statistics reported in Section 3. Table 7 and Figures 5- 8(a) illustrate how solution quality evolves across refinement stages on t2g20, how quickly the multi-pass schedule saturates, and how the sparse implementation scales on large G-set instances. Table 7: t2g20 (n=400n=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.81.8 points behind. 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 – Figure 5: Progressive improvement on t2g20 (n=400n=400) across the cumulative stage ladder, mean over three seeds. The CMG warm start opens at 0.8320.832; five PPR passes carry it to 0.9520.952; a single closing 2-opt sweep gives the 0.9750.975 headline of Table 7; and the discrete tail (KL, 3-opt, 200200-restart, memetic GA) closes to 0.9940.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=400n=400), L=128L=128, R=32R=32, k=40k=40. Pass 2 yields the largest single gain (+0.014+0.014); the curve is essentially flat from pass 5 onward. Read against Table 9, where quadrupling the restart count buys only +0.004+0.004 in total: it is the multi-pass schedule, not raw restart breadth, that escapes the warm-start basin. B.5.7 Pass and restart saturation Tables 8 and 9 below provide the evidence that the quality of the warm-start basin, not the breadth of random restarts, is what limits the pipeline on t2g20. Table 8 sweeps the pass count at fixed restart budget: pass 2 delivers the largest single gain (+0.014+0.014), the curve then flattens, and five passes capture essentially all achievable gain (0.9520.952), with only a small late bump at pass 9. Table 9 holds the pass count at one and instead quadruples the restart count: going k=40→80→160k=40→ 80→ 160 buys +0.003+0.003 then +0.001+0.001, so a single additional pass is worth roughly five times a doubling of k. Table 8: Pass-count saturation on t2g20 (n=400n=400). L=128L=128, R=32R=32, k=40k=40, EXTENDED penalty, s=0.5s=0.5. Δ is the incremental mean gain over the previous pass. Pass seed 5555 seed 6666 seed 7777 Mean Δ 1 0.9180 0.9352 0.9336 0.9289 – 2 0.9370 0.9510 0.9410 0.9430 +0.0140 3 0.9417 0.9618 0.9410 0.9482 +0.0052 4 0.9417 0.9618 0.9438 0.9491 +0.0009 5 0.9417 0.9677 0.9464 0.9520 +0.0029 6 0.9417 0.9677 0.9464 0.9520 +0.0000 7 0.9417 0.9677 0.9464 0.9520 +0.0000 8 0.9417 0.9677 0.9464 0.9520 +0.0000 9 0.9417 0.9677 0.9516 0.9537 +0.0017 10 0.9417 0.9677 0.9525 0.9540 +0.0003 Table 9: Single-pass high-k restart sweep on t2g20. L=128L=128, R=32R=32, EXTENDED penalty, s=0.5s=0.5. Quadrupling k gains less than one extra pass does in Table 8. k seed 5555 seed 6666 seed 7777 Mean Δ 40 0.9180 0.9352 0.9336 0.9289 – 80 0.9175 0.9475 0.9309 0.9320 +0.003 160 0.9249 0.9424 0.9323 0.9332 +0.001 B.5.8 The full t2g20 stage ladder and 2-opt ordering Table 10 isolates the 2-opt sweep itself. Applied once after five passes (variant A) it raises the mean from 0.9520.952 to 0.9750.975 on only 1212-1919 accepted flips, and the best single seed reaches 0.9840.984 of the exact optimum. Interleaving it after every pass (variant B) instead finds zero improving flips: the solution is already 2-opt-optimal from pass 1 onward, locked into a basin later passes cannot escape, and it finishes at 0.9570.957. Variant C shows how much a single 2-opt sweep is worth: 11-pass ++ 2-opt (0.9620.962) outperforms 55-pass alone (0.9520.952), so one 2-bit sweep recovers more than four extra particle passes. Table 11 orders every configuration by mean ratio, and Table 12 extends the winning one with the discrete tail. Table 10: 2-opt polish on t2g20 (n=400n=400). “Before”/“After” are ratio/OPT around the 2-opt sweep; “Flips” counts accepted 2-opt moves. Experiment Seed Before After Δ Flips A: 5-pass ++ 2-opt 5555 0.9417 0.9664 +0.025 12 6666 0.9677 0.9843 +0.017 19 7777 0.9464 0.9746 +0.028 18 mean 0.9520 0.9751 +0.023 16 B: 2-opt each pass 5555 0.9548 0.9548 0.000 0 6666 0.9700 0.9700 0.000 0 7777 0.9461 0.9461 0.000 0 mean 0.9570 0.9570 0.000 0 C: 1-pass ++ 2-opt 5555 0.9217 0.9637 +0.042 23 6666 0.9498 0.9653 +0.015 13 7777 0.9276 0.9574 +0.030 24 mean 0.9330 0.9621 +0.029 20 GW guarantee 0.878 Table 11: All t2g20 (n=400n=400) configurations, ordered by mean ratio/OPT. “1-pass only” is the single-pass configuration with 2-opt disabled; Table 8’s pass-1 row (0.92890.9289) is the same nominal configuration measured in a separate run and differs by 0.00410.0041; this is a run-to-run variation, not a discrepancy in the underlying method. Configuration Mean Best seed CMG baseline 0.832 – 1-pass only 0.933 0.950 5-pass only 0.952 0.968 B: 2-opt after each pass 0.957 0.970 C: 1-pass ++ 2-opt 0.962 0.965 A: 5-pass ++ 2-opt 0.975 0.984 GW guarantee 0.878 – Table 12: Discrete tail appended to the Experiment A (5-pass PPR ++ 2-opt) partition on t2g20, all three seeds, FULL config (L=128,R=32,k=40L=128,R=32,k=40, RHO_EXTENDED, s=0.5s=0.5). The ++2-opt row reproduces Table 10’s Experiment A exactly (bit-identical RNG stream and draw order), confirming the tail is layered on the genuine headline partition, not an approximation of it. ga_only is the uncontaminated baseline (independent RNG, no CMG or PPR) at the same GA budget; note that it exceeds the full pipeline here, the same finding the heavy-set ablation of Table 13 reports. Stage 5555 6666 7777 Mean vs. headline CMG 0.7915 0.8630 0.8406 0.8317 – 5-pass PPR 0.9417 0.9677 0.9464 0.9520 ==Table 11 ++2-opt (headline) 0.9664 0.9843 0.9746 0.9751 ==Table 10 ++KL 0.9710 0.9843 0.9746 0.9766 +0.0015 ++3-opt 0.9723 0.9888 0.9778 0.9796 +0.0046 ++restart (200) 0.9846 0.9888 0.9836 0.9857 +0.0106 ++GA 0.9876 0.9959 0.9988 0.9941 +0.0190 ga_only (uncontaminated) 0.9971 0.9973 0.9986 0.9977 – B.5.9 Tail ablation on the heavy set, and where the G81 budget goes This block supports the open question: “Once a discrete tail is budgeted, does the warm start still decide the answer?” Table 13 ablates the tail stage by stage across eight instances, and Figure 8 plots it against the ga_only control: a pure-random-seeded GA at the same budget, with no CMG or PPR. On three of eight instances the control beats the full pipeline and on a fourth it ties, which is the isolation finding the body cites. Table 13 reports absolute cuts, so nothing in it depends on an external reference value. Figure 8 normalizes the same measurements by a best-known cut drawn from the literature. Table 15 adds an empirical SDP-relaxation estimate (not a certified upper bound) for the same eight instances. Table 13: Discrete-tail ablation across the heavy set (single core, one shared seed so every row is directly comparable). The base of each row is the CMG warm start → light multi-pass PPR (L=32,R=8,k=20L=32,R=8,k=20, five passes) → 2-opt; subsequent columns append KL, then 200200-restart local search, then the memetic GA, reporting the cut after each. 3-opt runs between KL and the restart stage but is omitted as a column: it finds zero improving moves on seven of the eight instances, and +2+2 units on G22. ga_only is the control: the same memetic GA at the same budget from a pure random seed, with no CMG and no PPR. All cuts are absolute, so the pipeline-versus-control comparison needs no external reference value; bold marks the larger of ++GA and ga_only on each row. tFt_F and ttailt_tail are the PPR and total-tail wall-clock in seconds. The top block is the sparse-signed toroidal target regime; the bottom block is dense uniform-weight contrast. Instance n |E||E| CMG PPR++2-opt ++KL ++rst ++GA ga_only tF/ttailt_F/t_tail Sparse-signed toroidal (target regime) G11 800 1600 418 532 548 560 560 562 133/25 G12 800 1600 414 528 546 550 554 556 163/25 G13 800 1600 416 546 562 578 580 580 165/26 G32 2000 4000 1070 1306 1356 1382 1402 1396 550/128 G33 2000 4000 1012 1298 1328 1358 1368 1362 580/130 G34 2000 4000 1016 1300 1344 1366 1372 1376 631/132 Dense uniform-weight (contrast) G1 800 19176 11300 11541 11541 11571 11621 11617 235/513 G22 2000 19990 12806 13113 13126 13228 13355 13332 1068/305 Figure 8: Cut/best-known† after each tail stage (Table 13), with the uncontaminated ga_only baseline overlaid as red points. Where the red point sits above the green ++GA bar (G11, G12, G34; equal on G13), a pure-random-seeded GA with no CMG or PPR warm start reaches a better final cut than the full pipeline; the visual form of the isolation finding: once the discrete tail is budgeted, the particle solver does not uniformly improve the reported answer. †The denominator here is an external best-known reference, not a proven optimum; its provenance is flagged in the text preceding Table 13. It cancels from the red-versus-green comparison this figure is drawn to make, since both are our own measurements on the same instance. Table 14 asks where the wall clock actually goes on the largest instance. The marginal efficiency column spans five orders of magnitude: the first five stages consume 75.775.7 s, or 1.53%1.53\% of the original budget, and deliver most of the total gain, while the 200200-restart stage spends 27822782 s to buy 3030 cut units: 0.0110.011 cut/s, the least productive stage in the study by three orders of magnitude. Removing it and retuning the remaining stages is what reduces the budget from 49514951 s to 261261 s while improving the cut. Table 14: Per-stage anatomy of G81 (n=20,000n=20,000, |E|=40,000|E|=40,000, optimum 1406014060 (Zick et al., 2026)) before and after retuning. “Δ ” is the gain over the preceding stage; “t” is that stage’s own wall time (obtained by differencing the harness’s cumulative timestamps); “cut/s” is Δcut/t /t, the stage’s marginal efficiency. The original column is an earlier, unretuned configuration: dense all-pairs 2-opt, linear-scan Kernighan-Lin, 200200 random restarts, memetic GA at 150150 generations. The retuned column, CSR-adjacent 2-opt, heap-based KL, no restart stage, GA at 800800 generations, and a perturbation-based iterated local search, is the configuration behind Table 3; “–” marks a stage that configuration does not run, and the retuned 2-opt’s efficiency is omitted because its wall time is at timer resolution. Original (49514951 s) Retuned (261.2261.2 s) Stage cut t (s) cut/s cut t (s) cut/s % opt CMG warm start 10574 0.004 – 10574 0.007 – 75.21% Light PPR (3 passes) 12466 64.37 29.4 12466 64.07 29.5 88.66% 2-opt sweep 12628 4.47 36.3 12626 0.000 – 89.80% Kernighan-Lin 13674 6.19 169.0 13674 0.08 13789.5 97.25% 3-opt ++ KL/3-opt loop 13676 0.70 2.9 13676 0.04 48.8 97.27% Multi-restart (200200) 13706 2781.86 0.011 – – – – Memetic GA 13876 1880.56 0.090 13912 57.50 4.10 98.95% Iterated local search – – – 13922 136.11 0.073 99.02% Burer-Monteiro round 13876 213.10 0.000 13922 3.39 0.000 99.02% Finally, every stage above chases a bigger cut, and none of them says how close that cut is to optimal. Table 15 closes the ablation with a stage that answers the other question: solve the rank-p SDP relaxation max12∑wij(1−⟨vi,vj⟩) 12Σ w_ij(1- v_i,v_j ), ∥vi∥=1 v_i =1, by the Mixing Method (Wang et al., 2017) (coordinate update vi←−gi/∥gi∥v_i←-g_i/ g_i ), round via 200200 GW random hyperplanes, and locally optimize each rounding. At p=⌈2n⌉p= 2n (Boumal et al., 2016) the rank-restricted relaxation is generically free of spurious local minima, but the Mixing Method’s convergence check does not itself verify that condition, so the converged value is an empirical estimate, not a certified upper bound on the true MAX-CUT value (Table 15 and Appendix B.5.11 say more). The resulting gaps, 1010-12%12\% on the sparse-signed instances and 44-6%6\% on the dense contrast pair, are orthogonal to the cut-improvement stages: Burer-Monteiro never beats the GA on cut value, and is not intended to. Table 15: Burer-Monteiro relax-and-reround estimate (rank p=⌈2n⌉p= 2n , 200200 GW hyperplanes, single core). “bound” is the converged value of the Mixing Method’s coordinate updates on the (nonconvex, sphere-constrained) SDP relaxation; since the Mixing Method is not guaranteed to reach the relaxation’s global optimum, this is an empirical estimate, not a certified upper bound on the true MAX-CUT value (Appendix B.5.11’s Karate Club walkthrough reports a small negative gap, which a genuine upper bound cannot produce). gapBM is the empirical gap between that estimate and Burer-Monteiro’s own rounded cut; gapGA is the empirical gap between the estimate and the pipeline’s best reported cut (the ++GA column of Table 13), which is always at least as tight since the GA cut is ≥ BM’s cut on every instance. Both gap columns are measured against an estimate this pipeline computes itself, so like Table 13 they involve no external reference value. Instance bound BM cut GA cut gapBM (%) gapGA (%) tBMt_BM (s) G11 627.7 558 560 11.10 10.78 1.9 G12 622.3 554 554 10.97 10.97 1.9 G13 645.1 578 580 10.40 10.09 1.9 G32 1563.1 1386 1402 11.33 10.31 12.0 G33 1539.5 1360 1368 11.66 11.14 12.1 G34 1541.7 1366 1372 11.39 11.00 11.9 G1 12077.6 11591 11621 4.03 3.78 108.8 G22 14125.8 13283 13355 5.97 5.46 83.1 B.5.10 Biq Mac families: cut quality against wall time Figure 9 is the visual form of body Table 2. Figure 9: The six Biq Mac families of Chen et al. (Chen et al., 2026), ten instances each. Left: cut divided by published optimum, CMG warm start versus the full pipeline; every family reaches 1.0001.000. Right: wall time on a log axis, ours against their vanilla and neural branch-and-bound. The two axes measure different deliverables: our bar is a heuristic cut that matches a published optimum, theirs is a proof of optimality. The time comparison is therefore not a like-for-like ranking of solvers, and is shown because it is the comparison the learned-solver literature sets up. B.5.11 Pipeline Walkthrough Example Figure 13(a) shows the pipeline on Zachary’s Karate Club (Zachary, 1977). The example is illustrative rather than a benchmark: it uses degree-weighted edges to expose structure and does not report a ratio to a published optimum. It shows the mechanical role of each stage: sparsify, coarsen, project a warm start, and run PPR on the finest graph. (a) Pipeline walkthrough on Zachary’s Karate Club. The four panels show the input graph, sparsified graph, CMG grouping, and a PPR solve on the finest graph initialized from the CMG projection. On this small instance, the CMG warm start already reaches the best cut found by the later stages. A Burer-Monteiro (Burer and Monteiro, 2003) relax-and-reround pass gives a converged SDP relaxation estimate of approximately 2587.182587.18, matching the best rounded cut to a gap of about −7.7×10−6-7.7× 10^-6, a negative gap, which demonstrates directly that this estimate is not a certified upper bound (a genuine upper bound cannot fall below a feasible cut); see Table 15. This example is therefore useful mainly as a transparent mechanical walkthrough, not as evidence that every stage adds value on every graph. B.5.12 The continuous-phase optimizer swap in full Table 16 gives the per-instance breakdown for the optimizer swap summarized in Section 3. L-BFGS, Adam, GD, and a level-stochastic variant use the same CMG warm start, restart budget, continuation schedule, and downstream tail. Table 16: Continuous-phase optimizer swap: light PPR solved by L-BFGS (production), Adam, GD, and level-stochastic SGD, each feeding the identical tail (2-opt→ → 3-opt→ 200200-restart→ GA), shared CMG warm start, independently seeded per arm. Columns are cut after the continuous phase alone (pre-tail) and the final cut (post-tail), as a ratio to L-BFGS’s own cut on that instance; last column is GD’s continuous-phase wall clock relative to L-BFGS’s. Two representative rows per regime shown; the max spread row summarizes all eight. Pre-tail (/L-BFGS) Post-tail (/L-BFGS) Instance n Adam GD SGD Adam GD SGD tGD/tLBt_GD/t_LB Sparse-signed toroidal G33 2000 0.938 0.944 1.000 1.003 1.001 1.000 27.5×27.5× G34 2000 0.946 0.942 0.995 0.997 1.000 1.000 29.0×29.0× Dense uniform-weight G1 800 0.987 0.979 0.979 1.000 1.000 1.000 11.8×11.8× G22 2000 0.985 0.981 0.983 0.997 0.997 0.999 15.1×15.1× max spread (8 instances) up to 7.4%7.4\% ≤0.7%≤ 0.7\% 1111–30×30× B.5.13 Internal optimality certificate for G81 The tabu-diversified (Glover, 1986; Glover and Laguna, 1997) tail reaches a cut of 1396213962 on G81, which is 99.3%99.3\% of the externally reported value 1406014060 (Zick et al., 2026). As an internal check, we solved mixed-integer repair problems with HiGHS (Huangfu and Hall, 2018) on every connected residual core of size up to 200200 vertices, covering 4040 cores in total. No improving repair was found. This certifies the reported cut on those residual cores, but it should not be read as an independent proof that the global G81 optimum is 1406014060. Appendix C Pseudocode for every pipeline component Appendix B.4 names the components of the pipeline and shows how they compose. This appendix gives pseudocode for each component in isolation, transcribed from the reference implementation that produced every numerical result reported here, so that the pseudocode and the measured behaviour agree exactly. Two components already have boxes and are not repeated: the continuous solver itself is Algorithm A (Appendix A), and CMG coarsening is Algorithm B.5.4 (Appendix B.5.4). FnProcedure: C.1 Stage 1: Spielman-Srivastava sparsification Algorithm B.5.11 realizes the Spielman-Srivastava leverage-score sampler (Spielman and Srivastava, 2011) of Appendix B.5.3. For n≤500n≤ 500 it computes exact effective resistances via the Laplacian pseudoinverse; for larger n it falls back to the degree-proxy approximation Rij≈1/di+1/djR_ij≈ 1/d_i+1/d_j. It is invoked only when |E|>3n|E|>3n; on the already-sparse toroidal instances that dominate our benchmarks it is a no-op. algorithm2e [htbp!] (b) Spielman-Srivastava effective-resistance sparsification G=(V,E,w)G=(V,E,w); target edge count t G′=(V,E′,w′)G =(V,E ,w ) , t |E|≤t|E|≤ t *no-op ≤500n≤ 500 build Laplacian L from |w||w|; eigendecompose L=QΛQ⊤L=Q Q Rij←∑k:λk>tol(Qik−Qjk)2/λkR_ij← _k: _k>tol(Q_ik-Q_jk)^2/ _k for every edge (i,j)(i,j) *exact resistances di←∑j∼i|wij|d_i← _j i|w_ij| for every vertex Rij←1/di+1/djR_ij← 1/d_i+1/d_j for every edge (i,j)(i,j) *degree-proxy fallback ℓe←|we|Re _e←|w_e|\,R_e for every edge e *leverage score e=(i,j)e=(i,j) pe←min(1,ℓet/∑e′ℓe′)p_e← \! (1,\; _e\,t/ _e _e ) with probability pep_e: keep e with rescaled weight sign(we)|we|/pesign(w_e)\,|w_e|/p_e G′=(V,E′,w′)G =(V,E ,w ) C.2 Stage 3: coarse sweet-spot SQP solve Algorithm B.5.11 is the Burer-Monteiro (Burer and Monteiro, 2003) moment-matrix solve applied at the bottom of the CMG hierarchy, and is used only at a level with nℓ≤20n_ ≤ 20 vertices, where a small dense SLSQP (Kraft, 1988) solve is affordable. Note that here the binary constraint enters as an explicit equality on the moments of Eq. (A.2) (μ(4)−2μ(2)+μ(0)=0μ^(4)-2μ^(2)+μ^(0)=0, i.e. [(x2−1)2]=0E[(x^2-1)^2]=0, which forces each marginal onto ±1\± 1\), rather than through the penalty schedule the larger levels use. Throughout, μi(k),l _i^(k),l denotes the order-k moment entry read off the Gram matrix Ri(l)⊤Ri(l)R_i^(l) R_i^(l) of the rank-restricted factor. algorithm2e [htbp!] (c) Coarse sweet-spot SQP solve (nℓ≤20n_ ≤ 20) coarse graph GℓG_ ; CMG projection x0x_0 ±1± 1 partition on GℓG_ ℓG_ , x0x_0 best←−∞best←-∞ ∈x0,one random ±1drawx_init∈\x_0,\ one random ± 1\ draw\ initialize BM factors Ri(l)∈ℝrank×3R_i^(l) ^rank× 3 at the point mass xinitx_init solve via SLSQP: min−14∑(i,j)∈Ewij(1−∑lμi(1),lμj(1),l) - 14 _(i,j)∈ Ew_ij (1- _l _i^(1),l _j^(1),l ) solve via SLSQP: s.t. ∑lμi(0),l=1 _l _i^(0),l=1, ∑l(μi(4),l−2μi(2),l+μi(0),l)=0 _l( _i^(4),l-2 _i^(2),l+ _i^(0),l)=0 ∀i∀ i x^i←sign(∑lμi(1),l) x_i ( _l _i^(1),l ) for all i x, GℓG_ keep x x if Cut(x^)>bestCut( x)>best best x x found across the two restarts C.3 Stage 4: one particle pass, multi-pass, and 2-opt Algorithm B.5.11 is Algorithm A restricted to a fixed L,R,kL,R,k and packaged for repeated warm-started invocation; it is what Algorithm B.5.11 chains across passes. We keep it as a separate box because the multi-pass driver of Appendix B.5.5 calls it directly rather than through the full solver. Algorithm B.5.11 is the 2-opt (Croes, 1958) closing polish whose ordering matters: applied once at the end it is worth +0.023+0.023 in mean ratio, while applying it after every pass is worse (Appendix B.5.8). algorithm2e [htbp!] (d) One particle pass J; warm start xwarmx_warm; L,R,kL,R,k; sat; ρ1<⋯<ρS _1<·s< _S cut found and the corresponding partition x x , xwarmx_warm, L,R,kL,R,k, sat, ρ1<⋯<ρS _1<·s< _S (identical body to Algorithm A’s restart loop, warm-started from xwarmx_warm) cut found, and the corresponding partition x x algorithm2e [htbp!] (e) Multi-pass restarts J; initial partition x0x_0; edges; weights; number of passes cut and its partition , x0x_0, edges, weights, passes xwarm←x0x_warm← x_0; best←−∞best←-∞ =1,…,passesp=1,…,passes (c,x^)←(c, x)← , xwarmx_warm, … >bestc>best best←cbest← c; xwarm←x^x_warm← x *chain the best binary forward , xwarmx_warm algorithm2e [htbp!] (f) 2-opt sweep partition x; G=(V,E,w)G=(V,E,w) of accepted double-flips , G gi←∑j∼iwijxjg_i← _j iw_ijx_j for all i improvedimproved improved←falseimproved =1,…,ni=1,…,n =i+1,…,nj=i+1,…,n Δ←2xigi+2xjgj−4wijxixj ← 2x_ig_i+2x_jg_j-4w_ijx_ix_j Δ>10−10 >10^-10 update g for neighbors of i and of j; flip xi←−xix_i←-x_i, xj←−xjx_j←-x_j improved←trueimproved of accepted double-flips C.4 Stage 5 (optional discrete tail): Kernighan-Lin and 3-opt Algorithms B.5.11 (Kernighan-Lin (Kernighan and Lin, 1970)) and B.5.11 (3-opt (Lin and Kernighan, 1973)) are the first two tail stages ablated in Appendix B.5.9; both are monotone (neither ever decreases the cut) and neither is part of the headline light pipeline. KL is the stage that does the bulk of the tail’s work, which is why the endpoint is set by the search operator rather than by the starting partition. algorithm2e [htbp!] (g) Kernighan-Lin variable-depth exchange partition x; G cut improvement , G total←0total← 0 _cum≤10−9best\_cum≤ 10^-9 gi←∑j∼iwijxjg_i← _j iw_ijx_j for all i; unlock all vertices cum←0cum← 0; best_cum←0best\_cum← 0; best_k←0best\_k← 0; moves←[]moves←[\,] =1,…,n=1,…,n v←argmaxvunlockedxvgvv← _v\ unlockedx_vg_v; break if none unlocked cum←cum+xvgvcum +x_vg_v; update g for neighbors of v under xv→−xvx_v→-x_v flip xv←−xvx_v←-x_v; lock v; append v to movesmoves >best_cumcum>best\_cum best_cum←cumbest\_cum ; best_k←|moves|best\_k←|moves| undo every move in movesmoves after index best_kbest\_k *keep only the best prefix _cum>10−9best\_cum>10^-9total←total+best_cumtotal +best\_cum algorithm2e [htbp!] (h) Connected-triple 3-opt partition x; G cut improvement , G gi←∑j∼iwijxjg_i← _j iw_ijx_j for all i; total←0total← 0 improvedimproved improved←falseimproved (a,b)(a,b), a<ba<b Δab←xaga+xbgb−2wabxaxb _ab← x_ag_a+x_bg_b-2w_abx_ax_b *pair-flip ΔCut Δab>10−9 _ab>10^-9 flip a,b\a,b\, update g; total←total+Δabtotal + _ab; improved←trueimproved ; continue adjacent to a or b, c∉a,bc∉\a,b\ S←a,b,cS←\a,b,c\; ΔS←∑v∈Sxvgv−2∑(u,v)∈E∩Swuvxuxv _S← _v∈ Sx_vg_v-2 _(u,v)∈ E∩ Sw_uvx_ux_v ΔS>10−9 _S>10^-9 flip S, update g; total←total+ΔStotal + _S; improved←trueimproved ; break C.5 Stage 5 (optional discrete tail): local optimum, memetic GA, and Burer-Monteiro Algorithm B.5.11 drives a partition to a joint 2-opt (Croes, 1958)/Kernighan-Lin (Kernighan and Lin, 1970)/3-opt (Lin and Kernighan, 1973) local optimum; it is the polish step used both by the multi-restart diagnostic and, inside Algorithm B.5.11, to evaluate every population member and every child. Algorithm B.5.11 is the memetic genetic algorithm (Moscato and Cotta, 2003), using the Chu-Beasley (Chu and Beasley, 1998) steady-state replacement scheme, whose ga_only control appears in Appendix B.5.9, and Algorithm B.5.11 is the Burer-Monteiro (Burer and Monteiro, 2003) relax-and-reround pass, computed via the Mixing Method (Wang et al., 2017), that produces the empirical SDP-relaxation estimate of Table 15. Its default rank ⌈2n⌉ 2n is the threshold above which the rank-restricted problem is generically free of spurious local minima (Boumal et al., 2016), but the Mixing Method’s convergence check (a tolerance on successive objective values) does not itself verify that condition, so the resulting estimate is not a certified bound; Appendix B.5.11’s Karate Club walkthrough gives a direct, concrete negative-gap counterexample. algorithm2e [htbp!] (i) Joint 2-opt/KL/3-opt local optimum partition x; G at a joint 2-opt/KL/3-opt local optimum (modified in place) , G , G =1,…,50it=1,…,50 a←a← , G; b←b← , G +b<10−9a+b<10^-9break algorithm2e [htbp!] (j) Memetic GA (Chu-Beasley steady-state, agreement crossover) G; population size poppop; generations gensgens population member and its cut , poppop, gensgens =1,…,popi=1,…,pop Pi←P_i← random ±1± 1; _i, G; fiti←Cut(Pi)fit_i (P_i) =1,…,gensgen=1,…,gens p1,p2←p_1,p_2← two distinct binary-tournament winners from P align Pp2P_p_2 to Pp1P_p_1 by global sign (maximize agreement) childi←Pp1,ichild_i← P_p_1,i where they agree; a random ±1± 1 coin flip where they disagree , G; cf←Cut(child)c_f (child) population member has |fit−cf|<0.5|fit-c_f|<0.5 duplicate-cut children w←argminifitiw← _ifit_i >fitwc_f>fit_w Pw←childP_w ; fitw←cffit_w← c_f *steady-state replace-worst maxifiti _ifit_i and its cut algorithm2e [htbp!] (k) Burer-Monteiro relax-and-reround (Mixing Method) G; rank p; number of hyperplanes h (bound,best)(bound,best), whose difference is an empirical, not certified, optimality gap , p, h ≤0p≤ 0p←⌈2n⌉p← 2n *default rank Vi←V_i← random unit vector in ℝpR^p for all i |objprev−obj|<tol⋅(1+|obj|)|obj_prev-obj|<tol·(1+|obj|) =1,…,ni=1,…,n gi←∑j∼iwijVjg_i← _j iw_ijV_j; Vi←−gi/∥gi∥V_i←-g_i/ g_i *anti-align (coordinate update) obj←12(W−∑(i,j)∈Ewij⟨Vi,Vj⟩)obj← 12 (W- _(i,j)∈ Ew_ij V_i,V_j ) bound←objbound ; best←−∞best←-∞ ′=1,…,h =1,…,h draw random hyperplane r∼(0,Ip)r (0,I_p); xi←sign(⟨Vi,r⟩)x_i ( V_i,r ) for all i , G; keep x if Cut(x)>bestCut(x)>best (bound,best)(bound,best) *bound−bestbound-best is an empirical, not certified, gap (a) Sparse scaling on six G-set instances, n=5000n=5000-20,00020,000 (a superset of the four shown in Table 3, which omits G65 and G66). Memory savings grow linearly with n, exceeding 3300×3300× at n=20,000n=20,000. The right-hand panel shows the gain over the CMG warm start at both pipeline stages: the continuous-relaxation path alone (CMG→ → 2-opt, blue) holds a tight 1.1941.194-1.212×1.212× band, and appending the discrete tail (KL/3-opt/GA/ILS, red) carries this to 1.3161.316-1.331×1.331×; 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.01.0, the no-gain line, so that the flatness of the bands is not exaggerated by a magnified scale.