Graf neuronske mreže za traženje Hamiltonovog puta

završni rad

• Naslov (engleski): Graph Neural Networks for Hamiltonian Pathfinding
• Autor: Katarina Gaćina
• Mentor: Mile Šikić (mentor)
• Član povjerenstva: Mile Šikić (predsjednik povjerenstva)
• Član povjerenstva: Filip Tomas (član povjerenstva)
• Član povjerenstva: Rafael Josip Penić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-07-05, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: GCN; GAT; GraphSAGE; graf; konvolucija; mehanizmi pažnje
• Ključne riječi (engleski): graph; attention; convolution; GraphSAGE; edge distinction; GAT; GCN
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:646268
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-10-11 08:52:24