Rete neurale grafica

Una rete neurale grafica ( GNN ) appartiene a una classe di reti neurali artificiali per l'elaborazione di dati che possono essere rappresentati come grafici .

In queste strutture, i nodi rappresentano oggetti (come pixel o parole), e i collegamenti rappresentano le relazioni tra di essi.

Ad esempio:

• Nel caso della visione artificiale, i pixel possono essere rappresentati come nodi collegati agli altri pixel a loro vicini. Questo è simile al funzionamento di uno strato di rete convoluzionale.
• Nel linguaggio naturale, le parole in una frase possono essere viste come nodi di un grafo, dove ciascuna parola è collegata a tutte le altre. Questo ricorda come lavora uno strato di trasformazione, come quelli usati nei modelli di linguaggio.

Le reti GNN funzionano grazie a uno scambio di informazioni tra i nodi del grafo: ogni nodo modifica le informazioni che descrivono il suo stato o il suo contenuto, basandosi sui dati che riceve dai nodi vicini, in modo iterativo. Esistono molte varianti di GNN, che differiscono per il modo in cui avviene questo scambio di informazioni, che viene spesso riadattato basandosi su metodi ricorsivi o convoluzionali.

I domini applicativi rilevanti per le GNN includono l'elaborazione del linguaggio naturale, reti sociali, reti di citazione, biologia molecolare, ^[1] chimica, ^[2] fisica e problemi di ottimizzazione combinatoria NP-hard .

Le librerie open source che implementano GNN includono PyTorch Geometric ( PyTorch ), TensorFlow GNN ( TensorFlow ), Deep Graph Library ^[3] (framework agnostico), jraph ( Google JAX ) e GraphNeuralNetworks.jl /GeometricFlux.jl ^[4] ( Julia, Flux ).

Negli ultimi anni, le reti neurali grafiche (GNN) hanno guadagnato popolarità grazie alla loro capacità di trattare e analizzare dati strutturati sotto forma di grafi. Questi modelli sono stati adottati in vari settori, tra cui la previsione del traffico (come nel caso di Google Maps), i sistemi di raccomandazione su larga scala (ad esempio PinSage di Pinterest), e le previsioni meteorologiche (come nel caso di GraphCast di DeepMind). Inoltre, i GNN sono stati applicati anche in ambiti scientifici, come la creazione di materiali bioispirati e la mappatura delle conoscenze interdisciplinari, mostrando un ampio potenziale in diverse aree di ricerca e innovazione. Questi sviluppi sono il risultato di significativi miglioramenti nelle architetture dei GNN, che hanno consentito di superare le limitazioni precedenti, rendendo questi modelli più potenti ed efficienti.

L'architettura di una GNN generica implementa i seguenti livelli fondamentali:

1. Uno strato equivariante di permutazione che mappa una rappresentazione del grafo in una versione aggiornata dello stesso grafo, mantenendo invariata la struttura del grafo stesso. Nella pratica, questo processo viene implementato attraverso il passaggio di messaggi tra i nodi del grafo. In ogni passaggio, i nodi aggiornano le proprie rappresentazioni aggregando i messaggi ricevuti dai loro vicini. Questo permette a ciascun nodo di "espandere" il proprio campo recettivo, ovvero di includere informazioni da un numero maggiore di nodi vicini. A ogni passaggio di messaggi aumenta, quindi, la quantità di informazioni a cui ogni nodo ha accesso, migliorando progressivamente la comprensione complessiva della struttura del grafo.
2. Uno strato di pooling locale, che riduce la complessità del grafo tramite sottocampionamento, semplificandone la struttura. Questa operazione aumenta il campo recettivo della rete, in modo simile al pooling nelle reti neurali convoluzionali, dove vengono aggregati i valori locali per ridurre la risoluzione. Esistono diverse varianti di pooling locale, come il "pooling dei k-vicini più prossimi", che seleziona i nodi più vicini, il "pooling dei k-migliori", che prende i nodi più importanti, e il "pooling tramite auto-attenzione", che utilizza meccanismi di attenzione per determinare quali nodi aggregare tra loro.
3. Un livello di pooling globale, noto anche come livello di lettura, che fornisce una rappresentazione di dimensioni fisse dell'intero grafico. Lo strato di pooling globale deve essere invariante alla permutazione, in modo che le permutazioni nell'ordinamento dei nodi e dei bordi del grafico non alterino l'output finale. Esempi includono la somma, la media o il massimo elemento.

