Improving Graph Few-shot Learning with Hyperbolic Space and Denoising Diffusion

1. Probleemstelling

Het paper adresseert de uitdagingen van Graph Few-Shot Learning (FSL), specifiek de taak van onzelftoezichtende (unsupervised) few-shot node-classificatie. Het doel is om knopen te classificeren in nieuwe categorieën met behulp van slechts een klein aantal gelabelde support-knopen ($M$-shot) en een groot aantal ongelabelde query-knopen, zonder te vertrouwen op gelabelde data tijdens de meta-training fase.

De auteurs identificeren twee kritieke beperkingen in bestaande Graph FSL-methoden:

1. Beperkingen van de Euclidische Ruimte: De meeste huidige modellen leren knooprepresentaties in Euclidische ruimte. Echter, real-world graafdata (bijvoorbeeld organisatiestructuren, academische taxonomieën) bezit vaak inherente hiërarchische of boom-achtige structuren. Euclidische geometrie lijdt aan significante vervorming bij het inbedden van dergelijke structuren, waardoor het faalt om de ware geometrische relaties vast te leggen.
2. Distributionele Bias & Overfitting: In de meta-testfase trainen modellen doorgaans classifiers op een zeer kleine support-set. Dit leidt tot twee problemen:
   • De empirische verdeling van de kleine support-set wijkt vaak aanzienlijk af van de ware onderliggende klassenverdeling (distributionele verschuiving).
   • Rechtstreeks trainen op schaarse data veroorzaakt ernstig overfitting, wat de generalisatie naar de query-set belemmert.

2. Methodologie: IMPRESS Framework

Het voorgestelde framework, IMPRESS (IMproves Praph Representation with Enhanced Space and Sampling), werkt in twee fasen: Meta-Training en Meta-Testing. Het integreert Hyperbolische Geometrie en Denoising Diffusion Modellen.

A. Meta-Training Fase

1. Hyperbolische Knoop Representatie Learning:

   • In plaats van Euclidische ruimte, leert het model knoop-embeddings in een Poincaré-bol (Hyperbolische ruimte), die op natuurlijke wijze hiërarchische structuren accommoderen.
   • Architectuur: Er wordt gebruik gemaakt van een Variational Graph Autoencoder (VGAE).
     • Encoder: Knoop-features worden geprojecteerd van Euclidische ruimte naar de raakruimte van de hyperbolische variëteit met behulp van de logaritmische afbeelding. Grafconvolutie (GCN) wordt uitgevoerd in de raakruimte. De resulterende embeddings worden via de exponentiële afbeelding teruggemapt naar de hyperbolische ruimte.
     • Decoder: Reconstructeert de graaf-adjacentiematrix met behulp van het inproduct van latente variabelen in de hyperbolische ruimte.
   • Doel: Het model wordt onzelftoezichtend getraind (alleen met graafstructuur en features) om de reconstructieverlies en de KL-divergentie te minimaliseren, waardoor het latente verdelingen leert die de hiërarchische geometrie behouden.

2. Prototype-Gestuurde Denoising Diffusion:

   • Omdat labels niet beschikbaar zijn tijdens meta-training, gebruikt het model onzelftoezichtende clustering (DBSCAN) op de geleerde latente embeddings om pseudo-labels toe te wijzen en klassen-prototypen te berekenen.
   • Een Denoising Diffusion Probabilistic Model (DDPM) wordt getraind op deze latente embeddings.
   • Conditionering: Het diffusieproces wordt geconditioneerd op de klassen-prototypen via een cross-attention mechanisme. Dit stelt het model in staat om de data-verdeling van elke klasse te leren zonder expliciete ground-truth labels, waardoor het voorbereid wordt om later samples voor nieuwe klassen te genereren.

B. Meta-Testing Fase

1. Embedding Generatie:
   • Voor een nieuwe taak met een kleine support-set ($S_{tes}$) en query-set ($Q_{tes}$), encodeert de vooraf getrainde VGAE de knopen in de hyperbolische latente ruimte.
   • Klassen-prototypen worden berekend vanuit de gelabelde support-set.
