GCN / GAT / GraphSAGE
- Anno
- 2017–2018 (major variants)
- Tipo
- Deep learning on graph-structured data
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Una Graph Neural Network (GNN) è un'architettura di deep learning che opera direttamente su dati strutturati a grafo, combinando le feature dei nodi con informazioni strutturali attraverso un passaggio iterativo di messaggi tra vicini.
Le tre varianti canoniche — la Graph Convolutional Network (GCN) introdotta da Kipf e Welling nel 2017, la Graph Attention Network (GAT) introdotta da Veličković et al. nel 2018, e GraphSAGE — differiscono nel modo in cui aggregano le informazioni dei vicini: la GCN applica una convoluzione spettrale sull'intera adiacenza, la GAT pondera i vicini con punteggi di attenzione appresi, e GraphSAGE campiona e aggrega vicinanze locali in modo induttivo, consentendo la generalizzazione a nodi non visti.
L’intuizione alla base del metodo
Si pensi a ogni nodo di un grafo come a una persona in una rete sociale. Quella persona ha il proprio profilo (feature), ma anche chi conosce dice molto di lei. Una GNN consente a ogni nodo di raccogliere ripetutamente messaggi dai suoi vicini, mescolare tali messaggi con le proprie informazioni e aggiornare la propria rappresentazione — strato per strato. Dopo alcuni cicli di questo scambio in stile pettegolezzo, l'embedding di ogni nodo riflette non solo se stesso, ma anche il sottografo locale circostante. La GCN lo fa con una media simmetrica fissa dei vicini; la GAT decide quali vicini fidarsi di più apprendendo pesi di attenzione; GraphSAGE campiona un sottoinsieme fisso di vicini e apprende una funzione di aggregazione che può essere applicata a nodi mai visti prima.
Storia
Le basi per l'applicazione di reti neurali ai grafi sono state poste da Scarselli et al. (2009), ma l'era moderna delle GNN è iniziata con la Graph Convolutional Network (2017) di Kipf e Welling, che ha semplificato la convoluzione spettrale su grafi in un'approssimazione efficiente di primo ordine utilizzando la moltiplicazione normalizzata simmetrica dell'adiacenza. Un anno dopo, Veličković et al. (2018) hanno introdotto le Graph Attention Networks, sostituendo la media fissa della GCN con coefficienti di attenzione apprendibili su ogni arco — consentendo al modello di ponderare selettivamente i vicini. Contemporaneamente, Hamilton et al. (2017) hanno proposto GraphSAGE, un framework induttivo che campiona vicinanze di dimensione fissa e apprende funzioni di aggregazione trasferibili a nodi non visti, rendendo le GNN pratiche per grafi grandi e dinamici. Questi tre articoli hanno stabilito il paradigma del passaggio di messaggi che ora sottende la maggior parte della ricerca sulle GNN.
Quando usarlo
Utilizzare una GNN quando i dati sono naturalmente strutturati a grafo — reti sociali, reti di citazioni, grafi molecolari, grafi di conoscenza, o qualsiasi contesto in cui le relazioni tra entità portano un segnale predittivo. È necessaria una matrice di feature dei nodi e una lista di archi. È richiesto un minimo di circa 50 nodi per un addestramento significativo. Le GNN sono applicabili alla classificazione dei nodi (predire un'etichetta per ciascun nodo), alla predizione di archi (inferire archi mancanti) e alla classificazione dei grafi (assegnare un'etichetta a un intero grafo). L'assunzione di omofilia — nodi connessi tendono a condividere la stessa etichetta — è sfruttata implicitamente da GCN e GAT standard; se il vostro grafo è eterofilico, considerate architetture progettate per tale contesto. Per grafi di grandi dimensioni, l'addestramento full-batch è proibitivo in termini di memoria e sono necessari campionamenti di vicinato in mini-batch (stile GraphSAGE). Se il vostro grafo ha meno di 20 nodi, le metriche di centralità tradizionali sono una scelta più appropriata.
Limiti e considerazioni
- Sovra-smussamento (Over-smoothing): l'impilamento di molti strati GNN spinge tutti gli embedding dei nodi verso un valore comune, limitando la profondità effettiva a circa 2–4 strati in pratica.
- Scalabilità: GCN e GAT in full-batch richiedono di mantenere l'intera matrice di adiacenza e la matrice delle feature in memoria, il che è infattibile per grafi molto grandi senza campionamento o partizionamento.
- L'assunzione di omofilia incorporata nell'aggregazione standard degrada le prestazioni su grafi eterofilici dove i vicini tendono ad avere etichette diverse.
- È richiesto un numero minimo di circa 50 nodi; meno nodi lasciano al modello un segnale insufficiente per apprendere rappresentazioni significative.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Sfrutta congiuntamente sia le feature dei nodi che la topologia del grafo, superando le prestazioni di metodi che utilizzano solo una delle due.
- Il meccanismo di attenzione di GAT fornisce punteggi di importanza per arco, aggiungendo interpretabilità all'aggregazione.
- GraphSAGE è induttivo e può generalizzare a nodi e grafi non visti durante l'addestramento, consentendo il deployment su reti in crescita.
- Un framework unificato di passaggio di messaggi copre la classificazione dei nodi, la predizione di archi e la classificazione dei grafi con la stessa architettura di base.
Applicazioni
- Classificazione dei nodi in reti di citazioni — predire l'argomento di un articolo basandosi sul suo contenuto e sui link di citazione.
- Scoperta di farmaci — predire le proprietà molecolari trattando gli atomi come nodi e i legami chimici come archi.
- Sistemi di raccomandazione — modellare utenti e articoli come un grafo bipartito e predire le interazioni utente-articolo tramite predizione di archi.
- Rilevamento frodi in reti di transazioni finanziarie — identificare nodi anomali basandosi sulle loro feature e sulla struttura del vicinato.
- Completamento di grafi di conoscenza — inferire relazioni mancanti tra entità in basi di conoscenza su larga scala.
Come funziona
Come funziona
Il grafo è definito da una matrice di feature dei nodi X (una riga per nodo, una colonna per attributo) e una lista di archi (o matrice di adiacenza) A. Archi non diretti sono standard per GCN e GAT; GraphSAGE supporta anche grafi diretti. I self-loop vengono tipicamente aggiunti ad A in modo che ogni nodo sia incluso nella propria aggregazione.
Le feature grezze dei nodi vengono normalizzate e, se necessario, incorporate in uno spazio vettoriale continuo. Le feature degli archi, se presenti, possono essere incorporate come segnali aggiuntivi. Il risultato è una matrice di feature densa che ogni strato GNN trasformerà.
Ogni strato GNN calcola una nuova rappresentazione del nodo aggregando le feature dei vicini di un nodo e combinandole con le feature del nodo stesso attraverso una matrice di pesi apprendibile e una funzione di attivazione non lineare. La GCN applica una moltiplicazione normalizzata dell'adiacenza (convoluzione spettrale); la GAT calcola coefficienti di attenzione softmax per ogni arco, in modo che i vicini influenti contribuiscano maggiormente; GraphSAGE campiona casualmente un vicinato di dimensione fissa e applica un aggregatore differenziabile (media, LSTM o pooling). L'impilamento di L strati consente alle informazioni di fluire fino a L hop di distanza, ma l'impilamento di troppi strati causa sovra-smussamento (over-smoothing), dove tutti gli embedding dei nodi convergono allo stesso valore.
Gli embedding finali dei nodi vengono immessi in una testa specifica per il task. Per la classificazione dei nodi, uno strato softmax assegna probabilità di classe a ciascun nodo. Per la predizione di archi, un prodotto scalare o un MLP valuta la probabilità di un arco tra due embedding di nodi. Per la classificazione dei grafi, un pooling globale (somma, media o gerarchico) aggrega tutti gli embedding dei nodi in un singolo vettore a livello di grafo prima dello strato di classificazione.
Le prestazioni del modello vengono misurate su un set di test tenuto da parte, utilizzando metriche appropriate per il task: accuratezza o F1 per la classificazione di nodi e grafi, AUC-ROC per la predizione di archi. Poiché i dataset di grafi hanno spesso dimensioni limitate, la valutazione trasduttiva (maschere di addestramento/validazione/test sullo stesso grafo) o split induttivi (sottografi disgiunti) dovrebbero corrispondere allo scenario di deployment.
Errori comuni
- Aggiungere troppi strati GNN causa sovra-smussamento: tutti gli embedding dei nodi convergono e il modello perde potere discriminatorio. Mantenere il numero di strati a 2–4 e monitorare la varianza degli embedding.
- L'addestramento sul grafo completo senza mini-batch è proibitivo in termini di memoria per reti di grandi dimensioni; utilizzare campionamento di vicini in stile GraphSAGE o partizionamento del grafo per grafi con più di qualche migliaio di nodi.
- Applicare una GCN addestrata trasduttivamente a nodi nuovi e non visti al momento dell'inferenza è errato; utilizzare un metodo induttivo come GraphSAGE se il deployment richiede generalizzazione a nuovi nodi.
- Ignorare l'assunzione di omofilia su grafi eterofilici produce risultati scarsi; ispezionare il coefficiente di assortatività del grafo prima di scegliere una variante GNN standard.
- Con meno di 20 nodi, l'addestramento GNN produce rappresentazioni inaffidabili; preferire l'analisi convenzionale della centralità della rete in tale regime.
Domande frequenti
Quale variante GNN dovrei scegliere per iniziare — GCN, GAT, o GraphSAGE?
La GCN è il baseline più semplice e funziona bene su grafi omofilici di piccole-medie dimensioni dove tutti i nodi sono noti al momento dell'addestramento. La GAT è preferibile quando l'importanza dei vicini varia e si desiderano pesi di attenzione interpretabili. GraphSAGE è la scelta giusta quando è necessario generalizzare a nodi non visti durante l'addestramento o quando il grafo è troppo grande per l'elaborazione full-batch.
Cos'è il sovra-smussamento e come posso evitarlo?
Il sovra-smussamento si verifica quando molti strati GNN causano la convergenza di tutti gli embedding dei nodi a un valore comune, eliminando le informazioni discriminanti. In pratica, 2–4 strati sono solitamente ottimali. Tecniche come connessioni residue, reti di conoscenza saltate (jumping knowledge networks) e DropEdge possono aiutare se sono necessarie architetture più profonde.
Le GNN richiedono dati etichettati per tutti i nodi?
No. GCN e GAT sono comunemente utilizzate in contesti semi-supervisionati dove solo una piccola frazione di nodi possiede etichette; la struttura del grafo propaga le informazioni dai nodi etichettati a quelli non etichettati. GraphSAGE può anche essere addestrata in modo completamente supervisionato o non supervisionato a seconda del task.
Quanto deve essere grande il grafo?
È necessario un minimo di circa 50 nodi per un addestramento GNN significativo. Con meno di 20 nodi, il modello non può apprendere rappresentazioni affidabili e l'analisi convenzionale basata sulla centralità è più appropriata. Per grafi con milioni di nodi, sono necessari campionamenti di vicini in mini-batch (come in GraphSAGE) o metodi di partizionamento del grafo per mantenere gestibile l'utilizzo della memoria.
Metodi correlati
Fonti
Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR).
Apri il riferimento DOICopiato.Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations (ICLR).
Apri il riferimento DOICopiato.Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.
Apri il riferimento DOICopiato.