Riepilogo Tecnico: Ripensamento delle GNN Pre-Propagazione

1. Enunciato del Problema

Le Reti Neurali su Grafi Pre-Propagazione (PP-GNN) offrono un'alternativa scalabile alle tradizionali GNN a Passaggio di Messaggi (MP-GNN) disaccoppiando la propagazione delle caratteristiche dalla trasformazione. Nelle PP-GNN, la diffusione sul grafo viene eseguita una sola volta come fase di pre-elaborazione per generare caratteristiche multi-hop, consentendo alla fase di training successiva di utilizzare trasformazioni dense e mini-batchabili senza dipendenze inter-nodo. Sebbene questo design migliori l'efficienza e si allinei con gli acceleratori hardware moderni ottimizzati per il calcolo denso, le PP-GNN mostrano un divario di prestazioni significativo rispetto alle MP-GNN, in particolare sui grafi eterofili (dove i nodi connessi hanno spesso etichette diverse).

Gli autori identificano due limitazioni progettuali primarie che contribuiscono a questo divario:

1. Limitazioni dell'Operatore di Diffusione: Le PP-GNN standard si affidano a operatori semplici (ad esempio, adiacenza normalizzata, cammini casuali) che agiscono come filtri passa-basso. Questi sono subottimali per i grafi eterofili, che spesso richiedono componenti ad alta frequenza o passa-banda. Inoltre, le basi di diffusione monomiali standard (potenze della matrice di diffusione) sono spesso mal condizionate e producono caratteristiche altamente correlate, limitando la qualità dell'approssimazione.
2. Propagazione in Un Solo Scatto: Le PP-GNN propagano le caratteristiche di input grezze una sola volta. A differenza delle MP-GNN, che intercalano iterativamente la propagazione con trasformazioni non lineari per affinare le rappresentazioni adattate al compito, le PP-GNN non possono aggiornare le caratteristiche propagate basandosi sugli stati nascosti in evoluzione durante l'addestramento.

2. Metodologia

Il documento propone una serie di miglioramenti per colmare il divario di accuratezza preservando al contempo l'efficienza di addestramento delle PP-GNN. L'approccio consta di tre componenti principali:

A. Operatori di Diffusione Robusti

Per affrontare le limitazioni delle basi di diffusione standard, gli autori introducono due basi di diffusione ortogonali e meglio condizionate per la fase di pre-elaborazione:

• Base dei Polinomi di Jacobi: Invece di utilizzare i monomi $\Phi^k$, gli autori impiegano i polinomi di Jacobi $P_k^{(\alpha, \beta)}(\tilde{L})$, dove $\tilde{L}$ è un Laplaciano spostato. I parametri $(\alpha, \beta)$ vengono calibrati in un singolo passaggio di pre-elaborazione leggero basato sulla densità spettrale del grafo (utilizzando momenti di Chebyshev stocastici) per allocare la risoluzione dove lo spettro del grafo si concentra. Ciò crea una base ortogonale che riduce la correlazione delle caratteristiche.
• Base Sottospazio di Lanczos/Krylov: Per catturare il contenuto spettrale specifico del canale, gli autori costruiscono un sottospazio di Krylov per ciascun canale di caratteristiche utilizzando l'iterazione di Lanczos. Questo genera un insieme di vettori e valori di Ritz che formano una banca di diffusione ortogonale e allineata al segnale. Questo metodo scompone le caratteristiche in componenti decorrelate, fornendo un sistema di coordinate più stabile per l'aggregazione sotto un budget di hop fisso.

B. Ri-Propagazione dello Stato Nascosto (HRP)

Per superare il limite della "propagazione in un solo scatto", gli autori introducono la Ri-Propagazione dello Stato Nascosto (HRP). Questo meccanismo ricoppia la propagazione delle caratteristiche con le rappresentazioni apprese:

• Meccanismo: L'addestramento è suddiviso in più fasi. Al termine di ciascuna fase, viene selezionata e staccata la migliore rappresentazione nascosta (prima della proiezione finale di output). Questo stato nascosto viene quindi ri-propagato attraverso l'operatore di diffusione per generare un nuovo insieme di caratteristiche multi-hop.
• Integrazione: Queste caratteristiche nascoste ri-propagate vengono mescolate con le caratteristiche precalcolate originali per formare l'input per la fase di addestramento successiva.
• Distinzione: Gli autori contrappongono esplicitamente l'HRP al riutilizzo basato sulle etichette (ad esempio, l'uso di logit o etichette one-hot come caratteristiche). Sostengono che la ri-propagazione di stati nascosti ad alta dimensionalità trasporta informazioni relazionali complementari oltre le probabilità di classe, mentre la propagazione delle etichette può introdurre scorciatoie o rumore, specialmente sui grafi eterofili.

C. Aggregatore di Hop Basato su RNN

Come miglioramento opzionale dell'efficienza, gli autori propongono di sostituire gli aggregatori Multi-Head Attention (MHA) (utilizzati in modelli come HOGA) con una Rete Neurale Ricorrente (RNN) per elaborare la sequenza delle caratteristiche di hop. Questo riduce il sovraccarico computazionale e l'uso di memoria mantenendo un'accuratezza comparabile.

