Approfondimenti tecnici

Reti neurali a grafo: teoria e applicazioni

Un’analisi approfondita delle reti neurali a grafo che spazia dal passaggio di messaggi ai metodi spettrali e alle GAT, fino alle applicazioni concrete nelle reti sociali, nello studio delle molecole e nei sistemi di raccomandazione.

AI.info Team · 2026-08-12

Perché i grafi resistono al deep learning tradizionale

Le reti convoluzionali presuppongono una griglia; le reti ricorrenti e i transformer presuppongono una sequenza. I grafi non offrono né l’una né l’altra. I nodi non hanno un ordinamento canonico, la dimensione dei vicinati varia da un nodo all’altro e uno stesso grafo può essere rappresentato da molte matrici di adiacenza diverse, a seconda di come vengono indicizzati i nodi. Questa proprietà è detta invarianza alle permutazioni (per gli output a livello di grafo) o equivarianza alle permutazioni (per gli output a livello di nodo).

Qualsiasi architettura che operi sui grafi deve rispettare questa proprietà: cambiare le etichette dei nodi non deve cambiare la risposta. Questo solo vincolo esclude la possibilità di appiattire semplicemente una matrice di adiacenza in un vettore di dimensione fissa e darla in input a un MLP. È anche il motivo per cui le reti neurali a grafo (GNN) hanno sviluppato una primitiva computazionale distinta: il passaggio di messaggi.

Il passaggio di messaggi come modello unificante

Justin Gilmer e i suoi coautori (Gilmer et al., «Neural Message Passing for Quantum Chemistry», ICML 2017) hanno formalizzato le reti neurali basate sul passaggio di messaggi (MPNN) come un quadro comune che comprende la maggior parte delle varianti di convoluzione su grafi proposte fino a quel momento. Il calcolo in avanti si divide in due fasi. Nella fase di passaggio dei messaggi, ogni nodo aggiorna ripetutamente uno stato nascosto aggregando i messaggi dei suoi vicini:

m_v^(t+1) = AGGREGATE({ M_t(h_v^t, h_w^t, e_vw) : w in N(v) })
h_v^(t+1) = UPDATE(h_v^t, m_v^(t+1))

Dopo T iterazioni, una funzione di lettura aggrega tutti gli stati finali dei nodi in una rappresentazione a livello di grafo per compiti come la previsione delle proprietà molecolari. Il quadro è volutamente generico: M_t, UPDATE e la funzione di aggregazione possono essere appresi, mentre l’operatore di aggregazione (somma, media, massimo) viene scelto in base alle proprietà di invarianza che garantisce. L’aggregazione per somma, per esempio, è la più espressiva dal punto di vista del test di isomorfismo dei grafi di Weisfeiler-Leman, come formalizzato in seguito dall’architettura GIN (Xu et al., 2019), perché le somme conservano le informazioni sulla cardinalità dei multiinsiemi che la media e il massimo perdono.

Ogni architettura discussa qui sotto è una particolare istanza di questo schema: le differenze riguardano soprattutto il modo in cui definisce la funzione di messaggio e i pesi usati per aggregare i vicini.

Le radici spettrali: dalla trasformata di Fourier sui grafi alla GCN

La prima formulazione rigorosa della convoluzione sui grafi è nata dalla teoria spettrale dei grafi. Una convoluzione su un grafo si definisce calcolando la decomposizione agli autovalori del laplaciano del grafo L = D − A (dove D è la matrice dei gradi e A la matrice di adiacenza), trasformando i segnali dei nodi nel «dominio di Fourier del grafo» tramite gli autovettori del laplaciano, applicando un filtro e tornando alla rappresentazione iniziale. È una soluzione elegante, ma presenta due problemi pratici: la decomposizione agli autovalori ha complessità O(n^3) e i filtri appresi nel dominio spettrale di un grafo non si trasferiscono necessariamente a un grafo con una struttura diversa, complicando la generalizzazione induttiva.

Defferrard et al. (ChebNet, NeurIPS 2016) hanno affrontato il problema del costo approssimando i filtri spettrali con polinomi di Chebyshev del laplaciano. In questo modo si evita la decomposizione esplicita agli autovalori e i filtri restano localizzati entro K salti, cioè dipendono solo dai nodi raggiungibili in non più di K salti.