Le GNN hanno un limite intrinseco, poichè non possono essere più espressive del test di isomorfismo dei grafi di Weisfeiler-Leman. Questo implica che alcune strutture grafiche, come ad esempio certe molecole composte dagli stessi atomi ma da legami differenti, non possono essere distinte utilizzando GNN tradizionali.

Per affrontare questa limitazione, sono in fase di sviluppo modelli GNN più potenti che operano su geometrie di dimensioni superiori, come i complessi simpliciali.

I livelli di passaggio dei messaggi corrispondono a permutazioni che mappano il grafo in una sua rappresentazione aggiornata. Formalmente, possono essere espressi come reti neurali di passaggio di messaggi (MPNN).

Assumiamo che ${\displaystyle G=(V,E)}$ sia un grafico, dove ${\displaystyle V}$ è l'insieme dei nodi e ${\displaystyle E}$ è l'insieme dei bordi. Assumiamo poi che ${\displaystyle N_{u}}$ rappresenti il vicinato di qualche nodo ${\displaystyle u\in V}$ . Inoltre, interpretiamo ${\displaystyle \mathbf {x} _{u}}$ come l'insieme delle caratteristiche del nodo ${\displaystyle u\in V}$, E ${\displaystyle \mathbf {e} _{uv}}$ come le caratteristiche del bordo ${\displaystyle (u,v)\in E}$ . Un livello MPNN può essere espresso come segue:

${\displaystyle \mathbf {h} _{u}=\phi \left(\mathbf {x} _{u},\bigoplus _{v\in N_{u}}\psi (\mathbf {x} _{u},\mathbf {x} _{v},\mathbf {e} _{uv})\right)}$

Dove 𝜙 e 𝜓 sono funzioni differenziabili (ad esempio, reti neurali artificiali), e ⨁ è un operatore di aggregazione invariante rispetto alla permutazione che può accettare un numero arbitrario di input (ad esempio, somma elemento per elemento, media o massimo). In particolare, 𝜙 e 𝜓 sono rispettivamente chiamate funzioni di aggiornamento e funzioni di messaggio. In modo intuitivo, in un blocco computazionale MPNN (Message Passing Neural Network), i nodi del grafo aggiornano le loro rappresentazioni aggregando i messaggi ricevuti dai loro vicini.

Gli output di uno o più strati MPNN sono le rappresentazioni dei nodi ℎ𝑢 per ciascun nodo 𝑢 ∈ 𝑉 nel grafo. Le rappresentazioni dei nodi possono essere utilizzate per qualsiasi compito successivo, come la classificazione dei nodi o dei grafi o la previsione delle connessioni (archi).

I nodi del grafico MPNN aggiornano la loro rappresentazione aggregando le informazioni dai loro vicini immediati. In quanto tale, l'impilamento ${\displaystyle n}$ I livelli MPNN fa sì che un nodo sarà in grado di comunicare con nodi che sono al massimo a ${\displaystyle n}$ "salti" di distanza. In linea di principio, per garantire che ogni nodo riceva informazioni da tutti gli altri nodi, sarebbe necessario impilare un numero di strati MPNN pari al diametro del grafico. Tuttavia, l'impilamento di molti strati MPNN può causare problemi come l'eccessivo livellamento e l'eccessivo schiacciamento. L'oversmoothing si riferisce al problema delle rappresentazioni dei nodi che diventano indistinguibili. L'oversquashing si riferisce al collo di bottiglia causato dalla compressione delle dipendenze a lungo raggio in rappresentazioni di dimensioni fisse. Le contromisure come le skip connections (già presenti nelle reti neurali residue), le regole di aggiornamento con gate e il jumping knowledge possono mitigare il fenomeno dell'oversmoothing. Modificando lo strato finale in modo che sia uno strato completamente adiacente, ovvero considerando il grafico come un grafico completo, è possibile mitigare l'oversquashing nei problemi in cui sono richieste dipendenze a lungo raggio.

Altre tipologie di MPNN sono state sviluppate in letteratura, come le reti convoluzionali grafiche e le reti di attenzione grafiche, le cui definizioni possono essere espresse in termini del formalismo MPNN.

La rete convoluzionale grafica (GCN) è stata introdotta per la prima volta da Thomas Kipf e Max Welling nel 2017.

Uno strato GCN definisce un'approssimazione del primo ordine di un filtro spettrale localizzato sui grafici. Le GCN possono essere intese come una generalizzazione delle reti neurali convoluzionali ai dati strutturati in grafici.

