Technische Samenvatting: Herbeoordeling van Pre-Propagation GNN's

1. Probleemstelling

Pre-Propagation Graph Neural Networks (PP-GNN's) bieden een schaalbaar alternatief voor traditionele Message-Passing GNN's (MP-GNN's) door feature-propagatie te ontkoppelen van transformatie. Bij PP-GNN's wordt grafdiffusie één keer uitgevoerd als een voorverwerkingsstap om multi-hop features te genereren, waardoor de daaropvolgende trainingsfase gebruik kan maken van dichte, mini-batchbare transformaties zonder inter-node afhankelijkheden. Hoewel dit ontwerp de efficiëntie verbetert en aansluit bij moderne hardware-accelerators die geoptimaliseerd zijn voor dichte berekeningen, vertonen PP-GNN's een aanzienlijke prestatiekloof ten opzichte van MP-GNN's, met name op heterofiele grafen (waar verbonden knopen vaak verschillende labels hebben).

De auteurs identificeren twee primaire ontwerpbeperkingen die bijdragen aan deze kloof:

1. Beperkingen van Diffusie-operatoren: Standaard PP-GNN's vertrouwen op eenvoudige operatoren (bijv. genormaliseerde adjacentie, random walks) die fungeren als low-pass filters. Deze zijn suboptimaal voor heterofiele grafen, die vaak hogere frequentie- of band-pass componenten vereisen. Bovendien zijn standaard monomiale diffusiebasissen (machten van de diffusiematrix) vaak slecht geconditioneerd en leveren ze sterk gecorreleerde features op, wat de benaderingskwaliteit beperkt.
2. Eén-shot Propagatie: PP-GNN's propageren ruwe input features slechts één keer. In tegenstelling tot MP-GNN's, die iteratief propagatie afwisselen met niet-lineaire transformaties om taak-geadaptede representaties te verfijnen, kunnen PP-GNN's de gepropageerde features niet bijwerken op basis van evoluerende hidden states tijdens het trainen.

2. Methodologie

Het artikel stelt een reeks verbeteringen voor om de nauwkeurigheidskloof te dichten terwijl de trainings-efficiëntie van PP-GNN's behouden blijft. De aanpak bestaat uit drie hoofdbestanddelen:

A. Robuuste Diffusie-operatoren

Om de beperkingen van standaard diffusiebasissen aan te pakken, introduceren de auteurs twee orthogonale, beter geconditioneerde diffusiebasissen voor de voorverwerkingsfase:

• Jacobi-Polynoom Basis: In plaats van monomen $\Phi^k$ te gebruiken, maken de auteurs gebruik van Jacobi-polynomen $P_k^{(\alpha, \beta)}(\tilde{L})$, waarbij $\tilde{L}$ een verschoven Laplaciaan is. De parameters $(\alpha, \beta)$ worden gekalibreerd in één enkele, lichtgewicht voorverwerkingsstap op basis van de spectrale dichtheid van de graf (met behulp van stochastische Chebyshev-momenten) om resolutie toe te wijzen waar het graf-spectrum zich concentreert. Dit creëert een orthogonale basis die feature-correlatie vermindert.
• Lanczos/Krylov-Subruimte Basis: Om kanaalspecifiek spectrale inhoud te vangen, construeren de auteurs een Krylov-subruimte voor elke feature-kanaal met behulp van de Lanczos-iteratie. Dit genereert een set Ritz-vectoren en -waarden die een orthogonale, signaal-gealigneerde diffusiebank vormen. Deze methode decomposeert features in gedecorreleerde componenten, waardoor een stabieler coördinatenstelsel voor aggregatie wordt geboden binnen een vast hop-budget.

B. Hidden-State Re-Propagation (HRP)

Om de "één-shot" beperking te overwinnen, introduceren de auteurs Hidden-State Re-Propagation (HRP). Dit mechanisme koppelt feature-propagatie weer aan geleerde representaties:

• Mechanisme: Training wordt opgesplitst in meerdere fasen. Aan het einde van elke fase wordt de beste hidden representatie (voor de uiteindelijke output-projectie) geselecteerd en losgekoppeld. Deze hidden state wordt vervolgens opnieuw gepropageerd via de diffusie-operator om een nieuwe set multi-hop features te genereren.
• Integratie: Deze opnieuw gepropageerde hidden features worden gemengd met de originele vooraf berekende features om de input te vormen voor de volgende trainingsfase.
• Onderscheid: De auteurs contrasteren HRP expliciet met label-gebaseerd hergebruik (bijv. het gebruik van logits of one-hot labels als features). Zij betogen dat het opnieuw propageren van hoog-dimensionale hidden states complementaire relationele informatie draagt die verder gaat dan klassen-kansen, terwijl label-propagatie shortcuts of ruis kan introduceren, vooral op heterofiele grafen.

C. RNN-gebaseerde Hop Aggregator

Als optionele efficiëntieverbetering stellen de auteurs voor Multi-Head Attention (MHA) aggregators (gebruikt in modellen zoals HOGA) te vervangen door een Recurrent Neural Network (RNN) om de reeks hop-features te verwerken. Dit verlaagt de rekenkundige overhead en het geheugengebruik terwijl vergelijkbare nauwkeurigheid wordt behouden.

3. Belangrijkste Bijdragen

1. Aanpassing van Robuuste Diffusiebasissen: Het artikel past Jacobi-polynoom- en Krylov-subruimte diffusiebasissen toe op het PP-GNN voorverwerkingsregime. Deze basissen verbeteren de conditionering van vooraf berekende features en maken rijkere spectrale responsen mogelijk binnen een vast hop-budget.
2. Hidden-State Re-Propagation (HRP): Een lichtgewicht mechanisme dat PP-GNN's iteratief verfijnt door tussentijdse hidden states opnieuw te propageren, waardoor de kloof tussen één-shot propagatie en iteratief message passing effectief wordt overbrugd zonder schaalbaarheid te offeren.
3. Efficiënte Aggregatie: Een RNN-gebaseerde hop aggregator die dient als een rekenkundig goedkoper alternatief voor attention-gebaseerde aggregatie.
4. Empirische Validatie: Uitgebreide experimenten over 12 datasets (6 heterofiel, 6 homofiel) en 4 PP-GNN backbones (SIGN, HOGA, GAMLP, GARNN).

4. Experimentele Resultaten

De voorgestelde methoden werden geëvalueerd op zowel heterofiele als homofiele benchmarks:

• Heterofiele Grafen: Op zes heterofiele datasets (waaronder Roman-Empire, Minesweeper en Pokec) verkleinden de verbeterde PP-GNN's de nauwkeurigheidskloof met MP-GNN's aanzienlijk.
  • De gemiddelde verbetering van de testnauwkeurigheid ten opzichte van de baseline PP-GNN's was +2,18% op heterofiele datasets.
  • De verbeterde modellen presteerden beter dan sterke MP-GNN baselines (bijv. GraphSAGE, GAT) op 4 van de 6 heterofiele grafen.
  • Op de Roman-Empire dataset werd de nauwkeurigheidskloof tussen MP-GNN's en PP-GNN's teruggebracht van ~11% tot bijna gelijkstand.
• Homofiele Grafen: De verbeteringen waren ook van toepassing op homofiele datasets (bijv. Cora, Citeseer, OGBN-Arxiv), met een gemiddelde verbetering van +1,96%. De verbeterde PP-GNN's presteerden beter dan MP-GNN's op 3 van de 6 homofiele datasets.
• Ablatie-studies:
  • Robuuste diffusie-operatoren alleen leverden een gemiddelde winst op van ~2,09% (validatie) / 1,99% (test).
  • HRP leverde een extra winst op van ~1,54% (validatie) / 1,61% (test).
  • HRP presteerde aanzienlijk beter dan label-als-input en label-propagatiestrategieën, met name op heterofiele grafen waar label-gladheid laag is.
• Efficiëntie:
  • De Lanczos-operator voegt een kostenplaatje toe dat vergelijkbaar is met een paar standaard diffusiestappen.
  • HRP introduceert een klein aantal fasen (doorgaans < 4, maximaal 7), waarbij de opnieuw gepropageerde diffusie slechts ~2% van de totale trainingsduur voor zijn rekening neemt.
  • De RNN-gebaseerde aggregator (GARNN) bereikte vergelijkbare nauwkeurigheid als HOGA, maar met aanzienlijk minder trainingsduur (2,4s/epoch versus 8,4s/epoch op Pokec).
  • Over het geheel genomen bereiken de verbeterde PP-GNN's een gunstige nauwkeurigheids-runtime trade-off, waardoor de PP-GNN-familie dichter bij de Pareto-grens van MP-GNN's komt.

5. Betekenis en Claims

Het artikel beweert dat het voorgestelde raamwerk de expressiviteitsbeperkingen van Pre-Propagation GNN's succesvol aanpakt zonder terug te vallen op de rekenkundige knelpunten van iteratief message passing.

• Schaalbaarheid versus Expressiviteit: Het werk toont aan dat PP-GNN's expressiviteit niet inherent opofferen voor schaalbaarheid; de kloof vloeit eerder voort uit suboptimale diffusie-operatoren en het ontbreken van iteratieve verfijning. Door het gebruik van robuuste diffusiebasissen en HRP kunnen PP-GNN's de nauwkeurigheid van MP-GNN's evenaren of overtreffen, terwijl ze hun trainings-efficiëntie en mini-batch mogelijkheden behouden.
• Algemene Toepasbaarheid: Hoewel gemotiveerd door de uitdagingen van heterofielie, blijken de methoden nuttig te zijn voor zowel heterofiele als homofiele grafstructuren.
• Praktische Impact: De aanpak biedt een weg om zeer schaalbare GNN's te implementeren op grootschalige grafen (bijv. sociale netwerken, aanbevelingssystemen) met prestaties die concurreren met state-of-the-art message-passing modellen, wat potentieel de rekenkosten en energieverbruik voor grootschalig grafenleren kan verminderen.

De auteurs behouden een bescheiden houding, en merken op dat hoewel de methoden de prestaties verbeteren, ze geen nieuwe data-modaliteiten introduceren en inherent geen downstream ethische risico's die gepaard gaan met grafenleren (zoals versterking van bias) voorkomen, waarmee de noodzaak wordt benadrukt van verantwoord ML-praktijken bij implementatie.