Technische Samenvatting: Neuronale Versnelling voor Grafpartitie

Probleemdefinitie

Grafpartitie, specifiek Grafbisectie (GB), is een fundamenteel NP-moeilijk probleem in wetenschappelijk rekenen, VLSI-ontwerp en parallel rekenen. Het doel is om de verzameling van knopen van een graaf te verdelen in twee disjuncte, ruwweg even grote deelverzamelingen, terwijl het aantal randen dat ze verbindt (de randdoorsnede) wordt geminimaliseerd.

Hoewel Spectrale Bisectie (SB) een gewaardeerde methode is voor het genereren van hoogwaardige partities door gebruik te maken van de Fiedler-vector (de eigenvector die hoort bij de op één na kleinste eigenwaarde van de graf-Laplaciaan), kampt deze methode met aanzienlijke computatieflessenhalsen. Het berekenen van de Fiedler-vector vereist een dichte eigenwaarde-decompositie, wat hoge geheugenkosten ($O(|V|^2)$) en rekenkundige overhead met zich meebrengt, waardoor het onpraktisch is voor grote, schaarse grafen. Bestaande alternatieven, zoals meervoudige methoden (bijv. METIS) of geometrische methoden, vertrouwen vaak op heuristieken die mogelijk suboptimale initiële partities produceren of specifieke coördinaten vereisen die in veel real-world grafen ontbreken.

Methodologie

De auteurs stellen een raamwerk voor Neuronale Versnelling voor dat de computatiedure eigenwaarde-berekening in spectrale partitie vervangt door een lichtgewicht Kunstmatig Neuraal Netwerk (ANN) om de Fiedler-vector te benaderen.

Kernarchitectuur

• Modeltype: Een eenvoudig, supervised, dicht neuraal netwerk met één verborgen laag.
• Invoer: Een uitgevlakte $128 \times 128$ graf-Laplaciaan-matrix.
• Uitvoer: Een vector van 128 eenheden die de Fiedler-vector benadert.
• Configuratie: De verborgen laag bevat 512 eenheden met bias en $tanh$-activering. Het model heeft ongeveer 8,45 miljoen trainbare parameters.
• Training: Het model wordt getraind op een GPU met de Adagrad-optimizer om de Gemiddelde Absolute Fout (L1-verlies) tussen de voorspelde vector en de ware Fiedler-vector te minimaliseren. De training is ontworpen om tijdens het compileren te worden voltooid.

Schaalbaarheidsraamwerk

Om grafen groter dan de trainingsgrootte van 128 knopen te verwerken, introduceren de auteurs een tweeledig verwerkingsstroom:

1. Vergroving: In plaats van traditionele zware-rand-matching (HEM) gebruiken de auteurs een Lokale Buurwervelfilter (schuifvenster-gemiddelde) die wordt toegepast op de bijkomende matrix. Deze techniek, geïnspireerd door beeldverwerking, verkleint de grafgrootte terwijl deze structurele patronen beter behoudt dan HEM voor neuronale leerprocessen.
2. Inferentie: Het neurale netwerk voorspelt de Fiedler-vector voor de vergroefde graaf.
3. Verfijning: De partitie wordt geïnterpoleerd terug naar de oorspronkelijke grafgrootte en verfijnd met het Fiduccia-Mattheyses (FM)-algoritme om randdoorsnedes te verbeteren.

Belangrijkste Bijdragen

1. Neuronale Benadering van Spectrale Methoden: Het artikel toont aan dat een eenvoudig dicht neuraal netwerk de Fiedler-vector effectief kan benaderen, een taak die traditioneel iteratieve eigen-decompositie vereist.
2. Efficiënte Training en Inferentie: Door GPU-versnelling voor dichte tensorbewerkingen te benutten, bereikt de methode inferentietijden die vergelijkbaar zijn met of sneller zijn dan traditionele oplossers, ondanks het aantal parameters van het model.
3. Nieuwe Vergroevingsstrategie: De auteurs stellen een lokaal buurwervelgemiddelde-filter voor voor grafvergroving, met het argument dat dit structurele patronen effectiever behoudt voor neuronale netwerklering in vergelijking met standaard HEM, dat willekeurige verdelingen in de bijkomende matrix produceert.
4. Integratie met Verfijning: De aanpak is ontworpen om een hoogwaardige initiële partitie te leveren die, in combinatie met standaard FM-verfijning, resultaten oplevert die concurrerend zijn met volledige spectrale bisectie.

Experimentele Resultaten

De evaluatie gebruikte datasets uit de SuiteSparse Matrix Collection, inclusief zowel kleine grafen (128 knopen) voor training/testen als grotere real-world grafen (tot ongeveer 1.000 knopen) voor schaalbaarheidstests.

• Partite Kwaliteit:
  • Zonder Verfijning (NN): Het neurale netwerk alleen produceerde partities met een randdoorsnede die ongeveer 1,56 keer slechter was dan volledige spectrale bisectie.
  • Met Verfijning (NN-FM): Wanneer gecombineerd met FM-verfijning, verbeterde de benaderingsratio tot 1,03 keer het resultaat van spectrale bisectie, wat wijst op bijna gelijke kwaliteit.
  • Vergelijking: De NN-FM-aanpak presteerde aanzienlijk beter dan willekeurige partitie en kwam vaak overeen met of overtrof METIS in specifieke gevallen, met name op grafen die zijn vergroefd met de voorgestelde schuifvenstertechniek.
• Prestaties en Timing:
  • CPU: Op CPU waren traditionele methoden (METIS, eigh) sneller dan de neuronale inferentie (METIS was ongeveer 8,3x sneller).
  • GPU: Op GPU was de inferentie van het neurale netwerk 4,5 keer sneller dan de iteratieve eigh-oplosser en vergelijkbaar met METIS.
• Geheugen: Het model vereist ongeveer 34 MB geheugen, wat verwaarloosbaar is in vergelijking met moderne GPU-geheugencapaciteiten.

Betekenis en Beweringen

Het artikel beweert dat neuronale versnelling een haalbaar alternatief biedt voor traditionele spectrale partitie, met name voor grootschalige problemen waarbij geheugen- en rekenkosten prohibitief zijn. Door de dure eigen-decompositiestap te vervangen door een voorgetraind neuraal netwerk, bereiken de auteurs:

• Schaalbaarheid: Het vermogen om grote grafen te verwerken door de zware berekening uit te besteden aan de GPU.
• Efficiëntie: Een aanzienlijke reductie in uitvoeringstijd op GPU-hardware in vergelijking met iteratieve oplossers.
• Kwaliteit: Het genereren van initiële partities die, na standaard verfijning, een kwaliteit bereiken die vergelijkbaar is met de gouden standaard spectrale methode.

De auteurs concluderen dat deze aanpak de automatisering van spectrale partitie voor wetenschappelijke toepassingen mogelijk maakt, heterogene rekenomgevingen (CPU-GPU) beter benut en tegelijkertijd een hoge partite-kwaliteit behoudt. Zij benadrukken dat de methode het meest effectief is wanneer de vergroevingsmethode overeenkomt met de verdeling van de trainingsdata (d.w.z. het gebruik van de schuifvensterfilter in plaats van HEM).