Degree-aware Progressive Contrastive Learning for Graph Combinatorial Optimization Problems

Addressing graph combinatorial optimization problems often poses significant challenges due to the difficulty and high cost of obtaining supervised labels. As a result, unsupervised algorithms have garnered increasing attention from researchers. In this paper, we propose a novel unsupervised framework that leverages contrastive learning to address these challenges. Drawing inspiration from traditional exact algorithms, we introduce a vertex-based degree-aware data augmentation method that enables the progressive learning of graph structure features. Furthermore, we incorporate optimal transport theory by using distance measures as the contrastive loss, thereby enhancing the model′s ability to capture local graph structures. Extensive experiments demonstrate the superior performance of our approach in terms of both solution accuracy and inference speed on most graph combinatorial optimization problems, particularly in large-scale graph problems and scenarios where training samples are scarce.