Graph Neural Network (GNN)

Una rete neurale a grafo (GNN) è una rete neurale che opera direttamente sui grafi: insiemi di nodi collegati da archi, dove sia i nodi sia gli archi possono avere caratteristiche. Molecole (atomi e legami), reti sociali (utenti e relazioni di follow), reti stradali (incroci e tratti stradali), mesh 3D e articolazioni di uno scheletro umano sono tutti grafi. Un grafo non ha una griglia o un ordine fissi e i suoi nodi hanno numeri diversi di vicini; perciò i filtri scorrevoli di una rete neurale convoluzionale (CNN) e l'elaborazione passo dopo passo di una rete neurale ricorrente (RNN) non si applicano direttamente. Le GNN gestiscono questo problema con il passaggio di messaggi: ogni nodo aggiorna ripetutamente il proprio vettore di caratteristiche usando quelli dei vicini, producendo embedding dei nodi che codificano sia gli attributi del nodo stesso sia la sua posizione nel grafo.

Come funziona il passaggio di messaggi#

Un layer GNN aggiorna ogni nodo in tre passaggi. Ogni vicino invia un messaggio, di solito una trasformazione appresa delle sue caratteristiche. Il nodo aggrega i messaggi in arrivo con una funzione che ne ignora l'ordine, come la somma, la media o il massimo. Quindi combina l'aggregato con le proprie caratteristiche per formare la nuova rappresentazione. Poiché l'aggregazione ignora l'ordine, il risultato non dipende dalla numerazione assegnata ai nodi. Nel 2017 Justin Gilmer e i suoi colleghi descrissero molte GNN come istanze del framework delle reti neurali a passaggio di messaggi. Dopo l'ultimo layer, una testa specifica per il compito legge gli embedding dei nodi per assegnare etichette ai nodi, prevedere archi mancanti o classificare un intero grafo:

Ogni layer estende la visuale di un nodo di un hop, quindi dopo k layer l'embedding di un nodo dipende da tutti i nodi che si trovano entro k archi: il suo campo recettivo nel grafo. Lo snippet PyTorch qui sotto crea un grafo a percorso di sei nodi, applica tre layer di convoluzione su grafi con la normalizzazione di GCN di Thomas Kipf e Max Welling e usa autograd per elencare quali nodi di input influenzano il nodo 0 dopo ogni layer:

import torch
from torch import nn

# A path graph 0-1-2-3-4-5 as an adjacency matrix with self-loops
A = torch.eye(6)
for i in range(5):
    A[i, i + 1] = A[i + 1, i] = 1
deg = A.sum(dim=1)
A_hat = A / torch.sqrt(deg[:, None] * deg[None, :])  # GCN normalization D^-1/2 (A + I) D^-1/2

torch.manual_seed(0)
x = torch.randn(6, 4, requires_grad=True)  # 4 input features per node
layers = [nn.Linear(4, 4) for _ in range(3)]

h = x
for k, layer in enumerate(layers, start=1):
    h = torch.tanh(A_hat @ layer(h))  # each node mixes in its neighbors' transformed features
    grad = torch.autograd.grad(h[0].sum(), x, retain_graph=True)[0]
    print(f"After layer {k}, node 0 depends on nodes {grad.abs().sum(dim=1).nonzero().flatten().tolist()}")

Stampa [0, 1], [0, 1, 2] e [0, 1, 2, 3]: il campo recettivo del nodo 0 cresce esattamente di un hop per layer.

Architetture GNN comuni#

• GCN: La rete convoluzionale su grafi calcola H′ = σ(D̃^(−1/2) à D̃^(−1/2) H W), dove à è la matrice di adiacenza con self-loop e D̃ la sua matrice dei gradi: una media ponderata per grado di ogni nodo e dei suoi vicini, seguita da una matrice dei pesi W condivisa da tutti i nodi.
• GraphSAGE: Campiona un numero fisso di vicini per nodo e apprende l'aggregatore, consentendo così di scalare a grafi molto grandi e di calcolare gli embedding di nodi che compaiono dopo l'addestramento.
• GAT: Le reti ad attenzione su grafi assegnano a ogni vicino pesi determinati da punteggi di attenzione appresi, anziché da pesi fissi basati sul grado.
• GIN: La rete di isomorfismo dei grafi somma i vicini e applica un MLP; Keyulu Xu e i suoi colleghi hanno dimostrato che questo la rende altrettanto efficace nel distinguere i grafi quanto il test di Weisfeiler-Lehman, il limite massimo per il passaggio standard di messaggi.
• Transformer per grafi: Applicano la self-attention a tutti i nodi e aggiungono codifiche posizionali derivate dalla struttura del grafo. Un transformer standard è esso stesso una GNN su un grafo completamente connesso di token.

La sovrapposizione di molti layer causa un eccessivo livellamento: le medie ripetute avvicinano gli embedding dei nodi finché non diventano indistinguibili. Per questo molte GNN usano solo due o tre layer, come la GCN originale, che ne usava due. PyTorch Geometric e la Deep Graph Library (DGL) implementano questi layer in modo efficiente su liste sparse di archi.

Applicazioni nel mondo reale#

• Previsioni meteorologiche: GraphCast di Google DeepMind, pubblicato su Science nel 2023, esegue il passaggio di messaggi su una mesh multiscala che copre il globo e produce previsioni a 10 giorni con una risoluzione di 0,25° in meno di un minuto, superando i sistemi deterministici operativi più accurati sul 90% di 1.380 obiettivi di verifica.
• Scoperta di farmaci: Nel 2020, ricercatori del MIT hanno addestrato una rete diretta con passaggio di messaggi per prevedere l'attività antibatterica a partire da grafi molecolari e l'hanno usata per identificare l'alicina, un composto strutturalmente diverso dagli antibiotici noti che ha ucciso molti batteri resistenti ai farmaci nei test di laboratorio.
• Sistemi di raccomandazione: PinSage di Pinterest ha appreso gli embedding dei pin da un grafo di 3 miliardi di pin e bacheche e 18 miliardi di archi, addestrandosi su 7,5 miliardi di esempi.
• Riconoscimento delle azioni basato sullo scheletro: ST-GCN tratta le articolazioni del corpo come nodi, le collega tramite le ossa all'interno di ogni frame e alla stessa articolazione nei frame vicini, quindi classifica l'azione a partire dal grafo spazio-temporale risultante. I modelli di stima della posa YOLO26 restituiscono 17 keypoint COCO per persona in ogni frame: le coordinate delle articolazioni da cui si costruisce un grafo scheletrico.

GNN e concetti correlati#

• Grafo della conoscenza: Una struttura dati che memorizza fatti sotto forma di triple entità-relazione-entità. Una GNN è un modello in grado di apprendere da un grafo della conoscenza, ad esempio per prevedere collegamenti mancanti.
• Apprendimento profondo geometrico: Il campo più ampio delle reti basate sulle simmetrie dei dati, che comprende CNN su griglie, GNN su grafi e modelli su mesh e varietà.
• CNN: Una CNN applicata a un'immagine è un caso particolare di passaggio di messaggi su un grafo a griglia. Ogni pixel ha lo stesso numero di vicini in posizioni relative fisse, quindi una CNN può apprendere un peso distinto per ogni posizione dei vicini, cosa che una GNN su un grafo irregolare non può fare.