Many hard graph problems, such as splitting a graph's nodes into two groups so that as many edges as possible cross between them (Max-Cut), can be rewritten as smooth energies over real-valued node variables. In a tight continuous relaxation, the smooth energy is shaped so that its minima sit exactly on the discrete ±1 corners and nowhere in between. Debraj Banerjee et al. (MiP-CRIM) add a quartic "attractor" polynomial to the spin energy and prove a landscape-equivalence theorem: every local minimum of the smooth energy is a discrete configuration that no single node flip can improve, and every such configuration is a smooth local minimum. Tightness does not escape NP-hardness, though. Which corner you reach depends entirely on where descent starts and how it travels. MiP-CRIM handles this with Adam steps plus random basin-hopping.
We propose to learn the journey. The solver is a graph neural ordinary differential equation, a network whose node states evolve continuously in time under a learned velocity field. It is conditioned on the problem instance, and a fixed time schedule hands its steering over to the exact gradient of the tight energy. The final phase is pure gradient flow on a minima-preserving landscape, so every output is a genuine discrete, one-flip-optimal configuration with no rounding. More importantly, the energy at the end of the trajectory equals the true discrete objective of the configuration the solver actually returns. That makes the discrete objective a differentiable training signal for the entire trajectory, early exploration included. Existing learned solvers train a predictor on a relaxed or expected objective and then run local search that the predictor never sees. We train the predictor for where local descent will actually land.
Core Claim
Let $H(x)$ be the Ising energy of an instance with node variables $x \in \mathbb{R}^n$, and let $E(x) = H(x) + A(x)$ be its MiP-CRIM relaxation, where $A$ is the quartic attractor. We define the solver's dynamics as
$$\frac{dx}{dt} = (1 - g(t))\, F_\theta(x, t; G) - g(t)\, \nabla E(x), \qquad t \in [0, T],$$
where $F_\theta$ is a graph neural ODE field in the style of Michael Poli et al., $G$ is the instance graph, and $g$ is a fixed ramp that rises from 0 to 1 and reaches 1 at a time $\tau < T$. On $[\tau, T]$ the flow is exact gradient descent on $E$. By landscape equivalence, its limit points are therefore discrete one-flip local minima. This holds however badly $F_\theta$ behaves, because the learned field only chooses which basin the state is in at time $\tau$.
The training loss is $\mathbb{E}_G[E(x(T))]$, averaged over a distribution of instances and backpropagated with the adjoint method of Ricky T. Q. Chen et al.. We state the claim to be tested plainly. Under an equal compute budget, training through the tight tail finds better basins than two alternatives: training the same network on the relaxed objective and appending the same descent afterwards, or running the exact descent from random starts.
There is a known obstacle, and we treat it as a research question rather than hiding it. As $T \to \infty$, the map from $x(\tau)$ to $x(T)$ becomes piecewise constant, one constant value per basin, so gradients vanish except near basin boundaries. We therefore keep $T$ finite and measure how informative the gradient remains as a function of $T - \tau$. At finite horizon the state near the boundary between two basins still responds to perturbations, and that response is exactly the "which basin" signal we want.
Relation to Prior Work
The tightness side of the design comes from three sources. MiP-CRIM supplies the energy and the theorem the design depends on, but it optimizes with discrete Adam steps and noise and learns nothing across instances. Yuma Ichikawa (Continuous Relaxation Annealing, CRA) motivates the explore-then-commit schedule. CRA starts with a convexifying penalty and anneals toward a corner-forcing one, which rescues physics-inspired graph neural networks (PI-GNNs) that otherwise collapse to the all-zero solution on dense graphs. That annealing happens over training epochs of a per-instance network. Here it happens inside one forward integration of a model shared across instances, and the gradient flows through the schedule. Sara Venturini et al. motivate rounding-free training. Their exact concave penalty beats top-$k$ rounding on data distillation (root mean squared error 20.87 vs 24.00 on BlogFeedback), which suggests that optimizing the quantity you will actually output matters.
ROS is the closest learned competitor. It trains a graph neural network over probability simplices, and its objective equals the expected cut under random sampling. It optimizes an average over sampled outputs. We optimize the value of the single deterministic output after local descent.
On the continuous-time side, graph neural ODEs have been used only for classification and forecasting Michael Poli et al., never for optimization. CHyLL++ addresses the tension between smooth flows and discrete jumps by embedding them in higher dimensions. We sidestep that tension instead: over a finite time a smooth flow can squeeze whole regions toward isolated corners, and the tight energy supplies those corners. The late phase is stiff, because trajectories lock onto corners quickly, so we use implicit integration following Proximal Implicit ODE Solvers for the tail.
Research Program
We will build the solver for problems expressible as Ising energies: Max-Cut, maximum independent set (MIS) via its penalized Ising form, and number partitioning. MiP-CRIM covers all three, so the same attractor applies throughout.
The program has three parts. First, an analysis of the tail. We will characterize the gradient of $E(x(T))$ with respect to $x(\tau)$ as a function of the horizon. The aim is to show that it concentrates on states near saddles, and to find a horizon that keeps it usable. We will measure gradient norms and signal-to-noise ratio empirically across horizons.
Second, amortized training. The model is trained once on small random regular and Erdős–Rényi graphs and then evaluated on larger instances without retraining.
Third, cost. At test time we will report the number of function evaluations and wall-clock time. The standard objection to neural ODEs is their training cost, and at inference the relevant comparison is against restart budgets, not against a single Adam run.
Baselines
The naive reference is pure tight descent from random starts: our own dynamics with $F_\theta \equiv 0$. This is MiP-CRIM's continuous-time limit. It is run with as many random restarts as fit in the proposal's wall-clock budget on the same GPU. It isolates whether learning adds anything at all.
The strongest existing method on dense Ising-type instances is MiP-CRIM itself Debraj Banerjee et al.: Adam with basin-hopping, with its attractor parameters tuned using the same number of trials we spend tuning our schedule. The file reports that it reaches a synchronization score of 1.0 (every output is already discrete) and the best cut among tested solvers on a dense 2000-node instance, but gives no exact cut value. On number partitioning it reports a partition discriminant of 0.0015 against D-Wave's 0.00957. Beating it means a higher Gset cut, or a lower partitioning discriminant, at matched wall-clock.
We also compare against CRA-PI-GNN Yuma Ichikawa on dense random-regular MIS. There plain PI-GNN reaches an independent-set density of 0.000 for degree above 16. The file gives no CRA numerical value, so we will rerun it. We further compare against ROS ROS, which runs 20,000-node instances in a few seconds; the file reports no Gset cut value for it, so we will rerun it at matched time.
The key ablation is the decoupled model. It uses the identical $F_\theta$ architecture, trained on $E(x(\tau))$ (the relaxed objective at the handoff time), followed by the same exact tail at test time. It differs from the full method only in whether gradients pass through the descent phase.
All methods share the same training-graph distribution, the same test instances, and the same hyperparameter-search budget.
Why not just…?
Why not just run Adam on MiP-CRIM with more restarts? This is the most serious threat. Random restarts on a minima-preserving landscape already guarantee discrete, one-flip-optimal outputs, and each run is cheap. Our only advantage can be better basin selection per unit of compute. The $F_\theta \equiv 0$ and MiP-CRIM baselines at matched wall-clock settle this directly. If they match us on Gset, the learned field is not worth its cost, and we will report that result.
Why not just train a graph neural network and then apply greedy one-flip local search? This achieves the same one-flip guarantee without any ODE machinery. The difference is that the network never learns about the search that follows it. The decoupled ablation is exactly this comparison with everything else held fixed. If coupled training shows no advantage over it, the central claim is false.
Why not use per-instance learned solvers like CRA-PI-GNN or ROS? They optimize each instance separately (CRA) or optimize an expectation over sampled outputs (ROS). Neither trains on the realized value of a deterministic output. We will compare them head-to-head at matched time. ROS's speed means it may win on very large sparse graphs, and we will report where the crossover occurs.
Why not Frank-Wolfe, a method that avoids expensive projections by solving a linear subproblem each step? For densest-$k$-subgraph, Qiheng Lu et al. show that each step reduces to a partial sort and scales to com-Orkut. We therefore leave densest-$k$-subgraph out of scope. For quartic Ising energies no such cheap linear step is available.
Proposed Experiments
For Max-Cut we use Gset, reporting the cut value and the gap to the best-known values from our own reruns (the file reports no Gset cut numbers). For MIS we use random regular graphs across a sweep of degrees, reporting independent-set density with emphasis on degree above 16. For number partitioning we report the partition discriminant. For every method we also report the synchronization score, wall-clock time, and number of function evaluations.
Two checks decide the outcome. The first is the coupled-versus-decoupled gap at matched compute. The second is whether the full method beats restart-matched MiP-CRIM on out-of-distribution Gset graphs. A supporting diagnostic plots gradient signal-to-noise against the tail horizon $T-\tau$ and against final quality. If the method helps, the benefit should peak at intermediate horizons and vanish both as the horizon goes to zero, where there is no tight tail to train through, and as it becomes very long, where the gradient flattens.
References
- Local-Minima-Preserving Polynomial Relaxation of Ising Problems
- Graph Neural Ordinary Differential Equations
- Neural Ordinary Differential Equations
- Controlling Continuous Relaxation for Combinatorial Optimization
- Relax and penalize: a new bilevel approach to mixed-binary hyperparameter optimization
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems
- Embedding Hybrid Systems into Continuous Latent Vector Fields
- Proximal Implicit ODE Solvers for Accelerating Learning Neural ODEs
- Densest k-Subgraph Mining via a Provably Tight Relaxation