L'espressione formale di uno strato GCN è la seguente:

${\displaystyle \mathbf {H} =\sigma \left({\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}\mathbf {X} \mathbf {\Theta } \right)}$

Dove ${\displaystyle \mathbf {H} }$ è la matrice delle rappresentazioni dei nodi ${\displaystyle \mathbf {h} _{u}}$, ${\displaystyle \mathbf {X} }$ è la matrice delle caratteristiche del nodo ${\displaystyle \mathbf {x} _{u}}$, ${\displaystyle \sigma (\cdot )}$ è una funzione di attivazione (ad esempio, ReLU ), ${\displaystyle {\tilde {\mathbf {A} }}}$ è la matrice di adiacenza del grafico con l'aggiunta di auto-cicli, ${\displaystyle {\tilde {\mathbf {D} }}}$ è la matrice del grado del grafico con l'aggiunta di auto-cicli, e ${\displaystyle \mathbf {\Theta } }$ è una matrice di parametri addestrabili.

In particolare, lascia che ${\displaystyle \mathbf {A} }$ sia la matrice di adiacenza del grafico: allora, si può definire ${\displaystyle {\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {I} }$ E ${\displaystyle {\tilde {\mathbf {D} }}_{ii}=\sum _{j\in V}{\tilde {A}}_{ij}}$, Dove ${\displaystyle \mathbf {I} }$ denota la matrice identità . Questa normalizzazione assicura che gli autovalori di ${\displaystyle {\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}}$ sono limitati nell'intervallo ${\displaystyle [0,1]}$, evitando instabilità numeriche e gradienti esplosivi/svanenti .

Una limitazione dei GCN è che non consentono funzionalità di bordo multidimensionali ${\displaystyle \mathbf {e} _{uv}}$ È tuttavia possibile associare pesi scalari ${\displaystyle w_{uv}}$ ad ogni bordo imponendo ${\displaystyle A_{uv}=w_{uv}}$, ovvero impostando ogni elemento diverso da zero nella matrice di adiacenza uguale al peso del bordo corrispondente.

La rete di attenzione del grafico (GAT) è stata introdotta da Petar Veličković et al. nel 2018.

La rete di attenzione grafica è una combinazione di una rete neurale grafica e di un livello di attenzione. L'implementazione del livello di attenzione nelle reti neurali grafiche aiuta a focalizzare l'attenzione sulle informazioni importanti dei dati, anziché focalizzarsi sui dati nel loro complesso.

Uno strato GAT multi-testa può essere espresso come segue:

${\displaystyle \mathbf {h} _{u}={\overset {K}{\underset {k=1}{\Big \Vert }}}\sigma \left(\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)}$

Dove ${\displaystyle K}$ è il numero di teste di attenzione, ${\displaystyle {\Big \Vert }}$ denota la concatenazione dei vettori, ${\displaystyle \sigma (\cdot )}$ è una funzione di attivazione (ad esempio, ReLU ), ${\displaystyle \alpha _{ij}}$ sono coefficienti di attenzione, e ${\displaystyle W^{k}}$ è una matrice di parametri addestrabili per la ${\displaystyle k}$ -esima testa di attenzione.

Per lo strato GAT finale, si calcola la media degli output di ogni testa di attenzione prima dell'applicazione della funzione di attivazione. Formalmente, lo strato GAT finale può essere scritto come:

${\displaystyle \mathbf {h} _{u}=\sigma \left({\frac {1}{K}}\sum _{k=1}^{K}\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)}$

L'attenzione nell'apprendimento automatico è una tecnica che imita l'attenzione cognitiva . Nel contesto dell'apprendimento sui grafici, il coefficiente di attenzione ${\displaystyle \alpha _{uv}}$ misura quanto è importante il nodo ${\displaystyle u\in V}$ al nodo ${\displaystyle v\in V}$ .

I coefficienti di attenzione normalizzati vengono calcolati come segue:

${\displaystyle \alpha _{uv}={\frac {\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {x} _{u}\Vert \mathbf {W} \mathbf {x} _{v}\Vert \mathbf {e} _{uv}]\right))}{\sum _{z\in N_{u}}\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {x} _{u}\Vert \mathbf {W} \mathbf {x} _{z}\Vert \mathbf {e} _{uz}]\right))}}}$

