Pre-training and fine-tuning: a unified approach for solving graph combinatorial optimization problems

To overcome computational inefficiency and generalization limitations in graph combinatorial optimization (GCOP) by establishing a unified framework (GCOP-PREMA) that leverages pre-training and fine-tuning to achieve state-of-the-art performance across multiple NP-hard problems (MVC, MIS, MC, MaxCut).

The proposed framework employed a three-stage methodology: First, diverse GCOPs were reduced to Quadratic Unconstrained Binary Optimization (QUBO) representations. Second, a custom QUBO Former model—integrating graph transformers with message-passing networks and positional encoding—was pre-trained on mixed QUBO datasets using Deep Q-Networks and adaptive penalty adjustment. Third, five fine-tuning strategies (e.g., decoder-specific updates) adapted the model to downstream tasks with minimal computational overhead.

Fine-tuning boosts MIS performance by 56.67% and MaxCut by 28.44% versus pre-trained baselines. The Centrality Encoding variant achieves solutions within 5% of Gurobi′s optimality across problems and outperforms specialized algorithms. Runtime analysis confirms stable efficiency, particularly on large-scale graphs.

GCOP-PREMA bridges specialized solvers and general-purpose AI by unifying problem reformulation, pre-training, and adaptive fine-tuning. It significantly advances cross-problem generalization while maintaining architectural consistency, with future work targeting optimization imbalance and diffusion-model enhancements.