Learning to solve combinatorial optimization problems with heterophily.

Abstract

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.