Geometric deep learning 1: graph convolutional network

Negli ultimi anni, il graph machine learning ha riscosso grande interesse nella communità di ricerca, grazie alla sua capacità di modellare nativamente ogni tipo di informazione espressa sotto forma di un grafo (solo per citare alcuni esempi: amicizie ed interessi sui social network, reti di sensori, citazioni fra articoli, struttura di molecole e proteine...). Tantissimi gli approcci al tema, dai graph kernel alle "italianissime" graph neural network sviluppate già un decennio fa, arrivando al più recente revival sotto il nome di geometric deep learning, ovvero il tentativo di estendere tecniche in voga nel deep learning (es., reti convolutive) per inglobare al loro interno l'informazione contenuta nel grafo stesso. In questo articolo vediamo una breve introduzione a quest'ultimo campo, soffermandoci poi su un modello in particolare, le graph convolutional network. Dopo averne discusso l'architettura (più o meno informalmente) concludiamo con un vero caso d'uso (con notebook Jupyter) su un dataset di testi.

Chi ha paura dei grafi?

Per capire l'importanza dei grafi, consideriamo per un istante due delle architetture di deep learning più usate (reti convolutive e reti ricorrenti), per discutere il motivo del loro successo. In entrambi i casi, come vedremo, il vero punto di forza, più che la pura flessibilità, è la loro capacità di saper sfruttare al meglio la conoscenza delle interconnessioni fra i dati in input (quasi sempre spaziali nel primo caso, temporali nel secondo), conoscenza intrinseca nel modo stesso in cui sono costruite. Prendiamo ad esempio un singolo filtro convolutivo in una rete convolutiva:

Sono due le assunzioni essenziali codificate in questo filtro:

1. in primo luogo, che i dati necessari ad elaborare un singolo pixel (per estrarne una feature) si trovino nei pixel a lui vicini (tipicamente, a due o tre pixel di distanza), mentre i pixel più distanti possano essere ignorati;
2. che la feature estratta dalla rete si possa ritrovare invariata sull'intera immagine (motivo per il quale il filtro scorre sull'immagine mantenendo gli stessi parametri).

Sono queste due assunzioni, ancora più che la discesa al gradiente, a rendere di enorme successo le reti convolutive, permettendo di utilizzare un numero di parametri infinitamente minore rispetto ad una rete interamente connessa. Dietro di esse si cela, in realtà, un grafo: infatti, la nozione di "vicinanza" dei pixel (punto 1) equivale a rappresentare l'immagine come un grafo dalla struttura perfettamente regolare:

(Tra l'altro, come nota a margine, non sempre questo grafo completamente regolare è la rappresentazione ideale per un'immagine: si veda ad esempio il recente campo del graph image processing ¹.)

Sfruttare questa informazione di vicinanza tra i pixel è il "cuore" di una rete convolutiva, ed un discorso molto simile vale per le reti ricorrenti, che sfruttano invece l'organizzazione temporale del segnale, la quale può essere rappresentata come un grafo ancora più semplice:

Sia i pixel in un'immagine che i campioni in un file audio sono interconnessi in un modo estremamente regolare. Nella maggior parte dei casi descritti nell'introduzione, però, l'informazione contenuta sul grafo a nostra disposizione non è così regolare, con alcuni nodi quasi isolati, altri molto "centrali", ecc. (si pensi ad esempio alle amicizie su un social network). La domanda fondamentale del graph machine learning, quindi, è come sfruttare questa informazione, senza sacrificare efficienza o flessibilità delle architetture?

Ad esempio: possiamo generalizzare le idee di prima, di località e di invarianza, per progettare reti convolutive che lavorino su grafi generici? Il seguito di questo articolo tenta di rispondere a questa domanda.

Grafi, matrici di adiacenza, ed inferenza su grafi

Consideriamo quindi un generico grafo come quello sotto:

