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

• URL: http://arxiv.org/abs/2603.02462v1
• Date: Mon, 02 Mar 2026 23:03:00 GMT
• Title: Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?
• Authors: Semih Cantürk, Thomas Sabourin, Frederik Wenkel, Michael Perlmutter, Guy Wolf,
• Abstract summary: Key challenge in deriving unified neural solvers for optimization (CO) is efficient generalization of models.<n>We first establish a new model, which uses a GCON module as a form of expressive message passing together with energy-based unsupervised loss functions.<n>We propose pretraining and fine-tuning strategies that transfer effectively between MVC, MIS and MaxClique.
• Score: 12.560527470597505
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A key challenge in deriving unified neural solvers for combinatorial optimization (CO) is efficient generalization of models between a given set of tasks to new tasks not used during the initial training process. To address it, we first establish a new model, which uses a GCON module as a form of expressive message passing together with energy-based unsupervised loss functions. This model achieves high performance (often comparable with state-of-the-art results) 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 reduction 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 papers

• A Scalable Pretraining Framework for Link Prediction with Efficient Adaptation [16.82426251068573]
  Link Prediction (LP) is a critical task in graph machine learning.<n>Existing methods face key challenges including limited supervision from sparse connectivity.<n>We explore pretraining as a solution to address these challenges.
  arXiv  Detail & Related papers  (2025-08-06T17:10:31Z)
• HGMP:Heterogeneous Graph Multi-Task Prompt Learning [18.703129208282913]
  We propose a novel multi-task prompt framework for the heterogeneous graph domain, named HGMP.<n>First, to bridge the gap between the pre-trained model and downstream tasks, we reformulate all downstream tasks into a unified graph-level task format.<n>We design a graph-level contrastive pre-training strategy to better leverage heterogeneous information and enhance performance in multi-task scenarios.
  arXiv  Detail & Related papers  (2025-07-10T04:01:47Z)
• Train with Perturbation, Infer after Merging: A Two-Stage Framework for Continual Learning [57.514786046966265]
  We propose textbfPerturb-and-Merge (P&M), a novel continual learning framework that integrates model merging into the CL paradigm to mitigate forgetting.<n>Our proposed approach achieves state-of-the-art performance on several continual learning benchmark datasets.
  arXiv  Detail & Related papers  (2025-05-28T14:14:19Z)
• SyMerge: From Non-Interference to Synergistic Merging via Single-Layer Adaptation [28.417947631789783]
  SyMerge is a lightweight framework that jointly optimize one task-specific layer and merging coefficients.<n>SyMerge achieves state-of-the-art results across vision, dense prediction, and NLP benchmarks.
  arXiv  Detail & Related papers  (2024-12-26T07:42:06Z)
• DeepONet as a Multi-Operator Extrapolation Model: Distributed Pretraining with Physics-Informed Fine-Tuning [6.635683993472882]
  We propose a novel fine-tuning method to achieve multi-operator learning. Our approach combines distributed learning to integrate data from various operators in pre-training, while physics-informed methods enable zero-shot fine-tuning.
  arXiv  Detail & Related papers  (2024-11-11T18:58:46Z)
• ULTRA-DP: Unifying Graph Pre-training with Multi-task Graph Dual Prompt [67.8934749027315]
  We propose a unified framework for graph hybrid pre-training which injects the task identification and position identification into GNNs. We also propose a novel pre-training paradigm based on a group of $k$-nearest neighbors.
  arXiv  Detail & Related papers  (2023-10-23T12:11:13Z)
• Efficient Training of Multi-task Neural Solver for Combinatorial Optimization [23.694457372640912]
  We propose a general and efficient training paradigm to deliver a unified multi-task neural solver.<n>Our method significantly enhances overall performance, regardless of whether it is within constrained training budgets.<n>Our method also achieved the best results compared to single task learning and multitask learning approaches.
  arXiv  Detail & Related papers  (2023-05-10T14:20:34Z)
• Effective Adaptation in Multi-Task Co-Training for Unified Autonomous Driving [103.745551954983]
  In this paper, we investigate the transfer performance of various types of self-supervised methods, including MoCo and SimCLR, on three downstream tasks. We find that their performances are sub-optimal or even lag far behind the single-task baseline. We propose a simple yet effective pretrain-adapt-finetune paradigm for general multi-task training.
  arXiv  Detail & Related papers  (2022-09-19T12:15:31Z)
• Model-Agnostic Multitask Fine-tuning for Few-shot Vision-Language Transfer Learning [59.38343286807997]
  We propose Model-Agnostic Multitask Fine-tuning (MAMF) for vision-language models on unseen tasks. Compared with model-agnostic meta-learning (MAML), MAMF discards the bi-level optimization and uses only first-order gradients. We show that MAMF consistently outperforms the classical fine-tuning method for few-shot transfer learning on five benchmark datasets.
  arXiv  Detail & Related papers  (2022-03-09T17:26:53Z)
• Graph Representation Learning for Multi-Task Settings: a Meta-Learning Approach [5.629161809575013]
  We propose a novel training strategy for graph representation learning, based on meta-learning. Our method avoids the difficulties arising when learning to perform multiple tasks concurrently. We show that the embeddings produced by a model trained with our method can be used to perform multiple tasks with comparable or, surprisingly, even higher performance than both single-task and multi-task end-to-end models.
  arXiv  Detail & Related papers  (2022-01-10T12:58:46Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• Pre-training Text Representations as Meta Learning [113.3361289756749]
  We introduce a learning algorithm which directly optimize model's ability to learn text representations for effective learning of downstream tasks. We show that there is an intrinsic connection between multi-task pre-training and model-agnostic meta-learning with a sequence of meta-train steps.
  arXiv  Detail & Related papers  (2020-04-12T09:05:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.