Thomas Kipf e Max Welling hanno poi compiuto un passo ulteriore, troncando questa espansione al primo ordine (K=1) e condividendo i parametri. Ne è nata la Graph Convolutional Network (GCN), presentata in «Semi-Supervised Classification with Graph Convolutional Networks» (ICLR 2017). La regola di propagazione risultante, applicata strato per strato, è sorprendentemente semplice:

H^(l+1) = σ( D̃^(-1/2) Ã D̃^(-1/2) H^(l) W^(l) )

dove à = A + I aggiunge autoarchi affinché le caratteristiche del nodo stesso sopravvivano alla convoluzione, e D̃ è la matrice dei gradi di Ã. Questa normalizzazione simmetrica impedisce che la scala delle rappresentazioni dei nodi esploda o svanisca in funzione del grado del nodo. Nonostante la sua semplicità — in sostanza, una moltiplicazione di matrici e una proiezione lineare appresa per strato — GCN ha eguagliato o superato metodi spettrali molto più complessi nei benchmark sulle reti di citazioni (Cora, Citeseer, Pubmed) e ha un costo che cresce linearmente con il numero di archi, anziché cubicamente.

L’effetto pratico di GCN è stato quello di riformulare la convoluzione sui grafi come un’operazione spaziale di media sui vicini, anziché come un’operazione nel dominio spettrale. Lo strato si può descrivere direttamente così: «la nuova rappresentazione di ogni nodo è una media pesata e normalizzata delle rappresentazioni dei suoi vicini, seguita da una trasformazione lineare e da una funzione non lineare». Per implementarlo non serve fare riferimento agli autovettori.

Approcci spaziali: campionamento e attenzione

GCN, nella sua formulazione originale, è trasduttivo: richiede che l’intero grafo (tutti i nodi, compresi quelli di test) sia disponibile durante l’addestramento, perché la matrice di adiacenza normalizzata è incorporata nella regola di propagazione. Questo approccio non è praticabile per grafi come quelli dei social network in produzione o dei cataloghi di e-commerce, dove compaiono continuamente nuovi nodi.

William Hamilton, Rex Ying e Jure Leskovec hanno affrontato il problema con GraphSAGE («Inductive Representation Learning on Large Graphs», NeurIPS 2017). Anziché usare l’intera struttura di adiacenza, GraphSAGE campiona per ogni nodo un vicinato di dimensioni fisse e apprende funzioni di aggregazione (sono stati valutati aggregatori basati sulla media, su LSTM e sul max-pooling) che combinano le caratteristiche del nodo stesso con quelle dei vicini campionati:

h_v^(l+1) = σ( W^(l) · CONCAT(h_v^l, AGGREGATE({h_u^l : u ∈ sample(N(v))})) )

Poiché l’aggregatore è una funzione appresa, anziché una matrice specifica del grafo, può generalizzare a nodi e persino a interi grafi mai incontrati durante l’addestramento: è apprendimento induttivo delle rappresentazioni a tutti gli effetti. Il campionamento del vicinato pone inoltre un limite al costo computazionale per nodo indipendentemente dal suo grado, ed è questo che ha reso GraphSAGE praticabile per grafi con milioni di nodi.

Petar Veličković e i suoi coautori hanno affrontato da un’altra prospettiva lo stesso problema di fondo — il fatto che GCN assegni a ogni vicino un peso fisso, determinato dalla struttura — con la Graph Attention Network (GAT), «Graph Attention Networks» (ICLR 2018, arXiv:1710.10903). GAT sostituisce la normalizzazione fissa con un coefficiente di attenzione appreso, dipendente dalle caratteristiche dei nodi, per ciascun arco:

e_ij = LeakyReLU(a^T [W h_i || W h_j])
α_ij = softmax_j(e_ij) = exp(e_ij) / Σ_{k∈N(i)} exp(e_ik)
h_i' = σ( Σ_{j∈N(i)} α_ij W h_j )

I coefficienti di attenzione α_ij sono calcolati con un meccanismo di attenzione condiviso e apprendibile, applicato a ogni arco e normalizzato tramite softmax sul vicinato di ciascun nodo. I nodi imparano così ad attribuire pesi diversi a vicini strutturalmente simili in base alle loro caratteristiche: un meccanismo di self-attention limitato agli archi effettivi del grafo, anziché calcolato su tutte le coppie di nodi (ed è questo a distinguere GAT da un semplice Transformer applicato a un insieme di nodi completamente connessi).

