In questa sezione vengono descritti alcuni degli approcci al problema dell’ap- prendimento su grafi tramite reti neurali.
La Relational Neural Network (RelNN) [30] è un modello di rete neurale definito su grafi aciclici e alberi, che può essere esteso al dominio dei grafi ciclici tramite preprocessing del dataset di input. Lo scopo del preprocessing è di trasformare grafi ciclici in alberi; la trasformazione avviene tramite una visita breadth-first del grafo, il cui punto di partenza è il vertice “di output” del grafo, un vertice che viene scelto secondo un qualche criterio come quello a cui associare il target per l’intero grafo (il modello è direttamente applicabile solo a problemi di trasduzione scalare). Ad ogni passo della visita alla copia del vertice corrente v già inserita nell’albero vengono collegati, come figli, tutti i vertici che appartengono al suo vicinato; il processo continua finchè l’albero non raggiunge una certa profondità predefinita.
Questo modello presenta alcuni punti in comune con le reti neurali ricorsive, come la limitazione al dominio dei grafi aciclici, e l’utilizzo dello stesso algoritmo d’apprendimento, la Backpropagation through structure [26], per l’aggiornamento dei pesi della rete. Si differenzia però dal precedente per la realizzazione dell’en- coding network, che è implementata da una rete neurale ricorrente: la codifica per il vertice v dell’albero è calcolata come l’output di una rete ricorrente applicata alla sequenza formata dalle codifiche dei figli del vertice, ordinati secondo un certo criterio. L’ordinamento dei figli di un vertice, se non è dato dalla struttura del grafo (ad esempio se i grafi sono posizionali o ordinati), può influire nel processo d’apprendimento.
Il Graph Neural Network model (GNN), illustrato in [27], viene invece proposto come una estensione del modello ricorsivo in grado di trattare anche grafi ciclici.
Anche in questo modello il grafo viene processato da un insieme di unità, una per ogni vertice, connesse tra loro in base alla topologia del grafo. Ogni unità calcola uno stato per il vertice associato, basandosi sulle informazioni locali del vertice (ovvero la sua label I(v)) e sulle informazioni sui suoi vicini, N (v).
Più formalmente, indicando con x(v) la funzione di stato e con o(v) la funzione di output,
x(v) = fw I(v), I(N (v)), I(eN (v)), x(N (v))
(2.11)
o(v) = yw(I(v), x(v)) (2.12)
La funzione di stato è ricorsiva e, come prima, se il grafo è ciclico si creano delle dipendenze cicliche anche nelle connessioni della rete neurale. La soluzione proposta in [27] consiste nel calcolare lo stato tramite un processo iterativo, che si fermerà al raggiungimento di un punto di equilibrio (punto fisso). Il teorema del punto fisso di Banach assicura che, se la funzione fw è contrattiva1, il sistema di equazioni ammette una soluzione unica. Affinchè quindi il modello sia applicabile ad un grafo non diretto o comunque contenente cicli, è necessario che vengano imposte sulla funzione fw (ovvero, sui pesi della rete neurale) dei vincoli che assicurino la contrattività della funzione di stato.
L’equazione di stato 2.11 diventa quindi
xt+1(v) = fw I(v), I(N (v)), I(eN (v)), xt(N (v))
(2.13) Durante l’algoritmo di apprendimento vengono quindi eseguiti due compiti: ad ogni epoca, si calcolano i nuovi valori per i pesi w, con lo scopo di minimizza- re l’errore della funzione di loss, e successivamente si esegue il processo iterativo che permette di calcolare il punto fisso di x(v); la necessità di questo processo di convergenza aggiunge ovviamente un’ulteriore costo al processo di apprendimento. A dimostrazione dell’interesse per questo settore dell’apprendimento automatico da parte della ricerca, molto recentemente, in [31], è stato presentato un approccio
che incorpora alcuni degli aspetti di RelNN e di GNN in un nuovo modello per problemi relazionali, chiamato Recurrent Neural Collective Classification (RNCC). Il modello sfrutta, come RelNN, dei neuroni ricorrenti per aggregare le informazioni sul vicinato di un vertice e utilizzarle per la classificazione, che viene poi rifinita tramite successive iterazioni, come in GNN.
Il modello Graph Echo State Network (GESN, [28]) appartiene invece al para- digma del Reservoir Computing, ed è una estensione della Echo State Network per sequenze [32] al dominio dei grafi.
In questo paradigma si ha una separazione concettuale delle unità della rete in due layer: il reservoir, costituito da molte unità non lineari, non completamen- te connesso e con connessioni casuali, e il read-out, un layer con unità (di solito) lineari. La principale differenza tra i due livelli di unità, che caratterizza questo approccio, sta nel fatto che, mentre le unità di output del readout vengono nor- malmente allenate, le unità del reservoir vengono solamente inizializzate, seguendo delle specifiche regole, ma non allenate.
In GESN il reservoir ha la stessa funzione dell’hidden layer nelle reti neurali ri- corsive: ricavare dal grafo in input la sua codifica, che verrà poi usata dal read-out della rete per produrre l’output del modello per quel grafo. Il reservoir viene inizia- lizzato di modo che la funzione di stato calcolata sia contrattiva, come per GNN: anche in questo caso questa proprietà è necessaria per garantire la convergenza e la stabilità della funzione di codifica.
Anche in questo modello infatti la codifica di un vertice viene calcolata tramite il processo iterativo descritto dall’equazione
xt+1(v) = τE(I(v), xt(N (v))) (2.14) fino al raggiungimento del punto fisso di x(v). Contrariamente a quanto detto per GNN però, punto di forza di questo modello è l’efficienza del calcolo della co- difica durante il training, in quanto, nonostante sia sempre necessario un processo iterativo, il reservoir non deve essere allenato, mentre in GNN devono essere alter- nate le due fasi, che possono essere computazionalmente onerose, dell’allenamento delle unità e della convergenza al punto fisso dell’equazione iterativa.