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

Semih Cantürk; Thomas Sabourin; Frederik Wenkel; Michael Perlmutter; Guy Wolf

cs.LGMar 2, 2026

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

Authors: Semih Cantürk, Thomas Sabourin, Frederik Wenkel, Michael Perlmutter, Guy Wolf

Organizations: Dept. of Computer Science and Operations Research, Université de Montréal · Mila – Quebec AI Institute · Dept. of Mathematics & Statistics, Université de Montréal · Valence Labs · Dept. of Mathematics, Boise State University

Abstract

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.

Figures & tables

Figure 1: (Left) Reduction between tasks for pairwise transferability section: MIS/MVC are complements, but MaxClique is based on an auxiliary graph. (Right) Multi-task learning / fine-tuning architecture (pretraining set in green, fine-tuning set in purple).

CO Problem	Objective: $\min_{X\in\{0,1\}^{N}}H(X)$
MIS	$H(X)=-A\sum_{i=1}^{N}X_{i}+B\sum_{(i,j)\in\mathcal{E}}X_{i}\cdot X_{j}$
MDS	$H(X)=A\sum_{i=1}^{N}X_{i}+B\sum_{i=1}^{N}\left(1-X_{i}\right)\prod_{j\in\mathcal{N}(j)}\left(1-X_{j}\right)$
MaxClique	$H(X)=-A\sum_{i=1}^{N}X_{i}+B\sum_{(i,j)\notin\mathcal{E}}X_{i}\cdot X_{j}$
MaxCut	$H(\sigma)=-\sum_{(i,j)\in\mathcal{E}}\frac{1-\sigma_{i}\sigma_{j}}{2}\quad$ where $\sigma_{i}=2X_{i}-1$
MVC	$H(X)=A\sum_{i=1}^{N}X_{i}+B\sum_{(i,j)\in\mathcal{E}}\left(1-X_{i}\right)\cdot\left(1-X_{j}\right)$
$K$ -Coloring	$H(X)=\sum_{i=1}^{N}(1-\sum_{k=1}^{K}X_{i,k})^{2}+\sum_{(i,j)\in\mathcal{E}}\sum_{k=1}^{K}X_{i,k}X_{j,k}$

Table 1: Energy-based loss functions for CO problems considered. Table extended from Sanokowski et al. (2024) .

Method	Type	MVC $\downarrow$	MClique $\uparrow$	MIS $\uparrow$
True Size	—	206.95	19.07	20.07
GUROBI	OR	—	† 19.05 †	† 19.98 †
GFN	SSL	—	16.24	19.18
GCN	SSL-GNN	221.56 $\pm$ 0.05	15.33 $\pm$ 0.04	17.67 $\pm$ 0.20
GIN	SSL-GNN	221.63 $\pm$ 0.23	15.28 $\pm$ 0.14	17.50 $\pm$ 0.04
GATv2	SSL-GNN	220.76 $\pm$ 2.26	15.56 $\pm$ 0.09	17.58 $\pm$ 0.07

Table 2: Performance comparison of GCON with other baselines on RB-small datasets (Mean

\pm

Std). The best deep learning-based method is listed in gold , second best in silver . † indicates Gurobi outperforms all deep learning methods.

GNN	Out-head	MIS $\uparrow$	MVC $\downarrow$
Baseline		18.12 $\pm$ 0.11	211.69 $\pm$ 0.16
Freeze	Reset + FT	17.68 $\pm$ 0.04	212.46 $\pm$ 0.25
Freeze	Invert + FT	17.69 $\pm$ 0.05	212.39 $\pm$ 0.21
FT	Invert + FT	18.00 $\pm$ 0.05	211.56 $\pm$ 0.24

Table 3: MIS

\leftrightarrow

MVC transferability on RB-small . Baseline refers to models trained from scratch on the CO task tested on. Other models are pretrained on the opposite task, e.g., the MIS column evaluates models pretrained on MVC and fine-tuned on MIS.

#	Feats	GNN Stack	GT	Comp?	MC Size
1	$G$	Baseline	—	False	16.92 $\pm$ 0.13
2	$G\\|\bar{G}$	Baseline	—	False	16.63 $\pm$ 0.05
3	$G$	Random	—	False	10.71 $\pm$ 0.14
4	$G$	Frozen	—	False	16.12 $\pm$ 0.20
5	$G$	Fine-tuned	—	False	16.55 $\pm$ 0.03
6	$G\\|\bar{G}$	Frozen	—	False	15.98 $\pm$ 0.12

