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

undergraduate thesis

• Title (english): Examining graph isomorphism using deep graph neural networks
• Author: Anabel Dautović
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Tea Arvaj (član povjerenstva)
• Committee member: Filip Martinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-06-28, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

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