Mini-Batch Class Composition Bias in Link Prediction

1. Enunciazione del Problema

Il paper affronta una disconnessione critica tra i compiti di Link Prediction e Node Classification nelle Graph Neural Networks (GNN).

• L'Intuizione: Si ipotizza generalmente che le GNN addestrate per la previsione dei link dovrebbero apprendere rappresentazioni del grafo coerenti con quelle apprese per la classificazione dei nodi. Ciò si basa sul presupposto che, nei grafi omofili (dove i nodi della stessa classe sono connessi), i pattern strutturali utilizzati per prevedere i link dovrebbero intrinsecamente codificare informazioni sulla classe del nodo.
• La Realtà: Gli autori dimostrano che questa intuizione spesso fallisce nella pratica. I modelli popolari di previsione dei link spesso non riescono ad apprendere caratteristiche significative relative alla classe del nodo. Invece, apprendono un euristica banale dipendente dal mini-batch, abilitata dai livelli di Batch Normalization (BN).
• Il Meccanismo del Fallimento: L'addestramento standard per la previsione dei link costruisce mini-batch con un rapporto fisso tra archi positivi (esistenti) e negativi (non esistenti), tipicamente 50/50. Il livello di Batch Normalization calcola le statistiche (media e varianza) sul batch. Poiché la distribuzione delle classi è fissa, il livello BN permette al modello di "barare" apprendendo una mappatura semplice basata sulla composizione del batch piuttosto che sulla topologia effettiva del grafo o sulle caratteristiche dei nodi. Ciò porta a metriche di performance gonfiate (es. Hits@K) che non riflettono una vera comprensione delle proprietà sottostanti del grafo.

2. Metodologia

A. Analisi Teorica del Bias

Gli autori derivano matematicamente come la Batch Normalization faciliti questo bias:

1. In un mini-batch standard con $K_+$ archi positivi e $K_-$ archi negativi (dove $K_+ \approx K_-$), il livello BN normalizza le attivazioni in base alla media del batch $\mu = K_+/K$ e alla varianza $\sigma^2 = K_+K_-/K^2$.
2. Questa normalizzazione collassa tutti gli archi positivi in un singolo valore costante e tutti gli archi negativi in un altro valore costante all'interno del batch.
3. Una successiva trasformazione affine ($\gamma \hat{a} + \beta$) può facilmente separare queste due costanti, permettendo al modello di prevedere l'esistenza di un arco basandosi esclusivamente sulla composizione del batch piuttosto che su caratteristiche apprese.

B. Soluzione Proposta: Mini-Batching Corretto dal Bias

Per costringere il modello ad apprendere caratteristiche robuste (ovvero caratteristiche rilevanti per la classe del nodo) invece di euristiche basate sul batch, gli autori propongono un nuovo regime di addestramento:

• Composizione delle Classi Randomizzata: Invece di fissare il rapporto tra archi positivi e negativi, la frazione di archi positivi ($p$) in ogni mini-batch viene campionata casualmente da una distribuzione uniforme: $p \sim U\{1, \dots, K-1\}$.
• Effetto: Questa randomizzazione garantisce che le statistiche del batch (media e varianza) calcolate dal livello BN varino in modo imprevedibile tra i batch. Di conseguenza, una regola decisionale basata esclusivamente sulla composizione del batch diventa instabile ed inefficace, costringendo la rete a fare affidamento sulle caratteristiche reali degli archi e sugli embedding dei nodi per minimizzare la perdita.

C. Metriche di Valutazione

Per verificare che i modelli stiano apprendendo caratteristiche relative alla classe del nodo, gli autori introducono metodi di valutazione specifici:

