Mini-Batch Class Composition Bias in Link Prediction

1. Probleemstelling

Het artikel adresseert een kritieke disconnectie tussen de taken Link Prediction en Node Classification in Graph Neural Networks (GNN's).

• De Intuïtie: Er wordt algemeen verondersteld dat GNN's die zijn getraind voor link prediction, grafrepresentaties moeten leren die consistent zijn met die welke worden geleerd voor node classification. Dit is gebaseerd op de premisse dat in homofiele grafen (waarbij knopen van dezelfde klasse met elkaar verbonden zijn), de structurele patronen die worden gebruikt om links te voorspellen, inherent knoop-klasse-informatie moeten coderen.
• De Realiteit: De auteurs tonen aan dat deze intuïtie in de praktijk vaak faalt. Populaire modellen voor link prediction leren vaak geen betekenisvolle kenmerken op knoop-niveau. In plaats daarvan leren ze een triviale, mini-batch-afhankelijke heuristiek die mogelijk wordt gemaakt door Batch Normalization (BN)-lagen.
• Het Mechanisme van Falen: Standaard training voor link prediction bouwt mini-batches op met een vaste verhouding van positieve (bestaande) en negatieve (niet-bestaande) randen (doorgaans 50/50). De Batch Normalization-laag berekent statistieken (gemiddelde en variantie) over de batch. Omdat de klassenverdeling vaststaat, laat de BN-laag het model toe om te "valsspelen" door een eenvoudige mapping te leren die gebaseerd is op de samenstelling van de batch in plaats van de daadwerkelijke graf-topologie of knoopkenmerken. Dit leidt tot opgeblazen prestatie-metrics (bijv. Hits@K) die geen echte begrip van de onderliggende eigenschappen van de graf weerspiegelen.

2. Methodologie

A. Theoretische Analyse van de Bias

De auteurs leiden wiskundig af hoe Batch Normalization deze bias faciliteert:

1. In een standaard mini-batch met $K_+$ positieve randen en $K_-$ negatieve randen (waarbij $K_+ \approx K_-$), normaliseert de BN-laag activaties op basis van het batch-gemiddelde $\mu = K_+/K$ en de variantie $\sigma^2 = K_+K_-/K^2$.
2. Deze normalisatie doet alle positieve randen in de batch samenvallen tot één constante waarde en alle negatieve randen tot een andere constante waarde.
3. Een daaropvolgende affiene transformatie ($\gamma \hat{a} + \beta$) kan deze twee constanten eenvoudig scheiden, waardoor het model het bestaan van een rand kan voorspellen uitsluitend op basis van de batch-samenstelling in plaats van geleerde kenmerken.

B. Voorgestelde Oplossing: Bias-Corrected Mini-Batching

Om het model te dwingen robuuste kenmerken te leren (d.w.z. kenmerken die relevant zijn voor de knoop-klasse) in plaats van batch-heuristieken, stellen de auteurs een nieuw trainingsregime voor:

• Geraandomiseerde Samenstelling van Klassen: In plaats van de verhouding van positieve tot negatieve randen vast te leggen, wordt het aandeel positieve randen ($p$) in elke mini-batch willekeurig bemonsterd uit een uniforme verdeling: $p \sim U\{1, \dots, K-1\}$.
• Effect: Deze randomisatie zorgt ervoor dat de door de BN-laag berekende batch-statistieken (gemiddelde en variantie) onvoorspelbaar variëren tussen batches. Bijgevolg wordt een beslissingsregel die uitsluitend gebaseerd is op de batch-samenstelling instabiel en inefficiënt, waardoor het netwerk gedwongen wordt om zich te baseren op de daadwerkelijke randkenmerken en knoop-embeddings om de loss te minimaliseren.

C. Evaluatiemetrics

Om te verifiëren dat de modellen knoop-klasse-kenmerken leren, introduceren de auteurs specifieke evaluatiemethoden:

1. Trace Ratio (TR): Gebruikt om de scheidbaarheid van rand-embeddings te meten op basis van het klasse-label van de bronknoop. Een hogere TR geeft een betere uitlijning aan tussen rand-representaties en knoop-klassen.
2. Aggregatie van Knoop-Embeddings: Aangezien link-predictors rand-embeddings ($Z_2$) outputten, aggregeren de auteurs deze terug naar knopen door de embeddings van alle incidente randen voor een gegeven knoop te middelen ($x'_v$).
3. Clustering & NMI: Ze voeren $k$-means clustering uit op deze geaggregeerde knoop-embeddings en meten Normalized Mutual Information (NMI) tegenover ground-truth knooplabels. Een hoge NMI geeft aan dat de link-predictor representaties heeft geleerd die nuttig zijn voor node classification.

3. Belangrijkste Bijdragen

1. Identificatie van een Verborgen Bias: Het artikel onthult dat standaard modellen voor link prediction vaak de vaste verhouding positief/negatief in mini-batches uitbuiten via Batch Normalization, wat leidt tot "shortcut"-learning dat complexe kenmerkextractie omzeilt.
2. Theoretisch Bewijs: Biedt een wiskundige afleiding die aantoont hoe BN-lagen activaties laten samenvallen tot klassen-afhankelijke constanten wanneer de batch-samenstelling vaststaat.
3. Bias-Corrected Trainingschema: Introduceert een eenvoudige, architectuur-onafhankelijke modificatie (randomiseren van de mini-batch-klassen-samenstelling) die deze heuristiek elimineert.
4. Empirische Validatie: Toont aan dat hoewel deze correctie de ruwe nauwkeurigheid van link prediction (Hits@K) lichtjes kan verminderen, het de uitlijning van geleerde representaties met knoop-klasse-kenmerken significant verbetert, wat bewijst dat de modellen eerder "valsspelen".

4. Experimentele Resultaten

De auteurs evalueerden zes populaire modellen (BUDDY, ELPH, GCN, NCN, NEOGNN, GraphSAGE) over meerdere datasets (Cora, Citeseer, Pubmed, CS, Computers, Photo, ogbl-collab, ogbl-ppa).

• Prestaties Link Prediction (Hits@100):

  • Zoals verwacht veroorzaakte het verwijderen van de bias over het algemeen een daling in Hits@100-scores.
  • Voorbeeld: Op de ogbl-collab dataset daalde GCN van 42,0 naar 16,3. Op Computers daalde BUDDY van 56,0 naar 42,5.
  • Interpretatie: De daling bevestigt dat de oorspronkelijke hoge prestaties deels te danken waren aan de uitbuitbare batch-heuristiek.

• Uitlijning van Representaties (Trace Ratio):

  • Bij bijna alle modellen en datasets nam de Trace Ratio significant toe onder het bias-corrected schema.
  • Voorbeeld: Op Cora steeg de TR van GCN van 0,039 naar 0,165. Op CS sprong de TR van BUDDY van 0,225 naar 0,728.
  • Interpretatie: De modellen leren nu rand-representaties die sterk scheidbaar zijn per knoop-klasse.

• Uitlijning Node Classification (NMI):

  • Wanneer rand-embeddings werden geaggregeerd naar knopen, verbeterden de NMI-scores dramatisch met bias-correctie.
  • Voorbeeld: Op CS steeg de NMI van BUDDY van 0,218 naar 0,621. Op Cora steeg de NMI van ELPH van 0,193 naar 0,414.
  • Interpretatie: Dit bevestigt dat link-predictors, wanneer ze correct worden getraind, wel kenmerken kunnen leren die voorspellend zijn voor knoop-klassen, wat de initiële intuïtie valideert die eerder werd gemaskeerd door de bias.

• Ablatie-studie:

  • Wanneer Batch Normalization-lagen volledig werden verwijderd, verdween het prestatieverschil tussen "Origineel" en "Bias-Corrected" training (TR en Hits@K bleven vergelijkbaar). Dit bevestigt dat Batch Normalization de enableur van de bias is.

5. Betekenis en Implicaties

• Herwaardering van SOTA: Het artikel suggereert dat huidige state-of-the-art benchmarks voor link prediction de capaciteit van GNN's om gegeneraliseerde graf-representaties te leren, mogelijk overschatten. Veel modellen bereiken hoge scores door trainingsartefacten uit te buiten in plaats van structurele eigenschappen te leren.
• Taak-Transferabiliteit: De bevindingen ondersteunen de hypothese dat link prediction en node classification een gemeenschappelijke onderliggende representatieruimte delen, maar deze is alleen toegankelijk als het trainingsregime shortcut-learning voorkomt.
• Praktische Aanbeveling: De auteurs raden aan bias-corrected mini-batching (randomiseren van verhoudingen positief/negatief) te adopteren als standaardpraktijk. Dit zorgt ervoor dat modellen kenmerken leren die robuust zijn, overdrachtelijk zijn tussen taken, en de structurele en semantische eigenschappen van de graf werkelijk weerspiegelen, zelfs als dit gepaard gaat met een lichte kost voor de ruwe metrics van link prediction.