Che cos'è una GNN (rete neurale a grafo)?

Le reti neurali a grafo (GNN) sono un'architettura di rete neurale profonda, popolare sia nelle applicazioni pratiche che nella ricerca all'avanguardia sul machine learning. Utilizzano un modello di rete neurale per rappresentare i dati sulle entità e le loro relazioni. Sono utili per il data mining nel mondo reale, la comprensione dei social network, i grafi della conoscenza, i sistemi di raccomandazione e la bioinformatica.

Lo sviluppo delle GNN si è ispirato ad algoritmi di deep learning come le reti neurali convoluzionali (CNN) e le reti neurali ricorrenti (RNN), ma presentano diverse differenze chiave. Le CNN sono progettate per i dati che hanno una struttura simile a una griglia, come i pixel di un'immagine. Ogni pixel può essere collegato al massimo ad altri otto pixel. Al contrario, le RNN sono adattate a strutture di sequenza in cui ogni elemento può essere collegato al massimo ad altri due elementi, come una stringa di parole in un testo. Nei dati strutturati a grafo, tuttavia, qualsiasi elemento può avere una o più connessioni e potrebbe non avere coerenza tra il numero di connessioni per un elemento specifico.

Le reti neurali a grafo sono un'implementazione del deep learning geometrico¹, classificato in quattro categories:

Apprendimento basato su grafi: apprende dati simili a grafi.

Apprendimento basato su griglia: apprende informazioni su immagini simili a dati, e altri tipi di dati, che possono essere rappresentati tramite griglie.

Apprendimento basato su gruppo: apprende come le informazioni si relazionano con un gruppo di riferimento. Questa funzionalità è molto utile quando i dati vengono acquisiti da un gruppo come una sfera, ad esempio dati geologici provenienti da diverse fonti sparse sulla Terra.

Apprendimento basato su maglie: apprende come le informazioni si distribuiscono su una maglia irregolare, come ad esempio l'analisi e la previsione degli elementi di un modello 3D di un oggetto.

Le GNN sono un'area di ricerca attiva sull'intelligenza artificiale, ma sono ben supportate da librerie e toolkit realizzati in linguaggi come Python e framework tra cui TensorFlow e PyTorch.

Un insieme di oggetti e le connessioni tra di essi possono essere espressi come un grafo. I ricercatori informatici hanno sviluppato reti neurali per operare su strutture di dati a grafo.

Un grafo rappresenta le relazioni, chiamate "edge", tra un insieme di entità, chiamate "nodi". Matematicamente, un grafo G è definito come una tupla di un insieme di nodi e vertici V e di un insieme di edge e link. E:G = (V, E). Ogni edge è una coppia di due vertici e rappresenta una connessione tra di essi.

Per descrivere ulteriormente ogni nodo, edge o l'intero grafo, possiamo memorizzare informazioni in ognuna di queste parti del grafo.

I grafi possono essere ulteriormente descritti assegnando la direzionalità a ciascun edge. Un grafo è descritto come diretto o non diretto. Un grafo non diretto rappresenta una relazione, che è bidirezionale. Se Rosa ha un fratello, Juan, allora anche Juan ha una sorella, Rosa. Il rapporto tra Rosa e suo fratello non ha alcuna direzionalità, collega soltanto loro due. Un grafo orientato rappresenta relazioni direzionali. Se Rosa ha un fratello maggiore, Juan, allora la relazione "fratello maggiore" è unilaterale: da Juan a Rosa, Juan non ha un "fratello maggiore".

Un modo per visualizzare la connettività di un grafo è attraverso la sua matrice di adiacenza. Si tratta di una rappresentazione basata sulla matrice dei vertici del grafo che può rappresentare sia grafi orientati che non orientati.

La matrice di adiacenza di un grafo orientato indica tutti i vertici e la direzione dell'edge che li crea. Ad esempio, il nodo 0 nel grafo orientato si connette al nodo 1, ma l'inverso non è vero a causa della direzionalità della connessione. Nella matrice di adiacenza, [riga 0, colonna 1] contiene un valore, mentre [riga 1, colonna 0] non lo contiene.

Le rappresentazioni dei grafi dovrebbero avere un'invarianza di permutazione, il che significa che le rappresentazioni del grafo dovrebbero produrre gli stessi risultati se la struttura del grafo è la stessa ma l'ordine dei nodi è diverso. Questo approccio garantisce che la rappresentazione del grafo abbia le stesse proprietà del grafo stesso.

Le GNN adottano in genere un'architettura "graph-in, graph-out". Ciò significa che questi tipi di modello accettano un grafo come input, con informazioni caricate in nodi, edge e contesto globale. I modelli trasformano progressivamente questi embedding senza modificare la connettività del grafo di input. Gli embedding rappresentano i nodi come embedding del nodo e i vertici come embedding del vertice. Questi embedding consentono al modello di apprendere quali tipi di nodi si verificano e dove nel grafo, nonché i tipi e le posizioni degli edge.

