Research
Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?
arXiv:2603.02462v2 Announce Type: replace-cross Abstract: A key challenge in developing unified neural solvers for combinatorial optimization (CO) is the efficient generalization of models from a give
arXiv:2603.02462v2 Announce Type: replace-cross 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.
Related
- GOAL: Graph-based Objective-Aligned Diffusion Solvers for Dynamic Multi-Objective Optimization
- LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solvers
- Are Common Substructures Transferable? Riemannian Graph Foundation Model with Neural Vector Bundles
- Adversarial Instance Generation and Robust Training for Neural Combinatorial Optimization with Multiple Objectives
- Filtered Posterior Mean Collections: A Unified Framework for Analytical Models of Diffusion Generalization
Source: arXiv cs.AI | 2026-08-12