Geometrically Invariant and Equivariant Graph Neural Networks for TSP Algorithm Selection and Hardness Prediction

Algorithm selection and instance hardness prediction are important tasks in combinatorial optimization, as different algorithms perform optimally on different instances, and accurately predicting instance difficulty enables more efficient problem-solving strategies. While researchers have explored feature-based machine learning models for these tasks, there remains a lack of general and effective instance representations, even for fundamental problems like the Euclidean Traveling Salesman Problem (TSP). Recent studies have leveraged Convolutional Neural Networks (CNNs) to learn TSP representations, but they still require intermediate image-based representations, introducing additional preprocessing steps. We tackle algorithm selection and hardness prediction problems for TSP, but instead treat instances as geometric graphs. We propose four Geometrically Invariant and Equivariant Graph Neural Networks (GIE-GNNs), based on conventional GNN models. The proposed GIE-GNNs incorporate a novel message-passing mechanism to capture geometric information effectively. Evaluations on two algorithm selection and two hardness prediction datasets demonstrate that our GNNs outperform feature-based, CNN-based, and standard GNN approaches designed for non-geometric graphs and point clouds. Moreover, our analysis highlights that our GNNs uniquely achieve geometrically invariant predictions. Code and datasets are available at GitHub.