{"id":"arxiv/2605.07113","url":"https://arxiv.org/abs/2605.07113","tags":["cs.LG","math.OC"],"score":0,"title":"Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks","domain":"cs.LG","source":"arxiv","authors":["Hao Chen","Chendi Qian","Christopher Morris","Andrea Lodi","Can Li"],"reviews":0,"subject":"cs.LG","summary":"Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm can be prohibitively expensive. Hence, we consider this challenge for Max-Cut, where branch and bound commonly uses semidefinite programming (SDP) relaxations to bound subproblems. We propose a Max-Cut-specific graph neural network that serves as a principled, lightweight neural proxy for these SDP solvers and can be plugged directly into an exact branch-and-bound framework. The proposed architecture has update…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-08","reactions":{}}