Table 4: Overview of MIS

\rightarrow

MaxClique transferability experiments on RB-small . First two rows represent baselines trained from scratch. The “feats” column denotes whether graph statistics from only the original graph

G

or also its complement

\bar{G}

are provided as initial node features. Third row represents a randomly initialized GCON model. Mean

\pm

standard dev for 3 runs reported. Top 3 transfer runs are denoted with gold , silver and bronze .

Figure 2: Transfer performance on MVC and MIS. We compare training from scratch against frozen and unfrozen fine-tuning on the other task (MVC on MIS and MIS on MVC), the rest of tasks (MCut, MClique, MDS, $K$ -coloring), and all tasks (rest + other) for BA-small graphs.

Task	From Scratch	Fine-tuned
$\uparrow$ MaxCut	716.81 $\pm$ 3.00	722.40 $\pm$ 1.17
$\uparrow$ MaxClique	00 4.31 $\pm$ 0.01	00 4.32 $\pm$ 0.01
$\downarrow$ MDS	0 35.57 $\pm$ 2.41	0 36.15 $\pm$ 1.87
$\uparrow$ MIS	111.33 $\pm$ 0.20	111.56 $\pm$ 0.10
$\downarrow$ MVC	141.30 $\pm$ 0.27	140.04 $\pm$ 0.33
$\downarrow$ Color	00 61.92 $\pm$ 36.11	0 24.19 $\pm$ 9.08

Table 5: Leave-one-out fine-tuning in low-resource regime on BA-small graphs (20 epochs, unfrozen backbone, 5 runs average)

MaxCut	MaxClique	MIS	MVC	Color
33.36	41.34	41.40	34.68	45.29

Table 6: MDS (

\downarrow

) trained together with all but one task on BA-small graphs for 200 epochs (5 runs average)

Task	Fine-tuned	Baseline	Full
$\uparrow$ MaxCut	722.77 $\pm$ 1.00	716.90 $\pm$ 1.55	726.58 $\pm$ 0.51
$\uparrow$ MaxClique	00 4.32 $\pm$ 0.01	00 4.31 $\pm$ 0.00	00 4.43 $\pm$ 0.02
$\downarrow$ MDS	0 29.65 $\pm$ 0.09	0 33.93 $\pm$ 1.15	0 29.56 $\pm$ 0.22
$\uparrow$ MIS	111.94 $\pm$ 0.06	111.33 $\pm$ 0.26	112.23 $\pm$ 0.06
$\downarrow$ MVC	139.70 $\pm$ 0.31	141.43 $\pm$ 0.23	139.40 $\pm$ 0.20
$\downarrow$ Coloring	0 17.29 $\pm$ 1.97	00 49.04 $\pm$ 21.84	00 3.52 $\pm$ 1.52

Table 7: Fine-tuning on MDS-MIS-Coloring pretrained backbones for 20 epochs ( BA-small dataset, 3 runs average)

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Value
Architecture Details
Number of GCON Layers	16
Hidden Dimension ( $d_{h}$ )	64
Channels (Filters)	[0], [1], [2], [4], [0,1], [1,2], [2,4]
Aggregation	Sum
Dropout Rate	0.3

Appendix

Table 8: GCON Backbone and Training Hyperparameters

Reduction	# Nodes	$\times$ MDS size	# Edges	$\times$ MDS size
MDS (Base)	250.3 $\pm$ 28.9	–	0 985.0 $\pm$ 115.8	–
MIS	1239.0 $\pm$ 146.8	4.95	2964.0 $\pm$ 352.3	3.01
MVC	1239.0 $\pm$ 146.8	4.95	2964.0 $\pm$ 352.3	3.01
MaxClique	30873.7 $\pm$ 7148.0	123.37	0 91870.3 $\pm$ 21357.4	93.27

Appendix

Table 9: Average number of nodes and edges for the original BA-small graph where we train on solving MDS, and the equivalent graphs for other tasks obtained by applying reductions to the original graphs. For the transformed graphs, we denote the

\times

change in the “blow-up” in the nodes and edges of the resulting graph.

