Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms

Technische Samenvatting: Scalable Topology-Preserving Graph Coarsening (STPGC)

Probleemstelling
Graph coarsening (het vergroven van grafen) heeft als doel de grootte van een graaf te reduceren terwijl specifieke eigenschappen behouden blijven om efficiënte analyse te faciliteren, met name voor Graph Neural Networks (GNNs). Bestaande methoden richten zich primair op het behoud van spectrale eigenschappen (eigenwaarden/eigenvectoren van de Laplaciaan) of ruimtelijke kenmerken (lokale connectiviteit, invloedsdiffusie). Hoewel recent onderzoek aangeeft dat het behoud van topologische kenmerken (connectiviteit, ringen, hogere-orde holtes) cruciaal is voor het behoud van GNN-prestaties, lijden huidige topologie-behoudende benaderingen aan ernstige schaalbaarheidsproblemen. Specifiek heeft de state-of-the-art methode, Graph Elementary Collapse (GEC), te maken met exponentiële worst-case tijdscomplexiteit van $O(3^{n/3})$ door het gebruik van clique-enumeratie om reduceerbare structuren te identificeren. Dit maakt GEC onpraktisch voor grootschalige grafen. Bovendien verstoort de workaround van GEC waarbij grafen worden gepartitioneerd de globale topologische kenmerken, die niet kunnen worden hersteld tijdens reconstructie.

Methodologie
De auteurs stellen Scalable Topology-Preserving Graph Coarsening (STPGC) voor, een framework dat concepten uit de algebraïsche topologie — specif gezien strong collapse en edge collapse — uitbreidt naar het domein van grafen. In tegenstelling tot GEC vermijdt STPGC kostbare clique-enumeratie door reduceerbare structuren te identificeren via buurt-inclusie (neighborhood inclusion).

Het framework bestaat uit drie kernalgoritmen:

1. GStrongCollapse: Identificeert iteratief "gedomineerde knopen". Een knoop $u$ wordt gedomeerd door $v$ als de gesloten buurt van $u$ een deelverzameling is van de gesloten buurt van $v$ ($N[u] \subseteq N[v]$). Het algoritme verwijdert gedomeerde knopen en hun randen, en voegt ze samen tot superknopen.
2. GEdgeCollapse: Identificeert iteratief "gedomeerde randen". Een rand $(x, y)$ wordt gedomeerd door een knoop $v$ (waarbij $v \notin \{x, y\}$) als de gesloten buurt van de rand een deelverzameling is van de gesloten buurt van $v$ ($N[x, y] \subseteq N[v]$). Het verwijderen van deze randen doorbreekt structurele deadlocks, waardoor nieuwe gedomeerde knopen worden blootgesteld.
3. NeighborhoodConing: Om scenario's af te handelen waarin aanvankelijk geen gedomeerde knopen of randen bestaan, voegt dit algoritme "gedomeerde randen" in tussen buren van een doelknoop $u$ om een nieuwe gedomeerde knoop te creëren. Dit proces, geformaliseerd als "coning", maakt verdere reductie mogelijk terwijl homotopie-equivalentie behouden blijft.

Theoretische Garanties
Het artikel bewijst dat de combinatie van deze operaties de homotopie-equivalentie tussen de originele graaf en de vergroefde graaf behoudt. Dit zorgt ervoor dat topologische invarianten, zoals verbonden componenten, ringen, holtes en Betti-getallen, behouden blijven. Verder demonstreren de auteurs dat deze operaties het GNN receptieve veld behouden. Specifiek:

• GStrongCollapse en NeighborhoodConing verhogen de kortste padafstand tussen elk paar knopen niet.
• GEdgeCollapse verhoogt de kortste padafstand met maximaal 1.
  Dit behoud van kortste padafstanden zorgt ervoor dat de informatieaggregatie-scope voor GNNs grotendeels intact blijft.

