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

Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?
Mar 2, 2026Semih Cantürk, Thomas Sabourin, Frederik Wenkel +2Neural Combinatorial Optimization Transfer Learning
Dept. of Computer Science and Operations Research, Université de Montréal · Mila – Quebec AI Institute · Dept. of Mathematics & Statistics, Université de Montréal +2
Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
May 8, 2026Hao Chen, Chendi Qian, Christopher Morris +2Max-Cut Semidefinite Programming
1Davidson School of Chemical Engineering, Purdue University · Faculty of Computer Science, RWTH Aachen University · 3Jacobs Technion-Cornell Institute, Cornell Tech
Zero-Shot Size Transfer for Neural ODEs on Sparse Random Graphs: Graphon Limits and Adjoint Convergence
Jun 25, 2026Mingsong Yan, Zhida Wang, Sui TangGraphon Theory OOD Generalization
Department of Mathematics, University of California, Santa Barbara, CA.

Mar 2, 2026J/K move · Enter open · S save

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

Semih Cantürk, Thomas Sabourin, Frederik Wenkel, Michael Perlmutter+1

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

Open paper AskPDF arXiv

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.

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