UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimization

Kien X. Nguyen; Ilya Safro

cs.LGMar 12, 2026

UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimization

Authors: Kien X. Nguyen, Ilya Safro

Organizations: Department of Computer and Information Sciences, University of Delaware, Newark DE 19716, USA

Abstract

Unsupervised neural combinatorial optimization (NCO) offers an appealing alternative to supervised approaches by training learning-based solvers without ground-truth solutions, directly minimizing instance objectives and constraint violations. Yet for graph node subset-selection problems (e.g., Maximum Clique and Maximum Independent Set), existing unsupervised methods are typically specialized to a single problem class and rely on problem-specific surrogate losses, which hinders learning across classes within a unified framework. In this work, we propose UniHetCO, a unified heterogeneous graph representation for constrained quadratic programming-based combinatorial optimization that encodes problem structure, objective terms, and linear constraints in a single input. This formulation enables training a single model across multiple problem classes with a unified label-free objective. To improve stability under multi-problem learning, we employ a gradient-norm-based dynamic weighting scheme that alleviates gradient imbalance among classes. Experiments on multiple datasets and four constrained problem classes demonstrate competitive performance with state-of-the-art unsupervised NCO baselines, strong cross-problem adaptation potential, and effective warm starts for a commercial classical solver under tight time limits.

Figures & tables

Figure 1: High-level comparison between existing single-problem (top) and our multi-problem (bottom) neural combinatorial optimization framework. By encoding objectives and constraints into the input graph, our approach enables joint training across multiple problem classes.

Figure 2: Examples of MIS, MC, MVC and MDS instances encoded in our unified heterogeneous graph. The objectives and constraints are listed for each problem class, along with a simple example for $\mathbf{Q},\mathbf{c},\mathbf{A},$ and $\mathbf{b}$ and the corresponding heterogeneous graph defined in Sec. 4.1 . Red nodes are decision variables; black edges are original-graph relations; green edges are objective-graph relations. Blue squares are constraint nodes, connected to variables by blue dashed edges.

	IMDB	COLLAB	Twitter	RB200	SparseSuit
Number of $G_{\text{prob}}$ layers	4	4	6	6	6
Number of $G_{\text{obj}}$ layers	1	1	1	1	1
Number of $G_{\text{constr}}$ layers	4	4	6	6	6
Epochs (single-problem)	50	50	50	50	50
Epochs (multi-problem)	100	100	100	100	100
Batch size (single-problem)	64	64	64	64	64

Table 1: Main hyper-parameter settings for the datasets we use in our experiments.

Dataset	IMDB		COLLAB
Problem Class	MC	MVC	MC	MVC
EGN [ 15 ]	1.0000 (0.02)	1.0000 (0.02)	0.9820 (0.09)	1.0130 (0.04)
Meta-EGN [ 32 ]	1.0000 (0.02)	1.0000 (0.02)	0.9880 (0.09)	1.0003 (0.04)
UniHetCO (Ours)	1.0000 (0.01)	1.0000 (0.02)	0.9764 (0.07)	1.0019 (0.10)
Greedy	0.9888 (0.01)	1.0000 (0.01)	0.9916 (0.27)	1.2090 (0.33)
Gurobi v12.03 ( $\leq$ 0.2s)	1.0000 (0.02)	1.0000 (0.01)	0.9916 (0.07)	1.0000 (0.08)

Table 2: Results on the single-problem setting with state-of-the-art baselines and Gurobi, evaluated on MC and MVC.

Dataset	Twitter
Problem Class	MIS	MC	MVC	MDS
UniHetCO-Single	0.9725 (0.07)	0.9449 (0.07)	1.0338 (0.08)	1.0535 (0.12)
UniHetCO-ERM	0.9690 (0.07)	0.9072 (0.07)	1.1037 (0.08)	1.0585 (0.12)
UniHetCO-SW	0.9573 (0.07)	0.8996 (0.07)	1.0485 (0.08)	1.0456 (0.12)
UniHetCO-DW	0.9629 (0.07)	0.9080 (0.07)	1.0464 (0.08)	1.0452 (0.12)
Gurobi v12.03 ( $\leq$ 0.2s)	0.9964 (0.05)	0.9094 (0.19)	1.0007 (0.05)	1.0000 (0.01)