Om de beperking aan te pakken dat exacte topologische preservatie mogelijk geen willekeurige coarsening-ratio's bereikt (vanwege het NP-harde karakter van het reduceren van een graaf tot zijn minimale kern), introduceren de auteurs ApproximateCoarsening. Deze tweestapsstrategie voert eerst exacte coarsening uit en past vervolgens $r$-relaxed strong collapse toe, wat toestaat dat tot $r$ knopen in de buurt-inclusievoorwaarde ontbreken, wat flexibele reductieratio's mogelijk maakt.

Belangrijkste Bijdragen

1. Nieuwe Concepten en Algoritmen: De introductie van graph strong collapse en graph edge collapse, uitgebreid vanuit de algebraïsche topologie, geïmplementeerd via drie schaalbare algoritmen (GStrongCollapse, GEdgeCollapse, NeighborhoodConing) die gedomeerde structuren elimineren zonder exponentiële complexiteit.
2. Toepassing op GNN Training: Een bewijs dat STPGC het GNN receptieve veld behoudt, gekoppeld aan een benaderende coarsening-strategie om de balans te vinden tussen topologische getrouwheid en schaalbaarheid voor trainingsversnelling.
3. State-of-the-Art Prestaties: Empirisch bewijs dat STPGC bestaande baselines overtreft in taken voor knopenclassificatie, terwijl het significante verbeteringen in runtime biedt.

Experimentele Resultaten
Experimenten werden uitgevoerd op vijf gelabelde benchmarks (Cora, Citeseer, DBLP, ogbn-arXiv, ogbn-products) voor knopenclassificatie en vier grote ongelabelde datasets voor de evaluatie van schaalbaarheid.

• Nauwkeurigheid: STPGC presteerde consistent beter dan negen baselines, inclus\nief spectrale en ruimtelijke methoden. Het behaalde een gemiddelde verbetering in nauwkeurigheid van 1,73% ten opzichte van GEC over vijf datasets. De resultaten benadrukken dat topologie-behoudende methoden (STPGC en GEC) over het algemeen beter presteren dan niet-topologie-behoudende baselines.
• Efficiëntie: STPGC demonstreerde een superieure runtime en geheugenefficiëntie vergeleken met alle baselines. Merkwaardig genoeg behaalde het een tot wel 37x versnelling in runtime ten opzichte van GEC. Op de DBLP-dataset bij een coarsening-ratio van 0,1 was STPGC meer dan 15x sneller dan GEC.
• Topologische Preservatie: Analyse van Betti-getallen toonde aan dat STPGC het aantal topologische kenmerken strikt handhaaft totdat de exacte coarsening-fase eindigt, terwijl andere methoden (inclusief GEC) topologische kenmerken vroegtijdig verliezen door graafpartitionering of een gebrek aan globale preservatie.
• Schaalbaarheid: Op grootschalige datasets (LiveJournal, Youtube, cit-Patent, Flixster) vertoonde STPGC een bijna lineaire schaalbaarheid in runtime en een monotone geheugengroei, wat de toepasbaarheid op massieve grafen valideert.

Betekenis en Claims
Het artikel claimt dat STPGC een theoretisch onderbouwde, schaalbare oplossing biedt voor graph coarsening die topologische kenmerken rigoureus behoudt, een capaciteit die voorheen beperkt werd door computationele complexiteit. Door homotopie-equivalentie te garanderen en het GNN receptieve veld te behouden, stelt STPGC het trainen van GNNs op aanzienlijk kleinere grafen mogelijk zonder prestatieverlies op de originele data. De auteurs positioneren STPGC als een "plug-and-play" preprocessing-module die onafhankelijk is van downstream GNN-architecturen.

Het werk draagt bij aan "Green AI" door de computationele middelen en het energieverbruik te verminderen die nodig zijn voor het trainen van GNNs op grootschalige grafen. De auteurs erkennen beperkingen, zoals het gebruik van heuristische kenmerk-averaging en majority-vote labelaggregatie voor superknopen, wat suboptimaal kan zijn voor bepaalde taken, en suggereren toekomstig werk voor de toepassing van deze methoden op bredere domeinen zoals biologische datacompressie voor drug discovery.