Come prima, ogni nodo nel grafo rappresenta un elemento su cui abbiamo misurato un "segnale" (es., i singoli pixel in un'immagine), e le connessioni fra i nodi rappresentano legami noti fra i vertici (es., vicinanza spaziale, o amicizia su un social network). Di alcuni nodi potremmo poi conoscere delle etichette (i colori nella figura di prima).

Matematicamente, un grafo può essere rappresentato da una matrice di adiacenza, che per ogni nodo specifica la connessione (eventualmente pesata) verso tutti gli altri nodi:

Introduciamo qualche simbolo: il grafo su cui lavoreremo ha genericamente $N$ nodi, su ciascuno dei quali è definito un segnale $\mathbf{x}_n \in \mathbb{R}^C$ (dove $C$ è il numero di "canali" del segnale, es., 3 colori per un pixel). Denotiamo con $\mathbf{X}$ la matrice $N \times C$ che colleziona su ogni riga il segnale definito sul rispettivo nodo. Infine, $\mathbf{A}$ sarà la matrice $N \times N$ di adiacenza (come quelle sopra).

L'inferenza sul grafo comprende numerosi task definiti sul grafo stesso tra cui, ad esempio:

1. Predire le etichettte per alcuni nodi: si pensi ad esempio ad un grafo stradale, nel quale misuriamo il traffico solo su alcune intersezioni e vogliamo conoscerlo su quelle rimanenti;
2. Suddividere i nodi in cluster non noti a priori (unsupervised learning su grafi);
3. Classificare l'intero grafo, ad esempio per predire una caratteristica chimica di una determinata proteina.

Quello che accomuna tutti questi casi è la necessità di una architettura che elabori il segnale prendendo in considerazione la struttura del grafo. Come detto prima, ci concentriamo qui su un modello specifico, le graph convolutional network (GCN) ².

Graph convolutional network (informale)

Per comprendere il funzionamento delle GCN, ignoriamo per un attimo le connessioni fra i vari nodi. In questo caso, una rete neurale "classica" che operasse su ciascun nodo si comporrebbe di strati del tipo:

\[ g(\mathbf{X}) = \text{ReLU}( \mathbf{X}\mathbf{W} )\]

dove $W$ è la matrice di pesi dello strato e $\text{ReLU}(s) = \max(0,s)$ (o qualsiasi altra funzione di attivazione). Questo schema processa ogni nodo in maniera indipendente, ignorando completamente le connessioni fra di essi, e di conseguenza una quantità potenzialmente molto importante di informazione (come vedremo più sotto nella demo). Purtroppo, sostituire l'operazione di prima con una "convoluzione", come usata nelle classiche reti convolutive, non è banale a causa dell'irregolarità del grafo stesso, in quanto ogni nodo può avere un numero estremamente variabile di vicini.

Consideriamo però questa semplice variante, dove il cambiamento è evidenziato in rosso:

\[ g(\mathbf{X}) = \text{ReLU}( \mathbf{\color{red}A} \mathbf{X}\mathbf{W} )\]

La nuova matrice $\mathbf{A}$ è proprio la matrice di adiacenza introdotta prima. Possiamo concepire questa operazione come composta di tre parti in successione:

1. La prima, uguale a prima, processo il segnale su ciascun nodo in maniera indipendente tramite la moltiplicazione con $\mathbf{W}$.
2. La seconda fase, la moltiplicazione per la matrice di adiacenza, effettua una seconda combinazione lineare, fra i segnali di ogni nodo e dei rispettivi vicini ³. A differenza della prima fase, i coefficienti di questa combinazione sono fissi.
3. La terza fase, nuovamente uguale a prima, applica la nonlinearità scelta sui vari nodi.

La logica è simile a quella di una rete convolutiva: l'informazione elaborata da ciascun "filtro" dipende solo dagli immediati vicini del nodo, mentre le stesse operazioni (definite dalla matrice $\mathbf{W}$) vengono applicate su tutti i nodi del grafo in simultanea. A differenza delle reti convolutive, la seconda operazione non dipende da alcun parametro adattabile, ma in pratica questo non sembra comportare grandi cali di prestazione. Possiamo in effetti combinare più strati di questo tipo, per ottenere architetture che "diffondono" l'informazione sul grafo stesso tramite ripetute moltiplicazioni per $\mathbf{A}$:

Ad esempio, una rete formata da tre strati di questo tipo, anche senza ottimizzazione, produce una separazione fra i nodi del grafo di prima molto simile alla loro reale categorizzazione:

Non solo: questo modello ha anche una solida teoria alle spalle, come vediamo nella prossima sezione.

Teoria: graph convolution e graph Fourier transform

Un aspetto molto interessante delle GCN è che si legano alla teoria sull'analisi spettrale dei grafi, ed in particolar modo al graph signal processing ⁴. Questo dona una forte giustificazione teorica ai metodi, oltre ad ispirare tecniche di vario tipo per semplificarne la modellazione.

Buona parte di questa teoria parte dall'analisi della cosidetta matrice Laplaciana, definita come (nel caso di grafi senza direzionalità delle connesioni):

\[ \begin{equation} \mathbf{L} = \mathbf{D} - \mathbf{A} \end{equation}\]

dove $\mathbf{D}$ è una matrice diagonale contenente sulla diagonale il grado (numero di nodi vicini) di ciascun nodo. L'analisi di questa matrice rivela molte informazioni utili sul segnale, in particolar modo quando consideriamo la sua decomposizione spettrale in autovettori ed autovalori. Tra le varie cose, si può dimostrare che la matrice $\mathbf{U}$ di autovettori definisce una transformazione del segnale molto simile alla classica trasformata di Fourier, chiamata appunto graph Fourier transform (consideriamo per semplicità un solo canale):

\[ \hat{\mathbf{x}} = \mathbf{U}\mathbf{x}\]

Nel caso di un segnale temporale, la trasformata di Fourier permette di rappresentarlo tramite una somma pesata di sinusoidi di frequenza crescente, i cui coefficienti vengono detti appunto coefficienti di Fourier; in questo caso, l'equivalente dei coefficienti di Fourier è rappresentato da $\hat{\mathbf{x}}$, mentre l'equivalente delle "sinusoidi" è dato dagli autovettori, una volta ordinati in base ai loro autovalori:

Nella figura sopra, ad esempio, vengono rappresentati quattro di questi autovettori estratti dalla matrice Laplaciana del grafo, ordinati in base agli autovalori: come si vede, il primo autovettore rappresenta una segnale a frequenza costante sul grafo, mentre i contenuti a "frequenze più alte" tendono ad oscillare maggiormente fra i vicini. L'analisi di autovettori ed autovalori di questa matrice, e la rappresentazione di un segnale come somma di questi contributi, è alla base del graph signal processing. (L'equivalenza tra la trasformata classica e quella su grafi non è però perfetta, e ne esistono definizioni alternative.)

