Effektive algoritmer med grafnevrale nettverk

Maskinlæring har i nyere tid revolusjonert flere områder innen den digitale verden. Alt fra selvkjørende biler til avanserte språkmodeller som ChatGPT viser hvor langt feltet har kommet. Både i akademia og industrien jobbes det aktivt med å kartlegge hvilke problemer maskinlæring kan løse, og hvor effektive disse løsningene er sammenlignet med tradisjonelle metoder.

Denne avhandlingen undersøker hvordan maskinlæring kan bidra til å løse grafteoretiske problemer mer effektivt. En graf i denne sammenhengen er en abstrakt datastruktur som representerer relasjoner mellom objekter – ofte kjent som et "nettverk". Slike grafer kan brukes i alt fra trafikkstyring og cybersikkerhet til logistikk og kommunikasjonssystemer.

Å tilpasse maskinlæring til grafer byr på flere utfordringer, og dagens teknologi har begrensninger for hvor mye den kan lære av en grafs struktur. På tross av dette viser hovedresultatet i denne avhandlingen at maskinlæring kan være et nyttig verktøy for å løse vanskelige grafteoretiske problemer i praksis. Det er viktig å påpeke at dette kun er tilfelle ved et nøyaktig samspill mellom tradisjonelle metoder og maskinlæring.

Programvaren som er utviklet i forbindelse med denne avhandlingen kan håndtere store grafer med millioner av objekter. Kode fra prosjektet var også med å vinne førsteplass i den årlige konkurransen PACE (Parameterized Algorithms and Computational Experiments).

Personalia

Kenneth Langedal (f. 1993) er dataingeniør med en mastergrad i programvareutvikling fra Universitetet i Bergen og Høgskulen på Vestlandet. Han startet som stipendiat ved Universitetet i Bergen i slutten av 2020 med veileder professor Fredrik Manne.