.png){kind=icon}
.png){kind=icon}
Return
Degree-aware Progressive Contrastive Learning for Graph Combinatorial Optimization Problems
.png){kind=icon}
PRE
AI
DOI：10.1007/s11633-024-1532-2.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Graph combinatorial optimization
contrastive learning
graph neural network
unsupervised learning
machine learning
Journal
IF:
8.7
Papers:
301
Citations:
882