Per capire la relazione di tutto questo con le GCN, ricordate che una convoluzione (per un segnale definito nel tempo) può essere vista come una moltiplicazione in frequenza. Una proprietà simile vale anche sui grafi, considerando appunto la trasformazione di prima come l'equivalente della più classica trasformata di Fourier. Basandoci su questo, un modo teoricamente corretto di definire uno strato convolutivo di una rete neurale su grafi è di eseguire la convoluzione nel dominio spettrale:

\[ g(\mathbf{x}) = \text{ReLU}( \mathbf{U}^T\mathbf{\Lambda}\mathbf{U}\mathbf{x} )\]

dove la matrice diagonale $\mathbf{\Lambda}$ rappresenta l'operazione di filtraggio, mentre la moltiplicazione finale per $\mathbf{U}^T$ riporta il segnale nel dominio originale. Questa idea, originariamente proposta da Bruna et al. nel 2013 ⁵, richiede però una doppia moltiplicazione con $\mathbf{U}$, estremamente costosa, oltre a non possedere l'idea della "località" delle operazioni di filtraggio.

Buona parte del geometric deep learning si è evoluto cercando di semplificare questa operazione. In particolare, Kipf e Welling ² dimostrano come il modello che abbiamo visto prima, la GCN, corrisponda a sostituire la moltiplicazione per $\mathbf{\Lambda}$ con un più semplice filtro lineare sugli autovalori della matrice Laplaciana. Se questa (rapidissima) panoramica vi ha interessato, vi rimandiamo a Bronstein et al. ⁶ per una discussione completa sui vari metodi... perché per noi è ora di passare al codice!

