Graph Neural Networks for Hamiltonian Pathfinding

Pronalaženje puta koji posjećuje svaki vrh grafa točno jednom je problem iz teorije grafova poznat kao traženje Hamiltonovog puta. Traženje Hamiltonovog puta je NP-kompletan problem, što znači da je računski zahtjevan te bi stoga uporaba graf neuronskih mreža bila korisna. U ovom radu implementirano je šest različitih osnovnih graf neuronskih mreža kako bi se testirala njihova izvedba na problemu pronalaženja Hamiltonovog puta. Erdős-Rényi grafovi korišteni su za treniranje, validaciju i testiranje modela. Svaki model je testiran s različitim brojem slojeva, a najbolji od njih i s različitim početnim stopama učenja. Modeli su uspjeli naučiti kako pronaći Hamiltonov put, ali performanse opadaju s većim veličinama grafova.Finding a route that visits every graph vertex precisely once is referred to as the graph theory problem known as Hamiltonian Pathfinding. Hamiltonian Pathfinding is an NP-complete problem, which means it is computationally expensive, and therefore the use of graph neural networks would be beneficial. In this paper, six different basic graph neural networks were implemented in order to test their performance on the Hamiltonian Pathfinding problem. Erdős-Rényi graphs were used for training, validation, and testing models. Each model was tested with a different number of layers, and the best model with two additional different starting learning rates. The models were able to learn how to find the Hamiltonian path, but performance drops with larger graph sizes