On Sparse Graph Limits for Neural Combinatorial Optimization

Thien Le; Melanie Weber

cs.LGOct 31, 2026

On Sparse Graph Limits for Neural Combinatorial Optimization

Authors: Thien Le, Melanie Weber

Organizations: SEAS, Harvard University, Cambridge, MA

Abstract

Graph neural networks are often trained on small graphs and deployed on larger ones, raising the question of which graph information must be preserved for combinatorial optimization values to transfer across sizes. We establish size-transfer guarantees for normalized graph optimization values using finite collections of energy features. For affine objectives, including MAX-CUT, coloring defect, and independent-set density, differences in task value are controlled by discrepancies in normalized scalar energy probes on all bounded-degree graphs. For general Lipschitz objectives, such as those with balance penalties, an additional representation error appears; this error vanishes on hyperfinite graph families but can remain bounded away from zero on expanders. Thus, at fixed degree bound, state space, Lipschitz constant, and target accuracy, a finite energy representation independent of graph size suffices universally for affine tasks and asymptotically for general Lipschitz tasks on hyperfinite families. These results yield prediction guarantees under explicit conditions on encoder accuracy, readout stability, and representation coverage, together with statistical generalization bounds. Theoretically, we prove Shapley-Folkman bounds with sharp parameter dependence, including a dimension-free $\ell_2$ regime, and realize the resulting energy features with a fixed-weight message-passing network using random node initialization on bounded-treewidth graphs. Experiments with exact solvers and trained models test the resulting transfer guarantees.

Figures & tables

Panel of Figure 1 — Figure 1: Hyperfinite decomposition and convexification. In a hyperfinite family, with $n:=|V(G)|$ , deleting $E_{\rm cut}$ , $|E_{\rm cut}|\leq\varepsilon n$ , leaves components $C_{1},\ldots,C_{m}$ with $|C_{j}|\leq K(\varepsilon)$ and $K$ independent of $n$ . Independent component assignments make $\mathcal{S}_{q}(G-E_{\rm cut})$ a vertex-weighted Minkowski sum (dots); Shapley–Folkman bounds its gap $\kappa_{q,s}$ to the shaded convex hull.

Task class	Graph assumption	Bound on $\|T_{F}(G)-T_{F}(H)\|$
Affine: MAX-CUT, coloring defect, independent-set density	Any $D$ -bounded $G,H$	$L_{s}\eta_{q,s}(G,H)$
General $L_{s}$ -Lipschitz, including finite balance penalties	Any $D$ -bounded $G,H$	$L_{s}[\eta_{q,s}+\kappa_{q,s}(G)+\kappa_{q,s}(H)]$
Same general class, $s=1$	Both graphs admit such decompositions	$L_{1}[\eta_{q,1}+\rho_{1}(G)+\rho_{1}(H)]$
Same general class, $s=2$	Same	$L_{2}[\eta_{q,2}+\rho_{2}(G)+\rho_{2}(H)]$

Table 1: Task-value transfer by regime. Here

D

is the maximum-degree bound;

T_{F}(X):=\operatorname{opt}_{z\in\mathcal{S}_{q}(X)}F(z)

, where

\operatorname{opt}

is the task’s minimum or maximum;

L_{s}

is the Lipschitz constant under the

\ell^{s}

quotient metric;

\eta_{q,s}

is the

\ell^{s}

-Hausdorff distance between the convexified sets;

\kappa_{q,s}(X)

is the set-to-hull distance; and

n_{X}:=|V(X)|

. Under an

(\varepsilon_{X},K_{X})

decomposition,

\rho_{1}=O_{D}(\varepsilon_{X}+q^{2}K_{X}/n_{X})

and

\rho_{2}=O_{D}(\varepsilon_{X}+\min\{qK_{X}/n_{X},\sqrt{K_{X}/n_{X}}\})

. Note that the regime

\sqrt{K_{X}/n_{X}}

is independent of

q

Panel of Figure 2 — Figure 2: The fundamental objects on a worked example (exact rational coordinates). (a) An assignment $c=(1,1,2,1,2)$ on $C_{5}$ . (b) Its $q$ -quotient $G/c=(p,W)$ (Definition 1 ). (c) The quotient set $\mathcal{S}_{2}(C_{5})$ in the $(p_{1},W_{12})$ -projection, $G/c$ circled. (d) Partition convergence: $\circ$ marks $\mathcal{S}_{2}(C_{10})$ , $\cdot$ marks $\mathcal{S}_{2}(C_{30})$ ; the denser grid approaches the shaded limiting region (exact formula: Appendix C.1 ).

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: The $(p_{1},W_{12})$ -projection of $\mathcal{S}_{2}(mK_{4})$ (dots, exact) inside $\operatorname{conv}\mathcal{S}_{2}(K_{4})$ (shaded): the $m$ -fold Minkowski average fills the hull at rate $\Theta(K/n)=\Theta(1/m)$ (Theorem 5 and Remark 7 ).

