Finding Hamiltonian cycles with graph neural networks

Filip Bosnić, Mile Šikić
6/10/2023
cs.LGcs.SI

No official code found. Best implementation: lbcb-sci/GNNs-Hamiltonian-cycles (5 stars, MIT, last commit 2023-05-02).

Abstract

We train a small message-passing graph neural network to predict Hamiltonian cycles on Erdős-Rényi 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.

View on arXivView PDF

Code Implementations(1)

lbcb-sci/GNNs-Hamiltonian-cyclesCommunity100%
MIT

Supplementary code for "Finding Hamiltonian cycles with graph neural networks"

53PythonJun 4, 20213 years agoMIT

Similar Papers

Rapid training of Hamiltonian graph networks using random features

86% match2025

Training Hamiltonian neural networks without backpropagation

83% match1 repo72024

A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning

81% match2023

Applications of Machine Learning to Modelling and Analysing Dynamical Systems

81% match2023

Graph Attention Hamiltonian Neural Networks: A Lattice System Analysis Model Based on Structural Learning

81% match2024

Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs

81% match2024

Cite this paper

@article{bosni2023finding,
  title  = {Finding Hamiltonian cycles with graph neural networks},
  author = {Filip Bosnić and Mile Šikić},
  year   = {2023},
  eprint = {2306.06523},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2306.06523v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2306.06523.svg)](https://codeofpaper.com/paper/2306.06523)

Discussion