1. Trace Ratio (TR): Utilizzato per misurare la separabilità degli embedding degli archi in base all'etichetta di classe del nodo sorgente. Un TR più alto indica un migliore allineamento tra le rappresentazioni degli archi e le classi dei nodi.
2. Aggregazione degli Embedding dei Nodi: Poiché i predittori di link producono embedding degli archi ($Z_2$), gli autori li aggregano nuovamente ai nodi calcolando la media degli embedding di tutti gli archi incidenti per un dato nodo ($x'_v$).
3. Clustering & NMI: Eseguono un clustering $k$-means su questi embedding dei nodi aggregati e misurano l'Normalized Mutual Information (NMI) rispetto alle etichette vere dei nodi. Un NMI elevato indica che il predittore di link ha appreso rappresentazioni utili per la classificazione dei nodi.

3. Contributi Chiave

1. Identificazione di un Bias Nascosto: Il paper rivela che i modelli standard di previsione dei link sfruttano spesso il rapporto fisso positivo/negativo nei mini-batch tramite Batch Normalization, portando a un apprendimento "di scorciatoia" che bypassa l'estrazione complessa di caratteristiche.
2. Dimostrazione Teorica: Fornisce una derivazione matematica che mostra come i livelli BN collassino le attivazioni in costanti dipendenti dalla classe quando la composizione del batch è fissa.
3. Schema di Addestramento Corretto dal Bias: Introduce una modifica semplice e indipendente dall'architettura (randomizzazione della composizione delle classi nel mini-batch) che elimina questa euristica.
4. Validazione Empirica: Dimostra che, sebbene questa correzione possa ridurre leggermente l'accuratezza grezza di previsione dei link (Hits@K), migliora significativamente l'allineamento delle rappresentazioni apprese con le caratteristiche della classe del nodo, dimostrando che i modelli stavano precedentemente "barando".

4. Risultati Sperimentali

Gli autori hanno valutato sei modelli popolari (BUDDY, ELPH, GCN, NCN, NEOGNN, GraphSAGE) su più dataset (Cora, Citeseer, Pubmed, CS, Computers, Photo, ogbl-collab, ogbl-ppa).

• Performance di Link Prediction (Hits@100):

  • Come previsto, la rimozione del bias ha generalmente causato una diminuzione dei punteggi Hits@100.
  • Esempio: Sul dataset ogbl-collab, GCN è sceso da 42.0 a 16.3. Su Computers, BUDDY è sceso da 56.0 a 42.5.
  • Interpretazione: Il calo conferma che l'alta performance originale era parzialmente dovuta all'euristica sfruttabile del batch.

• Allineamento delle Rappresentazioni (Trace Ratio):

  • In quasi tutti i modelli e dataset, il Trace Ratio è aumentato significativamente sotto lo schema corretto dal bias.
  • Esempio: Su Cora, il TR di GCN è aumentato da 0.039 a 0.165. Su CS, il TR di BUDDY è salito da 0.225 a 0.728.
  • Interpretazione: I modelli stanno ora apprendendo rappresentazioni degli archi altamente separabili per classe del nodo.

• Allineamento alla Classificazione dei Nodi (NMI):

  • Quando gli embedding degli archi sono stati aggregati ai nodi, i punteggi NMI sono migliorati drammaticamente con la correzione del bias.
  • Esempio: Su CS, l'NMI di BUDDY è aumentato da 0.218 a 0.621. Su Cora, l'NMI di ELPH è salito da 0.193 a 0.414.
  • Interpretazione: Ciò conferma che i predittori di link, se addestrati correttamente, possono apprendere caratteristiche predittive delle classi dei nodi, validando l'intuizione iniziale che era precedentemente oscurata dal bias.

• Studio di Ablazione:

  • Quando i livelli di Batch Normalization sono stati rimossi completamente, il divario di performance tra l'addestramento "Originale" e quello "Corretto dal Bias" è scomparso (TR e Hits@K sono rimasti simili). Ciò conferma che la Batch Normalization è l'abilitatore del bias.

5. Significato e Implicazioni

• Rivalutazione dello SOTA: Il paper suggerisce che i benchmark attuali di stato dell'arte per la previsione dei link potrebbero sovrastimare la capacità delle GNN di apprendere rappresentazioni generalizzate del grafo. Molti modelli potrebbero ottenere punteggi elevati sfruttando artefatti di addestramento piuttosto che apprendendo proprietà strutturali.
• Trasferibilità del Compito: I risultati supportano l'ipotesi che la previsione dei link e la classificazione dei nodi condividano uno spazio di rappresentazione sottostante comune, ma questo è accessibile solo se il regime di addestramento previene l'apprendimento di scorciatoie.
• Raccomandazione Pratica: Gli autori raccomandano l'adozione del mini-batching corretto dal bias (randomizzazione dei rapporti positivi/negativi) come pratica standard. Ciò garantisce che i modelli apprendano caratteristiche robuste, trasferibili tra compiti e che riflettano realmente le proprietà strutturali e semantiche del grafo, anche a costo di una leggera riduzione delle metriche grezze di previsione dei link.