Finding Hamiltonian cycles with graph neural networks
Filip Bosnić Mile Šikić
We train a small message-passing graph neural network to predict Hamiltonian
cycles on Erd\H{o}s-R\'enyi random graphs in a critical regime. It outperforms
existing hand-crafted heuristics after about 2.5 hours of training on a single
GPU. Our findings encourage an alternative approach to solving computationally
demanding (NP-hard) problems arising in practice. Instead of devising a
heuristic by hand, one can train it end-to-end using a neural network. This has
several advantages. Firstly, it is relatively quick and requires little
problem-specific knowledge. Secondly, the network can adjust to the
distribution of training samples, improving the performance on the most
relevant problem instances. The model is trained using supervised learning on
artificially created problem instances; this training procedure does not use an
existing solver to produce the supervised signal. Finally, the model
generalizes well to larger graph sizes and retains reasonable performance even
on graphs eight times the original size.