Method	MDS $\downarrow$	MVC $\downarrow$	MIS $\uparrow$	MaxClique $\uparrow$
(MDS Red.) Random	120.43 $\pm$ 25.3	190.11 $\pm$ 36.9	0 59.87 $\pm$ 40.1	1.61 $\pm$ 1.04
(MDS Red.) Base (20 epochs)	* 31.37 $\pm$ 0.62*	165.21 $\pm$ 0.96	0 80.99 $\pm$ 6.42	2.98 $\pm$ 0.12
(MDS Red.) 0-shot	* 31.37 $\pm$ 0.62*	148.21 $\pm$ 2.53	102.78 $\pm$ 2.53	2.46 $\pm$ 0.44
(MDS Red.) F-BB	-	144.59 $\pm$ 1.35	106.25 $\pm$ 1.35	2.27 $\pm$ 0.14
(MDS Red.) FT	-	142.79 $\pm$ 1.37	106.45 $\pm$ 0.92	2.82 $\pm$ 0.01
(MTL) FT (w/ Graph Stats)	32.03 $\pm$ 0.66	139.31 $\pm$ 0.17	111.96 $\pm$ 0.02	4.34 $\pm$ 0.01

Appendix

Table 10: Comparison of our MTL framework with unified-MDS-reduction-based approaches, where we train a GCON model to solve MDS on BA-small graphs, and then “transform” the graphs corresponding to MIS/MVC/MaxClique via constructing the true reductions over the graph. We test three variants of the pretrained MDS model: 0-shot, frozen backbone (F-BB), and full fine-tuning (FT). * denotes the original MDS pretraining result, which is trained for 100 epochs as opposed to constraining to 20 epochs for other tasks.

Problem	Fine-tuned	Baseline	Full
$\uparrow$ MaxCut	2935.82 $\pm$ 0.63	2926.39 $\pm$ 2.46	2946.01 $\pm$ 6.00
$\uparrow$ MaxClique	000 4.31 $\pm$ 0.03	000 4.32 $\pm$ 0.01	000 4.41 $\pm$ 0.02
$\downarrow$ MDS	0 109.72 $\pm$ 0.16	00 129.64 $\pm$ 12.74	01 121.20 $\pm$ 10.38
$\uparrow$ MIS	0 453.51 $\pm$ 0.17	0 452.59 $\pm$ 0.07	00 454.77 $\pm$ 0.13
$\downarrow$ MVC	0 550.55 $\pm$ 0.36	0 554.53 $\pm$ 1.22	00 548.86 $\pm$ 0.35
$\downarrow$ Coloring	00 31.40 $\pm$ 5.29	00 53.48 $\pm$ 4.53	000 10.61 $\pm$ 2.95

Appendix

Table 11: Fine-tuning on MDS-MIS-Coloring pretrained backbones for 20 epochs ( BA-large dataset, 3 runs average)

Problem	Fine-tuned	Extrapol.	Diff	Baseline	Fine-tuned	Extrapol.	Diff	Baseline
	BA-large				BA-small
$\uparrow$ MaxCut	2935.8 $\pm$ 0.6	2936.0 $\pm$ 0.1	+0.01%	2926.4 $\pm$ 2.5	722.8 $\pm$ 1.0	722.0 $\pm$ 1.4	-0.11%	716.9 $\pm$ 1.5
$\uparrow$ MaxClique	00 4.31 $\pm$ 0.03	00 4.30 $\pm$ 0.02	-0.24%	00 4.32 $\pm$ 0.01	00 4.32 $\pm$ 0.01	00 4.34 $\pm$ 0.01	+0.49%	00 4.31 $\pm$ 0.00
$\downarrow$ MDS	109.7 $\pm$ 0.2	111.9 $\pm$ 0.8	+2.01%	0 129.6 $\pm$ 12.7	0 29.6 $\pm$ 0.1	0 29.2 $\pm$ 0.1	-1.61%	0 33.9 $\pm$ 1.2
$\uparrow$ MIS	453.5 $\pm$ 0.2	453.9 $\pm$ 0.2	+0.08%	452.6 $\pm$ 0.1	111.9 $\pm$ 0.1	111.8 $\pm$ 0.0	-0.10%	111.3 $\pm$ 0.3
$\downarrow$ MVC	550.5 $\pm$ 0.4	550.9 $\pm$ 0.3	+0.06%	554.5 $\pm$ 1.2	139.7 $\pm$ 0.3	139.8 $\pm$ 0.2	+0.09%	141.4 $\pm$ 0.2