Table 3: Results on the multi-problem setting among UniHetCO variants on Twitter and RB200, evaluated on MIS, MC, MVC, and MDS.

Problem Class	MIS	MC	MVC	MDS
UniHetCO-Single	0.8845 (0.10)	0.9647 (0.08)	1.0746 (0.10)	1.0781 (0.20)
UniHetCO-ERM	0.7829 (0.10)	0.9786 (0.08)	1.1603 (0.10)	1.0732 (0.20)
UniHetCO-SW	0.8294 (0.10)	0.9567 (0.08)	1.0840 (0.10)	1.0802 (0.20)
UniHetCO-DW	0.8718 (0.10)	0.8736 (0.08)	1.0886 (0.10)	1.1236 (0.20)
Gurobi ( $\leq$ 0.2s)	0.9991 (0.02)	0.9476 (0.20)	1.0000 (0.02)	1.0279 (0.07)
Gurobi ( $\leq$ 1.0s)	1.0000 (0.03)	1.0000 (0.40)	1.0000 (0.03)	1.0098 (0.24)

Table 4: Results on multi-problem setting among three variants of UniHetCO on SparseSuit, evaluated on MIS, MC, MVC and MDS.

Figure 3: Results on cross-problem generalization and adaptation on the Twitter dataset across all four problem classes. In each subfigure, the target class is held out during training (e.g., MIS is evaluated after training on MC, MVC, and MDS), and performance is reported under zero-shot transfer and fine-tuning. The dashed horizontal line denotes the UniHetCO-Single baseline approximation ratio. Note that it is higher better for MIS and MC, and lower better for MVC and MDS.

Figure 4: Results on warm-start for Gurobi (

\leq

0.2s) for the MC problem. We use three datasets Twitter, RB200 and SparseSuit. UniHetCO-Single yields the strongest warm-start, with UniHetCO-DW offering smaller but still positive gains.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	IMDB	COLLAB	Twitter	RB200	SparseSuit
Training	800	4100	773	2000	800
Validation	100	450	100	200	100
Testing	100	450	100	100	90

Appendix

Table 5: Training, validation and testing splits for the datasets in our experiments.

Dataset	IMDB
Problem Class	MIS	MC	MVC	MDS
UniHetCO-Single	1.0000 (0.01)	1.0000 (0.02)	1.0000 (0.02)	1.0000 (0.01)
UniHetCO-ERM	1.0000 (0.01)	0.9698 (0.02)	1.0432 (0.02)	1.0100 (0.01)
UniHetCO-SW	0.9933 (0.01)	0.9518 (0.02)	1.0000 (0.02)	1.0000 (0.01)
UniHetCO-DW	0.9950 (0.01)	0.9500 (0.02)	1.0350 (0.02)	1.0000 (0.01)
Gurobi v12.03 ( $\leq$ 0.2s)	0.9964 (0.01)	1.0000 (0.02)	1.0007 (0.01)	1.0000 (0.01)

Appendix

Table 6: Results on the multi-problem setting among UniHetCO variants on IMDB and COLLAB, evaluated on MIS, MC, MVC, and MDS.

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 381 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
Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe
Sep 22, 2026Akbar Rafiey, Yifei Xu, Nikolaos KaraliasSelf-Supervised Learning Combinatorial Optimization
NYU · MIT
Enabling Population-Based Architectures for Neural Combinatorial Optimization
Jan 13, 2026Andoni Irazusta Garmendia, Josu Ceberio, Alexander MendiburuMetaheuristic Optimization Combinatorial Optimization
University of the Basque Country (EHU), Department of Computer Science and Artificial Intelligence, San Sebastian, Spain.

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

Combinatorial Optimization

Explore similar work

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

Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe

Enabling Population-Based Architectures for Neural Combinatorial Optimization