Panel of Figure 4 — Figure 4: The feature blind spot, in the $(p_{1},W_{12})$ -projection with exact coordinates. (a) $\mathcal{S}_{2}(K_{4})$ (dots) and its convex hull (shaded); the balanced zero-cut target $(p_{1},W_{12})=(\frac{1}{2},0)$ ( $\star$ ) lies in the hull—as the midpoint of the two monochromatic quotients—but not in the set, and $\Phi(K_{4})=\frac{1}{2}$ . (b) $\mathcal{S}_{2}(K_{4}\sqcup K_{4})$ (dots): the hull is identical to (a), so every probe energy agrees on the two graphs, yet the set now contains $(\frac{1}{2},0)$ (circled; color one copy state $1$ , the other state $2$ ), and $\Phi(K_{4}\sqcup K_{4})=0$ . Energy features see only the shaded region and cannot distinguish (a) from (b); the balanced-cut task lives in the difference between dots and shade.

Neural Combinatorial Optimization

Neural combinatorial optimization uses neural networks to find high-quality solutions to discrete problems such as routing, scheduling, and graph partitioning.

See all 141 papers

Mar 2, 2026

Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?

A key challenge in developing unified neural solvers for combinatorial optimization (CO) is the efficient generalization of models from a given set of tasks to new tasks unseen during initial training. To address this, we first establish a new GNN encoder, which uses a GCON module as a form of expressive message passing together with energy-based unsupervised loss functions. This model achieves highly competitive performance across multiple CO tasks when trained individually on each task. We then leverage knowledge from the computational reducibility literature to propose pretraining and fine-tuning strategies that transfer effectively (a) between MVC, MIS and MaxClique, and (b) in a multi-task learning setting that additionally incorporates MaxCut, MDS and graph coloring. Additionally, in a leave-one-out, multi-task learning setting, we observe that pretraining on all but one task almost always leads to faster convergence on the remaining task when fine-tuning, while avoiding negative transfer. Our findings indicate that learning common representations across multiple graph CO problems is viable through the use of expressive message passing coupled with pretraining strategies that are informed by the polynomial reducibility literature, thereby taking an important step towards enabling the development of foundational models for neural CO. We provide an open source implementation of our work at https://github.com/semihcanturk/COPT-MT.

Semih Cantürk, Thomas Sabourin, Frederik Wenkel +2

Dept. of Computer Science and Operations Research, Université de Montréal · Mila – Quebec AI Institute · Dept. of Mathematics & Statistics, Université de Montréal +2

Neural Combinatorial Optimization Transfer Learning Graph Neural Networks Multi-Task Optimization

Ask PDF

May 8, 2026

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

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

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

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

10.6 \times

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

Hao Chen, Chendi Qian, Christopher Morris +2

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

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

Ask PDF

Jun 25, 2026

Zero-Shot Size Transfer for Neural ODEs on Sparse Random Graphs: Graphon Limits and Adjoint Convergence

Graph Neural Differential Equations (GNDEs) model continuous-time graph dynamics by parameterizing Neural ODE velocity fields with Graph Neural Networks. Their local, size-independent filters suggest a zero-shot size-transfer principle: train on a small graph and deploy on larger, similar graphs without retraining. We develop a quantitative theory for this principle on sparse random graphs sampled from graphons. We consider Graphon Neural Differential Equations (Graphon-NDEs) and adjoint Graphon-NDEs as the infinite-node limits of the forward and adjoint GNDE systems, and establish well-posedness. For an

n

-node random graph with sparsity parameter

α_n

, we prove trajectory-wise convergence of GNDE solutions to Graphon-NDE solutions at rate

O((α_n n)^{-1/2})

, up to logarithmic factors, with high probability. We also establish uniform-in-time convergence bounds for adjoint systems governing hidden-state and parameter gradients. We further study discretize-then-optimize (DTO) and optimize-then-discretize (OTD) training. Under explicit Euler discretization with

M

steps, we show that DTO and OTD are asymptotically consistent, with hidden-state and local parameter-gradient discrepancies of orders

O(1/M)

and

O(1/M^2)

, respectively, up to sparsity and logarithmic factors. Experiments on HSBM and tent graphons support the theoretical rates, while zero-shot transfer experiments across four graphon classes demonstrate accurate deployment of learned GNDEs on larger independently sampled graphs.

Mingsong Yan, Zhida Wang, Sui Tang

Department of Mathematics, University of California, Santa Barbara, CA.

Graphon Theory OOD Generalization Neural ODEs

Ask PDF

Abstract

Neural Combinatorial Optimization

Explore similar work

Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?

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

Zero-Shot Size Transfer for Neural ODEs on Sparse Random Graphs: Graphon Limits and Adjoint Convergence