Dove ${\displaystyle \mathbf {a} }$ è un vettore di pesi apprendibili, ${\displaystyle \cdot ^{T}}$ indica la trasposizione, ${\displaystyle \mathbf {e} _{uv}}$ sono le caratteristiche del bordo (se presenti) e ${\displaystyle {\text{LeakyReLU}}}$ è una funzione di attivazione ReLU modificata . I coefficienti di attenzione sono normalizzati per renderli facilmente confrontabili tra diversi nodi.

Un GCN può essere visto come un caso speciale di GAT in cui i coefficienti di attenzione non sono apprendibili, ma fissi e uguali ai pesi dei bordi ${\displaystyle w_{uv}}$ .

La rete neurale a sequenza di grafici gated (GGS-NN) è stata introdotta da Yujia Li et al. nel 2015. Il GGS-NN estende la formulazione GNN di Scarselli et al. alle sequenze di output. Il framework di passaggio dei messaggi è implementato come una regola di aggiornamento in una cella GRU ( gate recurrent unit ).

Una GGS-NN può essere espressa come segue:

${\displaystyle \mathbf {h} _{u}^{(0)}=\mathbf {x} _{u}\,\Vert \,\mathbf {0} }$

${\displaystyle \mathbf {m} _{u}^{(l+1)}=\sum _{v\in N_{u}}\mathbf {\Theta } \mathbf {h} _{v}}$

${\displaystyle \mathbf {h} _{u}^{(l+1)}={\text{GRU}}(\mathbf {m} _{u}^{(l+1)},\mathbf {h} _{u}^{(l)})}$

Dove ${\displaystyle \Vert }$ denota la concatenazione dei vettori, ${\displaystyle \mathbf {0} }$ è un vettore di zeri, ${\displaystyle \mathbf {\Theta } }$ è una matrice di parametri apprendibili, ${\displaystyle {\text{GRU}}}$ è una cellula GRU e ${\displaystyle l}$ indica l'indice della sequenza. In una GGS-NN, le rappresentazioni dei nodi sono considerate gli stati nascosti di una cella GRU. Le caratteristiche del nodo iniziale ${\displaystyle \mathbf {x} _{u}^{(0)}}$ sono riempiti con zeri fino alla dimensione dello stato nascosto della cella GRU. La stessa cella GRU viene utilizzata per aggiornare le rappresentazioni di ciascun nodo.

Gli strati di pooling locale rendono il grafico più grossolano tramite il downsampling. Presentiamo qui diverse strategie di pooling locale apprendibili che sono state proposte. Per ogni caso, l'input è il grafico iniziale rappresentato da una matrice ${\displaystyle \mathbf {X} }$ delle caratteristiche del nodo e della matrice di adiacenza del grafico ${\displaystyle \mathbf {A} }$ . L'output è la nuova matrice ${\displaystyle \mathbf {X} '}$ delle caratteristiche dei nodi e la nuova matrice di adiacenza del grafico ${\displaystyle \mathbf {A} '}$ .

Per prima cosa abbiamo impostato

${\displaystyle \mathbf {y} ={\frac {\mathbf {X} \mathbf {p} }{\Vert \mathbf {p} \Vert }}}$

Dove ${\displaystyle \mathbf {p} }$ è un vettore di proiezione apprendibile. Il vettore di proiezione ${\displaystyle \mathbf {p} }$ calcola un valore di proiezione scalare per ciascun nodo del grafico.

Lo strato di pooling top-k può quindi essere formalizzato come segue:

${\displaystyle \mathbf {X} '=(\mathbf {X} \odot {\text{sigmoid}}(\mathbf {y} ))_{\mathbf {i} }}$

${\displaystyle \mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }}$