Appendix

Table 12: Size Extrapolation Comparison on BA-large and BA-small datasets (3 runs average)

Problem	BA-large	BA-small
MaxCut	00 6.23	0 2.23
MaxClique	0 48.95	32.58
MDS	0 46.42	10.65
MIS	0 65.11	22.78
MVC	137.52	31.39
Coloring	00 6.38	0 2.84

Appendix

Table 13: Inference Time Performance on NVIDIA L40S GPU (seconds)

Method	Type	MVC Time	MClique Time	MIS Time
True Size	—	—	—	—
Gurobi	OR	—	1:55	47:34
GFN	SSL	—	0:42	0:32
GCN	SSL-GNN	1:29	0:57	0:45
GIN	SSL-GNN	1:24	0:55	0:35
GATv2	SSL-GNN	1:26	1:02	0:57

Appendix

Table 14: Inference times of Table 2 over the RB-small test set (500 graphs, NVIDIA Tesla V100).

Graph name	Pretrained	Random	Best known
C1000.9	56	29	68
C125.9	32	25	34
C2000.5	11	9	16
C2000.9	48	28	80
C250.9	36	28	44
C400.5	10	8	18

Appendix

Table 15: Comparison of our pretrained (RB small) and a randomly initialized model on 0-shot inference on DIMACS instances for MIS.

Explore similar work

On the Effectiveness of Pretraining for Graph Combinatorial Optimization
Jul 21, 2026David Aguado, Daniel Fuertes, Carlos R. del-Blanco +1Traveling Salesperson Problem Self-Supervised Pre-Training
Grupo de Tratamiento de Imágenes, Information Processing and Telecomunications Center, ETSI Telecomunicación, Universidad Politécnica de Madrid, 28040, Madrid, Spain
Graph Optimization Foundation Model: Tokenizing Graph via A Language-Model Paradigm
Sep 29, 2025Yunhao Liang, Pujun Zhang, Yuan Qu +3Graph SSL Combinatorial Optimization
Faculty of Engineering, The University of Hong Kong, Hong Kong SAR, China · Costello College of Business, George Mason University, VA, USA · Faculty of Business and Economics, The University of Hong Kong, Hong Kong, China +1
Aligning LLMs with Graph Neural Solvers for Combinatorial Optimization
Mar 28, 2026Shaodi Feng, Zhuoyi Lin, Yaoxin Wu +4Combinatorial Optimization Neural Combinatorial Optimization
National Yang Ming Chiao Tung University · Institute for Infocomm Research (I2R), A*STAR · Eindhoven University of Technology Eindhoven +3

Jul 21, 2026J/K move · Enter open · S save

On the Effectiveness of Pretraining for Graph Combinatorial Optimization

David Aguado, Daniel Fuertes, Carlos R. del-Blanco, Fernando Jaureguizar

Grupo de Tratamiento de Imágenes, Information Processing and Telecomunications Center, ETSI Telecomunicación, Universidad Politécnica de Madrid, 28040, Madrid, Spain

Traveling Salesperson Problem Self-Supervised Pre-Training Combinatorial Optimization Graph Contrastive Learning Neural Combinatorial Optimization

Open paper AskPDF arXiv

This paper introduces a self-supervised pretraining framework for graph combinatorial optimization specifically designed to address the nature of routing problems like the Traveling Salesman Problem. By utilizing graph contrastive learning with geometric augmentations (specifically, rotations and axial reflections) the model is forced to learn invariant structural representations and global relative distance distributions. Results demonstrate that this pretraining strategy outperforms non-pretrained models across various problem scales. Notably, the hybrid strategy (combining rotation and reflection) achieved a 6.57% improvement in tour length for TSP1000, proving that geometric pretraining is an important inductive bias for effectively scaling neural solvers to high-dimensional instances.

Abstract

Explore similar work

On the Effectiveness of Pretraining for Graph Combinatorial Optimization

Graph Optimization Foundation Model: Tokenizing Graph via A Language-Model Paradigm

Aligning LLMs with Graph Neural Solvers for Combinatorial Optimization