Graf neuronske mreže za traženje Hamiltonovog puta

undergraduate thesis

• Title (english): Graph Neural Networks for Hamiltonian Pathfinding
• Author: Katarina Gaćina
• Mentor: Mile Šikić (mentor)
• Committee member: Mile Šikić (predsjednik povjerenstva)
• Committee member: Filip Tomas (član povjerenstva)
• Committee member: Rafael Josip Penić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-05, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: GCN; GAT; GraphSAGE; graf; konvolucija; mehanizmi pažnje
• Keywords (english): graph; attention; convolution; GraphSAGE; edge distinction; GAT; GCN
• Language: english
• URN:NBN: urn:nbn:hr:168:646268
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-10-11 08:52:24