In genere, l'addestramento di una rete neurale viene effettuata aggiornando i parametri di rete con gradienti calcolati su un sottoinsieme randomizzato dei dati di addestramento. Per addestrare le reti a grafo, le reti neurali a grafo creano sottografi che preservano le proprietà essenziali del grafo principale di grandi dimensioni.

Le GNN utilizzano un meccanismo di trasmissione dei messaggi per aggregare le informazioni dai nodi vicini, consentendo loro di catturare le complesse relazioni nei grafi. Una sfida nella modellazione dei dati strutturati a grafo è l'acquisizione delle interazioni tra i nodi. La trasmissione di messaggi neurali risolve questa sfida fornendo un framework per modellare le dipendenze e le interazioni nei dati a grafo. I nodi scambiano informazioni con i nodi vicini e aggregano tali informazioni per aggiornare le proprie rappresentazioni. Questo processo di trasmissione dei messaggi è simile ai nodi di un grafo che si scambiano messaggi o segnali.

Le GNN consentono diversi tipi di analisi, ognuna delle quali fornisce insight su diversi elementi dei dati a grafo.

Attività a livello di grafo

In un'attività a livello di grafo, la GNN prevede una proprietà dell'intero grafo. Per una molecola rappresentata come grafo, è possibile prevedere se si legherà a un recettore associato a una malattia. Per un social network, è possibile prevedere se è probabile che siano associati a una particolare istituzione, come un'università o un college. Questo tipo di riconoscimento dei modelli può essere inquadrato come una forma di classificazione dei grafi perché classifica l'intero grafo.

Attività a livello di nodo

Le attività a livello di nodo riguardano la previsione dell'identità o del ruolo di ciascun nodo all'interno di un grafo. Ad esempio, un problema di classificazione dei nodi in un set di dati di social network potrebbe consistere nel prevedere se è probabile che un utente abbia un interesse specifico in base alla connessione della sua rete di amici. Avere amici che condividono solo l'interesse per il golf, ma nessun altro interesse in comune, è una buona indicazione che anche un nuovo amico potrebbe apprezzare il golf. Questo tipo di caratteristiche dei nodi possono spesso essere previste con una GNN.

Attività a livello di edge

L'ultimo tipo di problema di previsione nei grafi è la previsione degli edge, a volte chiamata link prediction.

Un esempio di inferenza a livello di edge è la comprensione delle scene delle immagini. Dopo aver identificato gli oggetti in un'immagine, i modelli di deep learning possono anche prevedere la relazione tra loro. Questa è una classificazione a livello di edge perché i nodi rappresentano gli oggetti nell'immagine e la previsione indica quali di questi nodi condividono un edge o qual è il valore di quell'edge. Per scoprire le connessioni tra le entità, si potrebbe considerare il grafo come "completamente connesso" e, in base al loro valore previsto, snellire gli edge per arrivare a un grafo sparso.

Reti convoluzionali a grafo⁴ (GCN): questo approccio è per l'apprendimento semi-supervisionato basato su una variante di reti neurali convoluzionali in grado di apprendere e prevedere da dati basati su grafi. Questi modelli scalano linearmente nel numero di edge del grafo, rendendolo adatto a set di dati di grandi dimensioni. I modelli apprendono anche la struttura locale dei grafi e le caratteristiche dei nodi.

Autoencoder a grafo²: queste varianti sono modelli di reti neurali addestrabili end-to-end per l'apprendimento senza la supervisione, il clustering e la link prediction su grafi. In genere, usano una GCN come encoder per creare embedding e hanno un decoder che ricostruisce il grafo a partire dalla rappresentazione latente appresa.

Reti di attenzione a grafo³ (GAT): un'architettura di reti neurali che opera su dati strutturati in grafi. Le GAT utilizzano un meccanismo di attenzione sotto forma di livelli di auto-attenzione per affrontare le carenze dei metodi precedenti basati sulle convoluzioni dei grafi o sulle loro approssimazioni. Accumulando i livelli in cui i nodi possono partecipare alle caratteristiche dei loro vicinati, una GAT consente (implicitamente) di specificare pesi diversi per i diversi nodi di un vicinato. Questo è possibile senza richiedere costose operazioni sulle matrici come l'inversione o senza dipendere dalla conoscenza della struttura del grafo in anticipo.

Rappresentazione a grafo: l'apprendimento è un'area di ricerca che presenta le reti neurali a grafo come un modo per trovare una rappresentazione significativa e potenzialmente a bassa dimensione dei nodi dalle relazioni complesse presenti in un grafo. Un esempio di questa estensione è GraphSage⁶, un progetto della Stanford University, che crea rappresentazioni vettoriali a bassa dimensione per i nodi, rendendolo adatto a lavorare con dati in cui i nodi rappresentano dati ad alta dimensione.

