Ispitivanje izomorfnosti grafova s pomoću dubokih graf neuronskih mreža

završni rad

• Naslov (engleski): Examining graph isomorphism using deep graph neural networks
• Autor: Anabel Dautović
• Mentor: Anamari Nakić (mentor)
• Član povjerenstva: Anamari Nakić (predsjednik povjerenstva)
• Član povjerenstva: Tea Arvaj (član povjerenstva)
• Član povjerenstva: Filip Martinović (č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: 2024-06-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Ovaj rad istražuje primjenu dubokih neuronskih mreža na problem testiranja izomorfizma grafova, fundamentalnog izazova u teoriji grafova s raznolikim primjenama. Grafovi su matematičke strukture sastavljene od vrhova i bridova, a određivanje jesu li dva grafa izomorfna je računalno složen zadatak. Duboke neuronske mreže grafova pružaju pristup rješavanju tog izazova učenjem složenih reprezentacija struktura grafova. U ovom istraživanju, razvijena je i trenirana duboka neuronska mreža grafova na skupu generiranih podataka kako bi predvidjela izomorfizam grafova. Kroz eksperimentiranje i analize, istražen je utjecaj različitih arhitektura mreža i parametera na točnost predikcije. Zaključak je da popularne graf neoronske mreže nemaju dobru sposobnost determinacije izomorfizma, potencijalno jer ne razlikuju dovoljno dobro grafove koji su slučni ali nisu izomorfni.

Sažetak (engleski)

This thesis investigates the application of deep graph neural networks to the problem of graph isomorphism testing, a fundamental challenge in graph theory with wide-ranging applications. Graphs are essential mathematical structures composed of vertices and edges, and determining whether two graphs are isomorphic is a computationally complex task. Deep graph neural networks offer a promising approach to address this challenge by learning intricate representations of graph structures. In this study, a deep graph neural network is developed and trained on a generated dataset to predict graph isomorphism. Through experimentation and analysis, the influence of different network architectures and parameters on prediction accuracy is examined. The conclusion is that popular Graph Neural Networks lack the ability to effectively determine isomorphism. This may be because they do not sufficiently distinguish between graphs that are similar but not isomorphic.

• Ključne riječi: teorija grafova; izomorfizam grafova; duboke neuronske mreže; graf neuronske mreže
• Ključne riječi (engleski): graph theory; graph isomorphism; deep neural networks; graph neural networks
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:255317
• 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: 2024-10-12 20:25:02