2. Data Augmentatie:
   • Het getrainde diffusiemodel genereert $D$ nieuwe synthetische knoop-embeddings voor elke nieuwe klasse, geconditioneerd op de prototypen van de support-set.
   • Deze gegenereerde samples worden gecombineerd met de originele support-set om een geaugmenteerde support-set ($\tilde{S}_{tes}$) te vormen, wat effectief de steekproefgrootte verhoogt van $M$ naar $M+D$.
3. Classificatie:
   • Een lineaire classifier wordt getraind op de geaugmenteerde support-set en geëvalueerd op de query-set.

3. Belangrijkste Bijdragen

1. Nieuw Framework (IMPRESS): Het eerste framework dat Hyperbolische Ruimte combineert voor structurele representatie en Denoising Diffusion voor verrijking van de verdeling in de context van onzelftoezichtend graph few-shot learning.
2. Theoretische Vooruitgang:
   • Bewezen dat hyperbolische encoding een strakkere generalisatiegrens ($O(e^{-\delta})$) biedt vergeleken met Euclidische encoding voor $\delta$-hyperbolische grafen.
   • Afgeleid een classificatiefoutgrens die aantoont dat de voorgestelde methode de fout vermindert door intra-klassen variantie te minimaliseren, inter-klassen afstand te maximaliseren en de Wasserstein-afstand tussen gegenereerde en ware verdelingen te reduceren.
3. Prototype-Gestuurde Diffusie: Geïntroduceerd een mechanisme om diffusiemodellen te sturen met behulp van klassen-prototypen in een onzelftoezichtende setting, waarmee de uitdaging wordt opgelost om samples te genereren voor nieuwe klassen zonder voorafgaande labelinformatie.
4. Empirische Superioriteit: Toonde consistent state-of-the-art prestaties over meerdere benchmarks.

4. Experimentele Resultaten

Het model werd geëvalueerd op zes benchmark datasets: CoraFull, Coauthor-CS, Cora, WikiCS, Cora-ML, CiteSeer, en de grootschalige ogbn-arxiv.

• Prestaties: IMPRESS presteerde consistent beter dan een breed scala aan baselines, waaronder:
  • Graph embedding methoden (GCN, SGC).
  • Traditioneel meta-learning (ProtoNet, MAML).
  • Graph meta-learning (Meta-GNN, GPN, TEG, COSMIC).
  • Onzelftoezichtend graph meta-learning (VNT, NaQ).
  • Voorbeeld: Op ogbn-arxiv (5-way 3-shot) bereikte IMPRESS 61,11% nauwkeurigheid, wat de nummer twee (COSMIC met 52,98%) aanzienlijk versloeg. Op CoraFull bereikte het 85,49% (tegenover 75,18% voor de volgende beste).
• Ablatie Studies:
  • Het verwijderen van het hyperbolische component (w/o hyp) veroorzaakte een significante daling in prestaties, wat de noodzaak van hyperbolische geometrie voor hiërarchische data bevestigt.
  • Het verwijderen van het diffusiecomponent (w/o dif) degradeerde ook de prestaties, wat valideert dat data-augmentatie via diffusie effectief label-schaarste en distributionele bias mitigeert.
• Hyperparameter Gevoeligheid:
  • De optimale kromming ($c$) bleek te liggen tussen 0,5 en 2,0.
  • Het aantal gegenereerde samples ($D$) toonde een omgekeerde-U trend, met optimale prestaties bij $D=50$.

5. Betekenis

Dit werk overbrugt de kloof tussen geometrisch deep learning en generatieve modellering voor graafdata.

• Geometrisch Inzicht: Het valideert dat real-world grafen beter gemodelleerd kunnen worden in hyperbolische ruimte, en biedt een theoretische en praktische oplossing voor het "vervormings"-probleem van Euclidische embeddings.
• Oplossing voor Data-Schaarste: Door diffusiemodellen in te zetten om hoogwaardige, klasse-geconditioneerde samples te synthetiseren, biedt het een robuuste strategie om de "kleine data" bottleneck in few-shot learning te overwinnen, overfitting te reduceren en beslissingsgrenzen te verbeteren.
• Onzelftoezichtende Capabiliteit: Het vermogen om diffusiemodellen te trainen met behulp van pseudo-labels afgeleid van onzelftoezichtende clustering maakt het framework zeer toepasbaar in real-world scenario's waar gelabelde data duur of niet-bestaand is.