3. Contributi Chiave

1. Adattamento di Basi di Diffusione Robuste: Il documento adatta le basi di diffusione a polinomi di Jacobi e sottospazio di Krylov al regime di pre-elaborazione delle PP-GNN. Queste basi migliorano il condizionamento delle caratteristiche precalcolate e abilitano risposte spettrali più ricche sotto un budget di hop fisso.
2. Ri-Propagazione dello Stato Nascosto (HRP): Un meccanismo leggero che affina iterativamente le PP-GNN ri-propagando stati nascosti intermedi, colmando efficacemente il divario tra la propagazione in un solo scatto e il passaggio di messaggi iterativo senza sacrificare la scalabilità.
3. Aggregazione Efficiente: Un aggregatore di hop basato su RNN che funge da alternativa computazionalmente più economica all'aggregazione basata sull'attenzione.
4. Validazione Empirica: Esperimenti estesi su 12 dataset (6 eterofili, 6 omofili) e 4 backbones PP-GNN (SIGN, HOGA, GAMLP, GARNN).

4. Risultati Sperimentali

I metodi proposti sono stati valutati su benchmark sia eterofili che omofili:

• Grafo Eterofili: Su sei dataset eterofili (inclusi Roman-Empire, Minesweeper e Pokec), le PP-GNN potenziate hanno ridotto significativamente il divario di accuratezza con le MP-GNN.
  • Il miglioramento medio dell'accuratezza di test rispetto alle PP-GNN di base è stato del +2,18% sui dataset eterofili.
  • I modelli potenziati hanno superato forti baseline MP-GNN (ad esempio, GraphSAGE, GAT) su 4 dei 6 grafi eterofili.
  • Sul dataset Roman-Empire, il divario di accuratezza tra MP-GNN e PP-GNN è stato ridotto da ~11% alla quasi parità.
• Grafo Omofili: I miglioramenti si sono trasferiti anche ai dataset omofili (ad esempio, Cora, Citeseer, OGBN-Arxiv), con un miglioramento medio del +1,96%. Le PP-GNN potenziate hanno superato le MP-GNN su 3 dei 6 dataset omofili.
• Studi di Ablazione:
  • Gli operatori di diffusione robusti da soli hanno fornito un guadagno medio di ~2,09% (validazione) / 1,99% (test).
  • L'HRP ha fornito un guadagno aggiuntivo di ~1,54% (validazione) / 1,61% (test).
  • L'HRP ha superato significativamente le strategie di input come etichetta e propagazione delle etichette, in particolare sui grafi eterofili dove la regolarità delle etichette è bassa.
• Efficienza:
  • L'operatore di Lanczos aggiunge un costo comparabile a pochi passaggi di diffusione standard.
  • L'HRP introduce un piccolo numero di fasi (tipicamente < 4, massimo 7), con la diffusione di ri-propagazione che rappresenta solo ~2% del tempo totale di addestramento.
  • L'aggregatore basato su RNN (GARNN) ha raggiunto un'accuratezza simile a HOGA ma con un tempo di addestramento significativamente ridotto (2,4s/epoch vs 8,4s/epoch su Pokec).
  • Complessivamente, le PP-GNN potenziate raggiungono un compromesso favorevole tra accuratezza e tempo di esecuzione, avvicinando la famiglia PP-GNN al fronte di Pareto delle MP-GNN.

5. Significato e Affermazioni

Il documento afferma che il framework proposto affronta con successo le limitazioni espressive delle GNN Pre-Propagazione senza tornare ai colli di bottiglia computazionali del passaggio di messaggi iterativo.

• Scalabilità vs. Espressività: Il lavoro dimostra che le PP-GNN non sacrificano intrinsecamente l'espressività per la scalabilità; piuttosto, il divario deriva da operatori di diffusione subottimali e dalla mancanza di affinamento iterativo. Utilizzando basi di diffusione robuste e HRP, le PP-GNN possono eguagliare o superare l'accuratezza delle MP-GNN mantenendo la loro efficienza di addestramento e le capacità di mini-batch.
• Applicabilità Generale: Sebbene motivato dalle sfide dell'eterofilia, i metodi si dimostrano vantaggiosi sia su strutture di grafi eterofili che omofili.
• Impatto Pratico: L'approccio offre una via per distribuire GNN altamente scalabili su grafi su larga scala (ad esempio, reti sociali, sistemi di raccomandazione) con prestazioni competitive rispetto ai modelli di passaggio di messaggi all'avanguardia, riducendo potenzialmente i costi computazionali e il consumo energetico per l'apprendimento su grafi su larga scala.

Gli autori mantengono una posizione modesta, notando che, sebbene i metodi migliorino le prestazioni, non introducono nuove modalità di dati né prevengono intrinsecamente i rischi etici a valle associati all'apprendimento su grafi (come l'amplificazione del pregiudizio), sottolineando la necessità di pratiche di ML responsabili nella distribuzione.