GAT usa anche l’attenzione multi-head: concatena diverse teste di attenzione indipendenti (oppure ne calcola la media, nello strato finale) per stabilizzare l’addestramento, riprendendo l’architettura multi-head della self-attention dei Transformer standard. Soprattutto, poiché i pesi di attenzione sono calcolati dalle caratteristiche dei nodi anziché dal laplaciano fisso del grafo, anche GAT è induttivo e non richiede l’accesso all’intera struttura del grafo durante l’addestramento.

Il problema dell’over-smoothing

Per analogia con le CNN, aggiungere altri strati di convoluzione sui grafi dovrebbe permettere a una rete di cogliere dipendenze a distanze sempre maggiori. In pratica, le prestazioni delle architetture simili a GCN peggiorano nettamente oltre i 2-4 strati. Qimai Li, Zhichao Han e Xiao-Ming Wu ne hanno individuato la ragione in «Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning» (AAAI 2018): hanno mostrato che la regola di propagazione di GCN è, matematicamente, un caso particolare di smussamento laplaciano, un’operazione che calcola la media tra le caratteristiche di un nodo e quelle dei suoi vicini.

Un solo strato di smussamento è utile — è proprio per questo che GCN funziona meglio rispetto a trattare i nodi indipendentemente — ma, ripetuto su molti strati, lo smussamento rende le rappresentazioni dei nodi sempre più simili e, al limite, le porta verso un valore determinato soltanto dal grado del nodo e dalla sua appartenenza a una componente connessa, cancellando le informazioni distintive di cui ha bisogno un classificatore. Questo è l’over-smoothing: all’aumentare della profondità, gli embedding dei nodi diventano statisticamente indistinguibili e l’accuratezza nei compiti a valle crolla, anche se sulla carta il modello ha una capacità di rappresentazione strettamente maggiore.

L’over-smoothing è la ragione principale per cui la maggior parte delle architetture GNN di successo resta poco profonda (2-4 strati) rispetto alle profondità di 50-100+ strati comuni nei modelli per la visione e il linguaggio. Ha inoltre dato impulso a un intero filone di ricerca sulle possibili soluzioni: connessioni residue/skip che permettono di combinare l’output di uno strato con il suo input (riprese direttamente da ResNet), la rimozione stocastica degli archi durante l’addestramento secondo l’approccio DropEdge, PairNorm e altri schemi di normalizzazione che penalizzano esplicitamente il collasso delle rappresentazioni, e accorgimenti basati su connessioni residue iniziali/mappature identità (per esempio APPNP, GCNII) che separano «quanti salti di informazioni sul vicinato» da «quanti strati di trasformazione non lineare». Una rete può così propagare informazioni su lunghe distanze nel grafo senza aumentare in proporzione la profondità della trasformazione appresa e provocare il collasso.

Spettrale e spaziale: due prospettive, metodi convergenti

Vale la pena essere precisi su una distinzione che nell’uso informale tende a sfumare. I metodi spettrali (la CNN spettrale originale, ChebNet e GCN nella sua derivazione) definiscono la convoluzione attraverso la base degli autovettori del laplaciano del grafo ed ereditano la dipendenza di quella base dal grafo specifico: non è garantito che un filtro appreso su un grafo possa essere trasferito a un altro con un laplaciano diverso, anche se i filtri spettrali possono trasferirsi approssimativamente tra grafi di dimensioni e topologie diverse quando entrambi discretizzano lo stesso spazio sottostante.

I metodi spaziali (GraphSAGE, GAT e, più in generale, il framework MPNN) definiscono invece l’aggiornamento direttamente come funzione del vicinato locale di un nodo nel dominio originale del grafo, senza alcun riferimento alla teoria spettrale. Il fatto storicamente interessante è che GCN si trova nel punto di snodo: è stato derivato come approssimazione spettrale del primo ordine, ma lo strato che ne risulta è spaziale sotto ogni aspetto rilevante per l’implementazione e la generalizzazione: può essere, ed è, implementato e compreso semplicemente come una media sul vicinato.

In pratica, quasi tutte le architetture GNN usate oggi in produzione (GraphSAGE, GAT e i loro numerosi discendenti) sono metodi spaziali basati sul passaggio di messaggi, perché supportano minibatch, campionamento e generalizzazione induttiva.

Applicazioni reali

