Graph Neural Networks in Algorithm Engineering

Abstract

Graf Nevrale Nettverk (GNN) er ny teknologi innen kunstig intelligens. GNN viderefører de vellykkede ideene fra konvensjonell dyplæring til å fungere på grafer. For ulike grafteoretiske problemer har GNN blitt et nytt verktøy som både kan åpne for nye muligeheter og heve eksisterende metoder. Denne avhandlingen fokuserer på bruk av GNN-er for å løse grafproblemer i praksis. Selv om denne nye teknologien kan være nyttig, er det også klart at på nåværende tidspunkt kan ikke GNN-er konkurrere direkte med tradisjonelle grafalgoritmer. Istedet fokuserer vi på å bruke GNN-er som en komponent sammen med konvensjonelle algoritmeteknikker for å utvikle nye algoritmer. Resultatene som blir presentert i denne avhandlingen viser at dette kan føre til bedre og raskere algoritmer for å løse ulike NP-harde grafproblemer i praksis.

For Minste Vektede Nodedekkeproblemet presenterer vi en ny heuristikk som kombinerer reduksjonsregler, GNN-er og lokalt søk. Mens reduksjonsreglene og lokalt søk er de viktigste komponentene, viser vi at GNN-en forbedrer resultatene våre ytterligere. For komplementproblemet, Største Vektede Uavhengige Sett, introduserer vi også en ny metode for å anvende reduksjonsregler raskere ved å bruke GNN-er. Her brukes flere GNN-er for å bestemme hvilke noder som kan reduseres så at vi kan unngå å tape tid på å prøve reduksjonsregler hvor det er usannsynlig at grafen kan reduseres. Etter å ha redusert en graf, brukes ofte en type algoritme basert på forgrening for å finne en optimal løsning. For slike algoritmer viser vi at GNN-er kan brukes for å bestemme hvilken node algoritmen bør forgrene på i neste steg.

En fordel med GNN-er er at beregningene som trengs kan akselereres på flere måter. Dette inkluderer spesialiserte instruksjoner og parallellprosessering. Med dette viser vi at små GNN-modeller kan oppnå samme kjøretider som enkle grådige algoritmer samtidig som de kan ha bedre parallell skalerbarhet. På denne måten klarer vi å utkonkurrere konvensjonelle parallelle grådige algoritmer for Graf-Fargeleggingsproblemet.

Selv om GNN-er kan være nyttige verktøy, er de sjeldent den sentrale komponenten i en algoritme, i hvert fall ikke i de beste programmene for denne typen problemer. Dette er tydelig ved å se hvilke teknikker som blir brukt i den årlige programmeringskonkurransen PACE (Parameterized Algorithms and Computational Experiments Challenge). I PACE har hvert lag seks måneder på utvikle algoritmer for å løse et gitt NP-hardt grafproblem. Det har likevel ikke vært brukt GNN-er av noen lag siden konkurransen starten i 2015. Som det siste kapittelet i denne avhandlingen presenterer vi vårt vinnende bidrag til 2024-iterasjonen av PACE. Til tross for at dette resultatet ikke inkluderer maskinlæring har PACE vært en viktig del gjennom hele PhD-prosjektet.

Graph Neural Networks (GNNs) are recent additions to the field of artificial intelligence. They adapt the successful ideas from conventional deep learning to the irregular structure found in graphs. For various graph theoretical problems, GNNs have become a new tool that can enable new solutions and elevate existing ones. This thesis focuses on using GNNs to solve graph problems in practice. While this new technology can be powerful, it is clear that the current state of GNNs cannot stand up to traditional graph algorithms on their own. Instead, we focus on using GNNs as a component along with conventional algorithmc techniques to develop new algorithms. The results presented in this thesis demonstrate that this can lead to better and faster algorithms for solving various NP-hard graph problems in practice.

For the Minimum Weight Vertex Cover problem, we present a new heuristic that combines data reduction rules, GNNs, and local search. While the reduction rules and local search are the most important components, we show that the GNNs further elevate our results. For the complement problem, Maximum Weight Independent Set, we also introduce a new way of accelerating the application of data reduction rules using GNNs. Here, the GNNs are used for early screening to avoid losing time trying to reduce parts of the graph that are unlikely to be reduced. After reducing an input instance, a branch-and-bound algorithm is often used to find an optimal solution. For such algorithms, we show that GNNs can guide the algorithm and decide where to branch next.

A benefit of GNNs is that the computations involved when using them can be accelerated in several ways. This acceleration includes specialized instructions and parallel processing. With this, we show that small GNN models can reach the same running times as simple greedy algorithms while having better parallel scalability. This allowed us to outperform conventional parallel greedy algorithms for the Graph Coloring problem.

While GNNs can be powerful tools, they are rarely the primary component of an algorithm, at least not in state-of-the-art programs. This is clear when considering the annual programming competition PACE (Parameterized Algorithms and Computational Experiments Challenge). In PACE, teams have six months to work on algorithms to solve a given NP-hard graph problem. Still, GNNs have not appeared in any high-ranking submission since its inception in 2015. As the last chapter in this thesis, we present our winning submission to the 2024 iteration of the PACE challenge. Despite the lack of machine learning in this result, the PACE challenge played an important part throughout the PhD project.