Come esempio del modo in cui può essere strutturata una GNN, consideriamo una semplice rete convoluzionale a grafo (GCN) per classificare un intero grafo. La GCN più semplice ha tre livelli:

Strato convoluzionale: questo strato esegue la convoluzione su ogni nodo per imparare le sue connessioni.

Livello di attivazione non lineare: questo livello applica una funzione di attivazione come ReLU all'output della convoluzione.

Livello di output lineare: quest'ultimo livello somma i risultati per generare una previsione finale.

Innanzitutto, viene eseguita una convoluzione utilizzando ogni nodo nel grafo del livello di convoluzione. Questo livello convoluzionale utilizza le informazioni sulle caratteristiche dei vicini di ciascun nodo e le aggrega, aggiornando i pesi associati a ciascun nodo. Quindi, una funzione di attivazione non lineare, come ReLU, viene applicata all'output del livello di convoluzione. Per ottenere la massima precisione, una rete può utilizzare più convoluzioni e livelli di attivazione non lineari insieme. Infine, un livello lineare di output viene utilizzato per prevedere a quale classe è più probabile che appartenga un grafo.

Le GCN sono concettualmente semplici, adatte per grafi su larga scala e facili da programmare, ma presentano anche diversi inconvenienti chiave. Per prima cosa, le GCN non supportano le caratteristiche degli edge. Possono solo apprendere e prevedere le caratteristiche dei nodi o le caratteristiche complessive del grafo. Il concetto di trasmissione dei messaggi non esiste con le GCN. Questo problema ne limita l'utilizzo solo ai casi in cui tutte le informazioni richieste sono presenti nei nodi anziché negli edge.

Una rete neurale di trasmissione dei messaggi (MPNN), tuttavia, consente rappresentazioni di edge.⁵ Il processo di trasmissione dei messaggi è, grosso modo, il seguente. Ogni nodo nel grafo riceve un embedding iniziale che agisce come caratteristiche di input iniziale del nodo. A ogni iterazione del passaggio del messaggio, il nodo aggrega le informazioni dai nodi vicini. Quell'informazione aggregata viene poi combinata con l'embedding corrente del nodo utilizzando una funzione di aggiornamento. Gli embedding aggiornati vengono passati alla successiva iterazione della trasmissione dei messaggi. Dopo diverse iterazioni adatte a rappresentare la complessità del grafo, gli embedding finali vengono utilizzati per rappresentare ogni nodo del grafo. Infine, le fasi di aggregazione, aggiornamento e iterazione vengono eseguite dalle reti neurali per apprendere schemi complessi nel grafo complessivo.

L'uso della trasmissione di messaggi consente una classificazione dei nodi più sofisticata, la classificazione degli edge o persino una previsione di dove potrebbero apparire gli edge nel grafo (chiamata link prediction).

Le GNN hanno molte applicazioni nell'elaborazione del linguaggio naturale (PNL). Ad esempio, nella classificazione dei documenti le GNN possono essere utilizzate per modellare le relazioni tra parole o frasi nei documenti. Questa capacità consente una migliore classificazione dei documenti e un migliore recupero delle informazioni. Le GNN possono aiutare nelle attività di risposta alle domande rappresentando le relazioni tra le parole di una domanda e le risposte dei candidati all'interno di un grafo della conoscenza. Le GNN possono acquisire informazioni contestuali e dipendenze del sentiment nel testo, migliorando l'analisi del sentiment in situazioni con elevata ambiguità o relazioni tra entità molto specifiche.

Hanno anche numerose applicazioni nella computer vision. Le GNN possono anche essere impiegate per attività di segmentazione delle immagini a livello di pixel, modellando le relazioni tra pixel adiacenti sotto forma di grafo. Le GNN possono aiutare nel rilevamento degli oggetti acquisendo informazioni contestuali e relazioni tra oggetti nelle immagini. Nelle attività di comprensione della scena, le GNN vengono utilizzate per comprendere scene complesse e generare grafi di scena che rappresentano le relazioni spaziali tra gli oggetti in un'immagine.

Le GNN sono potenti strumenti anche in bioinformatica. Nell'analisi delle sequenze genomiche, le GNN possono modellare le relazioni tra geni o sequenze genetiche, aiutando nelle attività di previsione dell'espressione genica e classificazione delle sequenze. Nella scoperta di farmaci, le GNN possono essere utilizzate per la previsione dell'interazione farmaco-obiettivo e la previsione delle proprietà molecolari, il che è fondamentale nella ricerca farmaceutica.