Dove ${\displaystyle \mathbf {i} ={\text{top}}_{k}(\mathbf {y} )}$ è il sottoinsieme di nodi con i punteggi di proiezione più alti, ${\displaystyle \odot }$ denota la moltiplicazione di matrici elemento per elemento, e ${\displaystyle {\text{sigmoid}}(\cdot )}$ è la funzione sigmoide . In altre parole, i nodi con i punteggi di proiezione più alti tra i k vengono mantenuti nella nuova matrice di adiacenza ${\displaystyle \mathbf {A} '}$ . IL ${\displaystyle {\text{sigmoid}}(\cdot )}$ l'operazione rende il vettore di proiezione ${\displaystyle \mathbf {p} }$ addestrabile tramite backpropagation, che altrimenti produrrebbe output discreti.

Per prima cosa abbiamo impostato

${\displaystyle \mathbf {y} ={\text{GNN}}(\mathbf {X} ,\mathbf {A} )}$

Dove ${\displaystyle {\text{GNN}}}$ è uno strato GNN equivariante di permutazione generico (ad esempio, GCN, GAT, MPNN).

Lo strato di pooling dell'auto-attenzione può quindi essere formalizzato come segue:

${\displaystyle \mathbf {X} '=(\mathbf {X} \odot \mathbf {y} )_{\mathbf {i} }}$

${\displaystyle \mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }}$

Dove ${\displaystyle \mathbf {i} ={\text{top}}_{k}(\mathbf {y} )}$ è il sottoinsieme di nodi con i punteggi di proiezione più alti, ${\displaystyle \odot }$ indica la moltiplicazione di matrici elemento per elemento .

Lo strato di pooling dell'autoattenzione può essere visto come un'estensione dello strato di pooling top-k. A differenza del pooling top-k, i punteggi di auto-attenzione calcolati nel pooling di auto-attenzione tengono conto sia delle caratteristiche del grafico sia della topologia del grafico.

Le reti neurali grafiche sono uno degli elementi fondamentali di AlphaFold, un programma di intelligenza artificiale sviluppato da DeepMind di Google per risolvere il problema del ripiegamento delle proteine in biologia . AlphaFold ha ottenuto il primo posto in diverse competizioni CASP .

I social network rappresentano un importante ambito applicativo per le reti GNN, grazie alla loro rappresentazione naturale come grafici sociali . Le GNN vengono utilizzate per sviluppare sistemi di raccomandazione basati sia sulle relazioni sociali che sulle relazioni tra gli elementi.

Le GNN sono utilizzate come elementi costitutivi fondamentali per diversi algoritmi di ottimizzazione combinatoria. Esempi includono il calcolo dei percorsi più brevi o dei circuiti euleriani per un dato grafico, derivando posizionamenti di chip superiori o competitivi rispetto alle soluzioni umane artigianali, e migliorando le regole di diramazione progettate da esperti in branch and bound .

Una rete di computer, se visualizzata come un grafico, può essere analizzata con GNN per il rilevamento di anomalie. Le anomalie nei grafici di provenienza sono spesso correlate ad attività dannose all'interno della rete. Le GNN sono state utilizzate per identificare queste anomalie sui singoli nodi ^[5] e all'interno dei percorsi ^[6] per rilevare processi dannosi, o a livello di bordo ^[7] per rilevare movimenti laterali .

I sistemi di distribuzione idrica possono essere modellati come grafici, rappresentando quindi un'applicazione semplice della GNN. Questo tipo di algoritmo è stato applicato alla previsione della domanda di acqua, ^[8] interconnettendo le aree di misurazione distrettuali per migliorare la capacità di previsione. Un'altra applicazione di questo algoritmo sulla modellazione della distribuzione dell'acqua è lo sviluppo di metamodelli. ^[9]

V · D · M Apprendimento automatico
Problemi	Teoria dell'apprendimento statistico · Classificazione · Regressione · Regole di associazione · Apprendimento non supervisionato · Apprendimento supervisionato · Apprendimento per rinforzo · Apprendimento profondo
Apprendimento non supervisionato	Clustering · Clustering gerarchico · K-means · Algoritmo EM · DBSCAN · Mean shift · Rete generativa avversaria (cGAN · VAE-GAN · cycleGAN)
Apprendimento supervisionato	Albero di decisione · Foresta casuale · Conditional random fields CRF · Modello di Markov nascosto · K-nearest neighbors · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Modelli grafici · Macchine a vettori di supporto
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Analisi della correlazione canonica (CCA) · Analisi delle componenti indipendenti (ICA) · Analisi discriminante lineare (LDA) · Analisi delle componenti principali (PCA) · Selezione delle caratteristiche · Estrazione di caratteristiche · t-distributed stochastic neighbor embedding (t-SNE)
Reti neurali artificiali	Percettrone · Rete neurale a base radiale · Rete bayesiana · Rete neurale feed-forward · Rete di Hopfield · Percettrone multistrato · Rete neurale ricorrente (LSTM) · Macchina di Boltzmann ristretta · Mappa auto-organizzata · Rete neurale convoluzionale · Rete neurale a ritardo · Rete neurale spiking · Rete neurale grafica · Trasformatore
Software	Keras · Microsoft Cognitive Toolkit · Scikit-learn · TensorFlow · Theano · Torch · Weka
Altro	Algoritmo genetico · Particle Swarm Optimization · Caratteristica · Compromesso bias-varianza · Minimizzazione del rischio empirico