Predizione della struttura delle proteine. AlphaFold2 di DeepMind non è una rete neurale a grafo nel senso di GCN o GAT, ma il suo modulo centrale Evoformer opera su una rappresentazione a coppie — una matrice residuo per residuo che costituisce naturalmente un grafo degli amminoacidi — mediante aggiornamenti di self-attention triangolare che propagano vincoli di coerenza geometrica tra coppie di residui. Il principio è concettualmente in linea con l’idea, propria della graph attention, di apprendere pesi dipendenti dagli archi anziché usare pesi strutturali fissi.

Il successivo Structure Module converte poi questa rappresentazione in coordinate 3D usando Invariant Point Attention, un meccanismo di attention progettato per rispettare le invarianti rotazionali e traslazionali delle strutture fisiche: anche in questo caso, l’attention è calcolata su un insieme di residui simile a un grafo, anziché su una griglia o una sequenza.

Scoperta di farmaci e predizione delle proprietà molecolari. Le reti neurali a passaggio di messaggi, derivate direttamente dal quadro proposto da Gilmer e colleghi, sono uno strumento standard per predire le proprietà molecolari (solubilità, tossicità, affinità di legame): trattano una molecola come un grafo in cui gli atomi sono nodi e i legami sono archi. Questa rappresentazione nativa dei grafi evita la perdita di informazioni propria delle impronte molecolari a lunghezza fissa ed è stata applicata a compiti che spaziano dalla predizione delle interazioni tra farmaci e bersagli alla modellazione delle interazioni tra farmaci e al riposizionamento dei farmaci.

Sistemi di raccomandazione su larga scala. PinSage di Pinterest (Ying e colleghi, «Graph Convolutional Neural Networks for Web-Scale Recommender Systems», KDD 2018) ha esteso le convoluzioni localizzate sul modello di GraphSAGE con un campionamento dei vicini basato sull’importanza (che usa cammini casuali per attribuire un peso ai vicini in base alla loro rilevanza) e con la costruzione di minibatch produttore-consumatore, così da addestrare il modello su un grafo con miliardi di nodi e archi: secondo quanto riportato, circa 3 miliardi di nodi e 18 miliardi di archi, diversi ordini di grandezza in più rispetto ai benchmark sulle reti di citazioni su cui GCN era stato inizialmente valutato.

Questo ha dimostrato che le convoluzioni su grafo potevano passare dai benchmark accademici ai sistemi industriali su scala di produzione, generando rappresentazioni vettoriali dei pin per le raccomandazioni direttamente dal grafo bipartito pin-bacheche, insieme a caratteristiche visive e testuali.

Librerie e strumenti pratici

Due librerie open source dominano il lavoro applicativo sulle GNN. PyTorch Geometric (PyG) è costruita direttamente su PyTorch e offre implementazioni di GCN, GraphSAGE, GAT e decine di altre architetture pubblicate, oltre a operazioni su tensori sparsi, strumenti per caricare minibatch sia da molti piccoli grafi sia da un unico grafo enorme, e un’ampia raccolta di dataset di benchmark.

Deep Graph Library (DGL) offre un’API per il passaggio di messaggi indipendente dal backend (PyTorch o TensorFlow) ed è spesso preferita per i grafi eterogenei — grafi con diversi tipi di nodi e archi, comuni nei grafi della conoscenza e nei dati molecolari — per i quali la sua struttura dati più generale offre maggiore flessibilità. Entrambe le librerie implementano schemi di campionamento dei vicini derivati dall’approccio di GraphSAGE, rendendo pratico l’addestramento su grafi troppo grandi per essere rappresentati in forma densa nella memoria della GPU.

A che punto è il settore

Il passaggio di messaggi offre alle GNN un modo fondato su principi teorici ed equivariante rispetto alle permutazioni per apprendere dalla struttura relazionale. GCN, GraphSAGE e GAT delineano una chiara evoluzione dalle origini nella teoria spettrale a formulazioni spaziali sempre più generali, induttive e adatte al campionamento. Il risultato sull’over-smoothing è il principale monito emerso in questo campo: nei grafi, aumentare la profondità ha un costo che non ha nelle griglie o nelle sequenze, perché l’aggregazione ripetuta dei valori dei vicini è, matematicamente, un operatore di livellamento con un punto fisso.

Le architetture arrivate nei sistemi di produzione — le convoluzioni con campionamento di PinSage, l’attention sulle coppie strutturate come un grafo di AlphaFold, i modelli molecolari basati su MPNN — hanno un tratto in comune: considerano le connessioni del grafo come una proprietà strutturale da codificare esplicitamente, anziché da inferire implicitamente con un modello più denso che prescinde dalla struttura.