Riepilogo Tecnico: Rete Neurale a Grafi che sfrutta la Connettività di Classe di Ordine Superiore per Grafi Eterofili

Definizione del Problema

La classificazione dei nodi nelle Reti Neurali a Grafi (GNN) ha raggiunto un'elevata precisione nei grafi omofili, dove i nodi con etichette di classe simili tendono a connettersi. Tuttavia, le prestazioni degradano significativamente nei grafi eterofili, dove i nodi con etichette di classe diverse hanno maggiori probabilità di essere connessi.

Gli autori identificano un limite specifico nelle attuali GNN (incluse quelle derivate dalle Graph Convolutional Networks come GCN, GAT e i modelli avanzati per l'eterofilia come H2GCN e LINKX): esse trasformano il problema della classificazione dei nodi in una semplice mappatura dallo spazio di embedding allo spazio delle etichette di classe. Di conseguenza, questi modelli non riescono a catturare la connettività delle etichette di classe di ordine superiore — ovvero le relazioni strutturali tra le etichette di classe che si estendono su più salti tramite archi diretti. Sebbene alcuni metodi utilizzino una matrice di compatibilità delle classi per catturare la connettività di 1° ordine, essi non tengono conto delle complesse interazioni tra etichette a più salti frequentemente osservate nei grafi diretti del mondo reale (ad esempio, il dataset Texas, dove i nodi "Student" si connettono ai nodi "Department", i quali a loro volta si connettono ai nodi "Staff").

Metodologia

L'approccio proposto introduce un nuovo classificatore, il Label Context Classifier (LCC), e un framework per integrarlo con le GNN esistenti.

1. Label Context Classifier (LCC)

LCC è progettato per catturare la connettività delle etichette di classe di ordine superiore trattando le sequenze di etichette di classe lungo i cammini nel grafo come contesto, ispirandosi al modello word2vec Skip-gram. Il processo prevede tre fasi principali:

• Estrazione dei Cammini di Etichetta (Label Walk Extraction): Da un nodo target, vengono estratti quattro tipi distinti di cammini di etichetta. Un cammino di etichetta è una sequenza di etichette di classe in cui i nodi sono sostituiti dalle loro etichette. Se un nodo non è presente nell'insieme di addestramento, viene utilizzata un'etichetta nulla.
  • Cammino Forward (In avanti): Una ricerca in profondità (DFS) seguendo la direzione degli archi (Target $\to$ Figlio $\to$ Nipote).
  • Cammino Backward (All'indietro): Una ricerca in profondità seguendo la direzione inversa degli archi (Target $\to$ Genitore $\to$ Nonno).
  • Cammino Sibling (Fratello): Attraversa a ritroso verso un nodo genitore e poi in avanti verso i suoi altri figli (Target $\to$ Genitore $\to$ Fratello). Questo cattura la connettività tra i nodi che condividono un genitore comune.
  • Cammino Guardian (Tutore): Attraversa in avanti verso un nodo figlio e poi all'indietro verso i suoi altri genitori (Target $\to$ Figlio $\to$ Co-genitore). Questo cattura la connettività tra i nodi che condividono un figlio comune.
• Generazione dell'Embedding del Contesto di Etichetta (Label Context Embedding Generation): Utilizzando i cammini estratti, il modello apprende gli embedding che rappresentano il "contesto dell'etichetta". Un semplice Percettore Multistrato (MLP) a due strati viene addestrato per predire le etichette di contesto (le etichette successive nel cammino) dato l'input dell'etichetta del nodo target. Lo strato nascosto produce gli embedding del contesto dell'etichetta ($Z$).
• Addestramento del Classificatore: Il classificatore LCC finale è un MLP addestrato sulla concatenazione delle caratteristiche originali del nodo e degli embedding del contesto dell'etichetta derivati dai quattro tipi di cammino.

2. Integrazione con le GNN

Per sfruttare i punti di forza di entrambe le GNN tradizionali (che catturano informazioni sulle caratteristiche e sulla struttura locale) e l'LCC (che cattura la connettività delle etichette di classe di ordine superiore), gli autori propongono uno schema di integrazione adattivo:

• Addestramento Indipendente: Sia la GNN che l'LCC vengono addestrati indipendentemente sull'insieme di addestramento.
• Ponderazione Adattiva: L'importanza di ciascun modello è determinata dalla perdita di validazione (validation loss). I pesi ($w_{LCC}$ e $w_{GNN}$) sono calcolati come il reciproco della perdita di validazione, regolati da un parametro di temperatura ($T$).
• Predizione Ensemble: La predizione finale è una media ponderata degli output della GNN e dell'LCC. Questa integrazione non richiede l'addestramento di ulteriori modelli, ma solo il calcolo dei pesi in base alle prestazioni di validazione.

Contributi Chiave

1. Proposta di LCC: Un nuovo classificatore che stima le etichette dei nodi catturando la connettività delle etichette di classe di ordine superiore attraverso quattro cammini di etichetta direzionali (Forward, Backward, Sibling, Guardian).
2. Framework di Integrazione Adattiva: Un metodo per integrare l'LCC con qualsiasi GNN esistente, combinando adattivamente i pesi di importanza basati sulla perdita di validazione, senza costi di addestramento aggiuntivi.
3. Validazione Empirica: Risultati sperimentali che dimostrano come l'integrazione dell'LCC con le GNN superi i metodi State-of-the-Art (SOTA) su grafi diretti eterofili.

Risultati Sperimentali

Gli autori hanno valutato il loro metodo su sette dataset di grafi diretti eterofili: Cornell, Texas, Wisconsin, Chameleon, Squirrel, Roman-Empire e Amazon-Ratings.

• Miglioramento delle Prestazioni: I modelli integrati (ad es., H2GCN+LCC, LINKX+LCC, GloGNN+LCC) hanno ottenuto la massima accuratezza nella classificazione dei nodi in tutti i dataset rispetto alle GNN stand-alone, agli MLP e all'LCC da solo.
• Complementarità: I risultati indicano che LCC e GNN catturano proprietà di grafo differenti. Nella maggior parte dei casi, l'integrazione ha migliorato l'accuratezza rispetto ai singoli componenti.
• Efficacia dei Cammini di Etichetta: L'LCC ha superato significativamente un MLP vanilla (che utilizza solo le caratteristiche del nodo), confermando che gli embedding del contesto dell'etichetta catturano efficacemente la connettività delle etichette. In particolare, i guadagni di accuratezza hanno superato il 10% in dataset come Chameleon, Squirrel, Roman-Empire e Amazon-Ratings.
• Importanza del Tipo di Cammino: L'importanza di specifici tipi di cammino variava a seconda del dataset. Ad esempio, i cammini Guardian sono stati più critici per Chameleon, Squirrel e Amazon-Ratings, mentre i cammini Sibling sono stati più efficaci per Roman-Empire.
• Lunghezza del Cammino: L'aumento della lunghezza del cammino (per i cammini forward/backward) o l'utilizzo di cammini a 2 salti (sibling/guardian) ha generalmente migliorato le prestazioni, evidenziando la necessità di catturare la connettività di ordine superiore.

Significato e Rivendicazioni

Il documento sostiene che la debolezza primaria delle attuali GNN in contesti eterofili sia l'incapacità di modellare come le etichette di classe si connettono attraverso molteplici salti nei grafi diretti. Modellando esplicitamente queste relazioni di ordine superiore tramite i cammini di etichetta, l'LCC fornisce un segnale complementare alle GNN basate sulle caratteristiche.

Gli autori sottolineano che il loro approccio non richiede cambiamenti architettonici complessi alle GNN esistenti; piuttosto, offre un classificatore modulare che può essere combinato adattivamente con qualsiasi GNN per migliorarne le prestazioni. I risultati suggeriscono che sfruttare le informazioni strutturali tra le etichette di classe, invece di utilizzare solo le caratteristiche dei nodi o i vicini immediati, è fondamentale per una classificazione accurata nei grafi diretti eterofili. Il lavoro è supportato dai finanziamenti JSPS KAKENHI e JST ASPIRE.