Demo: GCN per la classificazione di testi (PyTorch)

La demo usa l'implementazione ufficiale delle GCN in PyTorch. Come caso pratico consideriamo il dataset CORA:

• Il dataset è composto da 2708 pubblicazioni scientifiche da categorizzare in sette macro-argomenti (es., "Neural_Networks").
• Ciascun documento è rappresentato da una bag-of-words di 1433 termini, ovvero, ogni documento è rappresentanto da un vettore di 1433 valori numerici corrispondenti alla frequenza delle rispettive parole nel testo.
• In fase di training, conosciamo la categoria di circa il 5% dei documenti, e vogliamo predirla per il restante 95%.
• Per aiutarci, conosciamo le citazioni fra i vari documenti, che permettono di creare un grafo di adiacenza con 1433 nodi (i documenti) e 5429 connessioni (le citazioni note).

Ci soffermiamo solo su alcuni aspetti essenziali del codice, lasciando la maggior parte dei dettagli al notebook. Consideriamo la fase di caricamento dei dati:

A, X, y, idx_train, idx_val, idx_test = load_data(path='pygcn/data/cora/')

Come in ogni problema di classificazione, abbiamo a disposizione la matrice di feature per ciascun input (2708 x 1433), e le corrispettive classi (2708 x 7), oltre ad uno split del dataset. Oltre a questi dati, però, abbiamo a nostra disposizione anche l'informazione sulle citazioni, rappresentata dalla matrice di adiacenza A (2708 x 2708).

Ignorando la matrice di adiacenza, come suggerito prima, potremmo allenare una rete neurale che lavori solo sulla bag-of-words di ogni documento:

net = nn.Sequential(
    nn.Linear(1433, 100), 
    nn.ReLU(), 
    nn.Linear(100, 7)
)

Allenandola con Adam e minimizzando la cross-entropia sui documenti di training, otteniamo però una accuratezza piuttosto deludente del 50%. Vediamo ora parte dell'implementazione dello strato convolutivo definito con il grafo:

class GraphConvolution(Module):
    """
    Simple GCN layer, similar to https://arxiv.org/abs/1609.02907
    """
    [...]

    def forward(self, input, adj):
        support = torch.mm(input, self.weight)
        output = torch.spmm(adj, support)
        return output + self.bias

Si noti la semplicità dell'implementazione: l'unica differenza rispetto ad uno strato classico è la seconda moltiplicazione, che introduce la combinazione degli elementi in base all'informazione del grafo (inoltre, la moltiplicazione è effettuata con una routine ottimizzata per matrici sparse, per massimizzarne l'efficienza).

Semplicemente utilizzando due di questi strati, con la stessa ottimizzazione di prima, raggiungiamo un'accuratezza dell'81%! Non solo: questo lo otteniamo senza aggiungere parametri aggiuntivi al modello.

Vale la pena, prima di concludere, discutere anche alcuni svantaggi di questo modello. In primo luogo, creare dei batch di dati è ora più complicato di prima, in quanto per ottenere una singola predizione abbiamo bisogno anche dei vicini per il primo strato, dei vicini dei vicini per il secondo, e così via. Per questo, quasi tutte le implementazioni tendono a lavorare sull'intero grafo. Inoltre, l'operazione di pooling, così semplice su un'immagine, è qui estremamente complessa, proprio a causa della natura irregolare del grafo.

Nonostante queste limitazioni, come abbiamo visto in questo semplice esempio, la capacità di processare nativamente l'informazione contenuta in un grafo risulta di eccezionale valore per un modello predittivo. Ovviamente, le GCN (ed il geometric deep learning), rappresentano solo uno dei tantissimi modi sviluppati di recente a questo fine: dalle graph attention networks, alle neural graph machine, passando per le graph network di Google's DeepMind. Se il tema vi interessa, continuate a seguirci per i nostri prossimi articoli sul graph machine learning!

Previous Post Next Post