Technische Samenvatting: CoRe-GNN: Multilevel Message Passing op Vergroefde Grafen

Probleemstelling

Het trainen van Graph Neural Networks (GNN's) op grootschalige grafen wordt fundamenteel beperkt door de geheugenkosten die nodig zijn om intermediaire node-representaties over lagen heen op te slaan. In standaard message-passing architecturen hangt de representatie van een node op laag $l$ af van zijn $l$-hop buurt. Voor grote grafen groeit deze buurt exponentieel met de diepte, wat leemt bottlenecks veroorzaakt die het GPU-geheugen verzadigen tijdens zowel training als inferentie.

Bestaande schaalbare benaderingen vallen over het algemeen uiteen in twee categorieën, die beide lijden aan complementaire beperkingen:

1. Grafvergroving (Graph Coarsening): Methoden zoals Coarsen-GNN mappen originele nodes naar "supernodes" om een kleinere graaf te creëren. Hoewel dit efficiënte propagatie mogelijk maakt en spectrale garanties biedt, dwingt het alle nodes binnen een supernode om dezelfde representatie te delen. Deze "uniformiteit" beperkt de per-node discriminatiekracht, met name in heterofiele settings waar aangrenzende nodes verschillende labels kunnen hebben.
2. Cluster-gebaseerde Restrictie (Cluster-Based Restriction): Methoden zoals Cluster-GCN beperken message passing tot enkel intra-cluster verbindingen, waardoor inter-cluster verbindingen worden weggegooid. Dit maakt efficiënte batching mogelijk door clusters als onafhankelijke subgrafen te behandelen. Echter, het doorsnijden van inter-cluster verbindingen elimineert langetermijnafhankelijkheden, wat de prestaties verslechtert bij taken die informatieaggregatie over vele hops vereisen.

Beide benaderingen vertrouwen op een decompositie van de graaf in groepen nodes, maar falen in het balanceren van de trade-off tussen het behoud van de langetermijnstructuur en het behoud van lokale node-discriminatie.

Methodologie: CoRe-GNN

De auteurs stellen CoRe-GNN (Coarsen and Restore) voor, een architectuur die is ontworpen om tegelijkertijd de nauwkeurigheidscel van grafvergroving en de langetermijnblindheid van Cluster-GCN aan te pakken.

Verenigde Matrixformulering

Het artikel stelt eerst een verenigd perspectief op gecomprimeerde grafen vast door ze te beschouwen als gestructureerde modificaties van de standaard propagatiematrix $S$.

• Coarsen-GNN vervangt $S$ door $\Pi S \Pi$, waarbij $\Pi = QP$ een blok-constante operator is die nodes naar supernodes en terug mapt.
• Cluster-GCN vervangt $S$ door $S_{intra}$, een blok-diagonaal matrix die enkel intra-cluster verbindingen behoudt.

De CoRe-GNN Architectuur

CoRe-GNN voert twee parallelle propagaties uit op elke laag, waarbij de vergroefde ruimte en de originele node-ruimte aan elkaar worden gekoppeld:

1. Inter-Cluster Propagatie (Vergroefd): Een term $S_{inter}^c$ opereert op de vergroefde graaf (supernodes). Dit vangt efficiënt langetermijn structurele informatie op.
2. Intra-Cluster Propagatie (Lokaal): Een term $S_{intra}$ opereert op de originele node-ruimte, waardoor per-node discriminatie binnen clusters behouden blijft.

De update regel voor laag $l$ is:
$$H^{(l)} = Q \sigma(S_{inter}^c P H^{(l-1)} \theta_c^{(l)}) + \sigma(S_{intra} H^{(l-1)} \theta^{(l)})$$
Hier zijn $P$ en $Q$ reductie- en lifting matrices afgeleid van de grafpartitie. De architectuur onderhoudt twee parallelle staten: $H_c^{(l)}$ in de vergroefde ruimte en $H^{(l)}$ in de originele ruimte. De gewichten $\theta^{(l)}$ en $\theta_c^{(l)}$ zijn onafhankelijk, waardoor het netwerk onderscheidende transformaties kan leren voor lokale en langetermijn interacties.

Batching Schema

Om te schalen naar grafen met miljoenen nodes, introduceert CoRe-GNN een natuurlijke batching strategie:

• Inter-cluster term: Wordt in elke stap berekend over alle $n$ supernodes (waarbij $n \ll N$), wat computationeel goedkoop is.
• Intra-cluster term: Wordt alleen berekend voor de clusters in de huidige batch $B$. Voor niet-gebatched supernodes wordt de intra-cluster term tijdens de training benaderd door een self-loop proxy in de vergroefde ruimte.
  Deze aanpak reduceert de geheugencomplexiteit naar $O(K(n+b)d)$, onafhankelijk van het totaal aantal nodes $N$, wat training mogelijk maakt op grafen die anders het GPU-geheugen zouden overschrijden.

Exacte Inferentie: Hoewel het batching schema voor training een benadering gebruikt, leiden de auteurs een niet-triviale exacte inferentieprocedure af die deze bottleneck vermijdt. In deze modus wordt de inter-cluster term berekend over alle supernodes op de GPU, terwijl de intra-cluster term cluster-voor-cluster wordt berekend, waarbij blokken op aanvraag van de CPU naar de GPU worden geladen en onmiddellijk weer worden weggegooid. Dit maakt exacte inferentie op zeer grote grafen mogelijk zonder de volledige computationele graaf over de lagen heen te bewaren.

Theoretische Garanties

De auteurs bewijzen dat CoRe-GNN garanties op benadering overneemt die vergelijkbaar zijn met grafvergroving. Specifiek begrenzen zij de fout tussen message passing op de originele graaf en CoRe-GNN met de Restricted Spectral Approximation (RSA) constante. De theoretische grens voor CoRe-GNN hangt af van de eigenschappen van de inter-cluster subgraaf ($S_{inter}$) in plaats van de volledige graaf, wat suggereert dat naarmate de vergroofingsratio toeneemt, de foutgrenzen kunnen verbeteren vergeleken met standaard vergroving.

Belangrijkste Bijdragen

1. Verenigd Perspectief: Het artikel biedt een matrixformulering die aantoont dat grafvergroving en Cluster-GCN complementaire gestructureerde modificaties zijn van de propagatiematrix, wat hun respectieve beperkingen verheldert.
2. CoRe-GNN Architectuur: Een nieuwe architectuur die inter-cluster (vergroefde) en intra-cluster (lokale) propagaties parallel koppelt, waardoor het verlies van discriminatie door vergroving en het verlies van langetermijn afhankelijkheden door clustering wordt gemitigeerd.
3. Schaalbaar Batching: Een natuurlijk batching schema dat CoRe-GNN in staat stelt om te trainen op grafen met miljoenen nodes, gekoppeld aan een exacte inferentieprocedure die de benadering vermijdt.
4. Theoretische Analyse: Afleiding van propagatie garanties voor CoRe-GNN, die aantonen dat het gladde signalen behoudt met constanten die afhankelijk zijn van de inter-cluster structuur.
5. Empirische Validatie: Uitgebreide evaluatie over homofiele, heterofiele, grootschalige en langetermijn benchmarks.

Experimentele Resultaten

De auteurs evalueerden CoRe-GNN op een diverse set datasets, waaronder:

• Homofiel: Cora, CiteSeer, PubMed.
• Heterofiel: Chameleon, Squirrel, Amazon Ratings.
• Grootschalig: ogbn-arxiv, Reddit, ogbn-products.
• Langetermijn: Paris en London wegennetwerken.

Belangrijkste Bevindingen:

• Prestaties: CoRe-GNN presteert consequent beter dan zowel Coarsen-GNN als Cluster-GCN baselines over alle categorieën.
• Langetermijn Taken: Op de Paris en London datasets bereikt CoRe-GNN de hoogste nauwkeurigheid, wat zijn vermogen aantoont om langetermijn afhankelijkheden te vangen die Cluster-GCN mist en de discriminatiekracht die pure Coarsen-GNN mist.
• Heterofilie: Op heterofiele datasets (bijv. Squirrel), presteert CoRe-GNN aanzienlijk beter dan Coarsen-GNN, dat moeite heeft wanneer nodes in dezelfde supernode verschillende labels hebben.
• Schaalbaarheid: Op grootschalige datasets zoals Reddit en ogbn-products lopen standaard GCN en niet-gebatched CoRe-GNN uit het geheugen (OOM). De gebatched variant van CoRe-GNN traint succesvol en bereikt een competitieve of superieure nauwkeurigheid vergeleken met Cluster-GCN.
• Ablatie: Experimenten bevestigen dat het gebruik van onafhankelijke gewichten voor de twee takken en het gebruik van de inter-cluster specifieke propagatiematrix ($S_{inter}^c$) in plaats van de volledige vergroefde matrix betere prestaties oplevert.

Betekenis en Claims

Het artikel claimt dat CoRe-GNN succesvol de voordelen van grafvergroving en cluster-gebaseerde restrictie verenigt. Door parallelle propagaties uit te voeren, overwint het de "complementaire mislukkingen" van bestaande schaalbare methoden: het verlies van node-niveau detail in vergroving en het doorsnijden van langetermijn afhankelijkheden in clustering.

De auteurs benadrukken dat CoRe-GNN een framework biedt dat:

1. Spectrale garanties behoudt voor het propageren van gladde signalen.
2. Per-node discriminatiekracht behoudt in heterofiele settings.
3. Langetermijn afhankelijkheden vangt die essentieel zijn voor complexe grafentaken.
4. Schaalt naar miljoenen nodes via een geheugenefficiënt batching schema.

Het werk suggereert dat de decompositie van de graaf in groepen niet een trade-off hoeft te zijn tussen nauwkeurigheid en schaalbaarheid; in plaats daarvan kan een multilevel aanpak beide bereiken. De auteurs merken op dat het framework momenteel beperkt is tot GNN's met vaste propagatiematrices (exclusief aandachtmechanismen) en dat toekomstig werk extensies naar residual connections en asynchrone federated learning scenario's kan verkennen.