Learning to solve combinatorial optimization problems with heterophily

doi:10.1016/j.neunet.2025.107554

Learning to solve combinatorial optimization problems with heterophily

2025-06-07

0

PRE

AI

DOI：10.1016/j.neunet.2025.107554

Original

Original request for help

Save

Abstract

En 中文

Graph Neural Networks (GNNs) are widely used to address combinatorial optimization problems. However, many popular GNNs struggle to generalize to heterophilic scenarios where adjacent nodes tend to be with different labels or dissimilar features, such as graph coloring problem. Moreover, most existing methods are typically optimized for specific instances and lack generalizability. To address these limitations, we propose an innovative self-supervised pre-training and fine-tuning framework HOCO for combinatorial optimization problems with heterophily. It adopts a heterophilic graph encoder to capture the heterophily through the separation of the node and its neighbors. Besides, bi-level optimization strategies are incorporated into our model: at the node level, contrastive learning helps to enhance representation discrimination of adjacent nodes; at the graph level, structural entropy optimization is used to refine the global clustering structure. Experimental results demonstrate that our model performs well on the graph coloring and maximum k-cut problems, significantly improving accuracy, generalization ability and computational efficiency compared to various baseline algorithms.

Keywords:

Self-supervised pre-training

Combinatorial optimization

Heterophilic graph neural network

Contrastive learning

Graph structural entropy

Learning to solve combinatorial optimization problems with heterophily

Abstract

Journal

Organization