Il mondo come grafo#
Fermati un attimo a guardare i dati che ti circondano. I tuoi contatti sul telefono non sono un elenco: sono una rete di persone che, a loro volta, si conoscono tra loro. Una molecola non è una lista di atomi, ma un intreccio di legami. Il web non è una pila di pagine, bensì un tessuto di link. La rete stradale di una città, i pagamenti tra conti bancari, le citazioni tra articoli scientifici, le proteine che interagiscono in una cellula: in tutti questi casi l’informazione più preziosa non sta dentro le singole cose, ma nei collegamenti fra loro. Guardare una cosa alla volta, qui, non basta più: conta anche chi le sta accanto.
Le reti che abbiamo studiato finora (quelle convoluzionali per le immagini, quelle ricorrenti e i Transformer per il testo) sono nate per dati con una forma regolare: una griglia di pixel, una sequenza di parole. Ma un grafo non ha né una griglia né un ordine. È una struttura più libera e, proprio per questo, più difficile da dare in pasto a una rete neurale. Questo capitolo racconta come si fa; questa prima sezione mette in fila il vocabolario e i problemi di fondo, per capire perché servono strumenti nuovi.
Nodi e archi: l’anatomia di un grafo#
Un grafo è la cosa più semplice del mondo: un insieme di puntini e un insieme di linee che li collegano. I puntini si chiamano nodi, le linee archi. Tutto il resto è dettaglio: importante, ma dettaglio. (Chi incontra i grafi altrove li troverà chiamati anche vertici e spigoli: sono le stesse due cose, e in questo libro restano nodi e archi.) La Fig. 28.2 mostra un grafo minuscolo, cinque nodi, che useremo come filo conduttore per l’intera sezione.
Fig. 28.2 Un grafo di 5 nodi. Accanto a ogni nodo, le tre caselle sono le sue caratteristiche, un numero per casella (nel disegno restano vuote: quali numeri ci finiscano dentro dipende da che cosa sono i nodi). A destra le stesse informazioni messe in tabella: la tabella \(\mathbf{A}\) dice chi è collegato a chi (si chiama matrice di adiacenza), la tabella \(\mathbf{X}\) raccoglie le caselle di tutti i nodi, una riga per nodo. In terracotta i tre archi che escono dal nodo 3: portano al suo vicinato, e siccome sono tre si dice che il nodo 3 ha grado 3 (che il grado coincida qui col numero che fa da nome al nodo è un caso).#
Nella didascalia sono già comparse le tre parole che ricorrono da qui alla fine del capitolo, e vale la pena non lasciarle lì: i nodi a cui un nodo è collegato sono i suoi vicini, tutti insieme sono il suo vicinato, e quanti sono è il suo grado. Una quarta parola riguarda le tabelle: una tabella di numeri, in matematica, si chiama matrice, quindi la tabella \(\mathbf{A}\) è la matrice \(\mathbf{A}\), e il libro userà l’una o l’altra parola indifferentemente.
Sistemiamo adesso tre distinzioni che tornano di continuo.
Gli archi possono avere o non avere un verso. In una rete di amicizie l’amicizia è reciproca, se sono tuo amico, sei mio amico: gli archi non hanno freccia, il grafo è non diretto. In una rete di «chi segue chi» sui social, invece, posso seguire una persona che non mi segue: ogni arco ha un verso, il grafo è diretto.
Gli archi possono anche avere un peso, cioè un numero che dice quanto è forte quel collegamento: tra due città il peso può essere la distanza in chilometri, tra due persone il numero di messaggi che si scambiano. Se non mettiamo pesi, è come dire che ogni arco vale 1: il collegamento o c’è o non c’è.
Infine, sia i nodi sia (a volte) gli archi portano con sé delle caratteristiche, in gergo feature: per una persona l’età e gli interessi, per un atomo il tipo di elemento. Nella figura sono le tre caselline accanto a ogni nodo: tre caselle in fila, una per caratteristica. Nel disegno restano vuote, perché quali numeri ci vadano dipende da che cosa sono i nodi; se fossero persone potrebbero esserci \(14\) (gli anni), \(2\) (gli sport che pratica), \(300\) (i messaggi che manda in un giorno). Una fila di numeri come questa si chiama vettore: quando più avanti si legge che un nodo «diventa un vettore», o che «i messaggi sono vettori», si intendono esattamente queste caselline in fila. Quante siano lo si decide una volta per tutte all’inizio, e poi è uguale per tutti i nodi: nel disegno sono tre perché tre ci stanno nella pagina, in un caso vero sono decine o centinaia.
E qui conviene mettere in fila i nomi, perché finora ne sono usciti tre per una cosa sola: fila di numeri, vettore, rappresentazione. Vettore è come si chiama l’oggetto: una fila di numeri, punto. La rappresentazione di un nodo, la parola dell’introduzione, è il vettore che in un certo momento descrive quel nodo: all’inizio sono proprio le caselline qui sopra, dopo un giro di ascolto sarà qualcos’altro. Non sono due oggetti diversi: è lo stesso oggetto, chiamato una volta col suo nome e una volta col suo mestiere.
Un grafo, insomma, è fatto di due cose insieme: una struttura (chi è connesso a chi) e dei contenuti (cosa sono i nodi).
Un grafo è una coppia \(G = (V, E)\), dove \(V\) è l’insieme dei nodi (\(N = |V|\)) ed \(E \subseteq V \times V\) l’insieme degli archi. La struttura si codifica nella matrice di adiacenza \(\mathbf{A} \in \{0,1\}^{N \times N}\):
Se il grafo è non diretto allora \(A_{ij} = A_{ji}\), cioè \(\mathbf{A}\) è simmetrica (\(\mathbf{A} = \mathbf{A}^\top\)); se è diretto non lo è in generale. In un grafo pesato lo 0/1 è sostituito dal peso \(w_{ij} \in \mathbb{R}\) dell’arco, e \(\mathbf{A}\) diventa una matrice reale. Le feature dei nodi si impilano nella matrice \(\mathbf{X} \in \mathbb{R}^{N \times F}\), la cui riga \(i\)-esima è il vettore \(\mathbf{x}_i \in \mathbb{R}^F\) delle \(F\) caratteristiche del nodo \(i\); eventuali feature di arco si raccolgono in un tensore analogo indicizzato dalle coppie.
Il grado di un nodo è il numero dei suoi vicini, cioè la somma della sua riga: \(\deg(i) = \sum_{j} A_{ij}\). I gradi si radunano nella matrice dei gradi \(\mathbf{D} \in \mathbb{R}^{N \times N}\), diagonale, con
dove \(D_{ii}\) è quante linee escono dal nodo \(i\). Le tre matrici \(\mathbf{A}\), \(\mathbf{X}\) e \(\mathbf{D}\) sono tutto ciò che serve per descrivere un grafo con feature: le ritroveremo in ogni formula del capitolo.
Perché i grafi mettono in crisi le reti classiche#
Cominciamo dalla mossa più ovvia, quella che verrebbe in mente a chiunque. La matrice \(\mathbf{A}\) si può srotolare, riga dopo riga, in un unico lungo elenco di numeri, e quell’elenco si può dare in pasto a una rete come quelle dei primi capitoli, che in ingresso vuole appunto una sfilza di numeri lunga sempre uguale. È quello che si fa con un’immagine, che in fondo è anch’essa una griglia di numeri (uno per pixel) srotolata. Non funziona, e capire perché non funziona è la chiave di tutto il capitolo. Il problema nasce da una libertà che griglie e sequenze non hanno: in un grafo i nodi non hanno un ordine.
Un’immagine è una griglia: il pixel in alto a sinistra è sempre in alto a sinistra, e la convoluzione sfrutta proprio questa regolarità. Una frase è una sequenza: la prima parola viene sempre prima della seconda, e i modelli per il testo su quell’ordine ci contano. Un grafo no: se rinumero i suoi nodi (chiamo «1» quello che prima chiamavo «3» e viceversa) è esattamente lo stesso grafo, ma la matrice \(\mathbf{A}\) cambia completamente aspetto.
È la cena dell’introduzione, guardata più da vicino. Se rifai l’elenco degli invitati in ordine diverso (prima per cognome, poi per età), la cena non è cambiata di una virgola: sono le stesse persone, le stesse amicizie. Ma se avessi scritto le amicizie come una tabella «riga per invitato», riordinando l’elenco la tabella si stravolge, pur descrivendo la stessa realtà.
Una rete che analizza i grafi deve capire questa cosa ovvia per noi: l’ordine in cui elenco i nodi non conta. Se le do lo stesso grafo con i nodi numerati in due modi diversi, la risposta non deve cambiare. Se la risposta è una sola per tutto il grafo («questa molecola è tossica»), dev’essere identica. Se è una risposta per ogni nodo, devono essere le stesse risposte attaccate agli stessi nodi: se prima «bot» toccava a quello che chiamavo 3, adesso deve toccare a quello stesso, comunque lo chiami. Le reti per immagini e testo, che invece si aspettano un ordine fisso, qui inciamperebbero: vedrebbero due grafi diversi dove ce n’è uno solo.
E ci sono altri due scogli, più piccoli ma altrettanto duri. Il secondo: nelle immagini ogni pixel ha sempre lo stesso numero di vicini, in una frase ogni parola ha una prima e una dopo; in un grafo no, un nodo può avere 2 vicini e un altro 100, e non esiste una finestra di dimensione fissa da far scorrere. Il terzo: ogni grafo ha un numero di nodi diverso, mentre le foto le possiamo tagliare tutte alla stessa misura, e una rete come quelle dei primi capitoli vuole in ingresso sempre la stessa quantità di numeri.
Chiamiamo \(\mathbf{P}\) una matrice di permutazione \(N \times N\) (una sola \(1\) per riga e colonna). Rinumerare i nodi significa trasformare \(\mathbf{A} \mapsto \mathbf{P} \mathbf{A} \mathbf{P}^\top\) e \(\mathbf{X} \mapsto \mathbf{P} \mathbf{X}\). Poiché questi descrivono lo stesso grafo, un modello sensato deve rispettare una di due proprietà. Per un compito che produce una risposta per l’intero grafo, serve l’invarianza a permutazione:
la predizione non cambia comunque si rinumerino i nodi. Per un compito che produce una risposta per nodo (un vettore per ciascuno), serve invece l’equivarianza a permutazione:
le uscite si permutano insieme agli ingressi. Progettare architetture che incorporano questa simmetria come bias induttivo (anziché sperare che la rete la impari a forza di esempi) è il cuore del programma della geometric deep learning [BBCVelivckovic21], che legge sotto un’unica lente CNN (equivarianza a traslazione degli strati convolutivi, con l’invarianza che arriva solo dal pooling globale finale) e GNN (equivarianza o invarianza a permutazione sul grafo). A ciò si aggiungono due irregolarità: il grado variabile (ogni nodo ha un numero diverso di vicini, quindi niente kernel di dimensione fissa) e la taglia variabile (\(N\) cambia da grafo a grafo, mentre una rete densa vuole un input di dimensione fissata). Sono esattamente i vincoli che il message passing della prossima sezione risolverà con un’operazione locale, condivisa e simmetrica.
Tre modi di fare una domanda a un grafo#
Sono i tre tipi di domanda già annunciati nell’introduzione del capitolo, e qui li guardiamo con calma, perché è a uno di questi tre stampi che ogni problema su grafo va ricondotto: si prevede qualcosa di un singolo nodo, di una coppia di nodi, o dell’intero grafo. La Fig. 28.3 li mette in fila sullo stesso grafo.
Fig. 28.3 I tre livelli di compito. Nodo: prevedere un’etichetta per ciascun nodo. Arco: prevedere se due nodi sono (o saranno) collegati (la link prediction). Grafo: prevedere una proprietà dell’intero grafo, per esempio se una molecola è tossica.#
Livello-nodo. A ogni nodo si assegna un’etichetta o un valore. È il caso di un social network in cui vogliamo classificare gli utenti (per esempio distinguere account autentici e bot), o di una rete di citazioni in cui prevediamo l’argomento di ciascun articolo.
Livello-arco. Si prevede se un arco esiste, o esisterà, tra due nodi: la link prediction. È il motore del «forse conosci…» di un social e del «chi ha comprato questo…» di un negozio online. È anche, alla lettera, la forma del problema che il capitolo sui sistemi di raccomandazione affronterà per intero: un grafo con gli utenti da una parte e i prodotti dall’altra, e consigliare un film vuol dire prevedere un arco che ancora non c’è.
Livello-grafo. Si prevede una proprietà dell’intero grafo, riassunto in un solo verdetto. L’esempio principe è la chimica: una molecola è un grafo di atomi e legami, e vogliamo prevedere se è solubile, tossica, o efficace come farmaco.
C’è poi una seconda domanda, che vale allo stesso modo per tutti e tre i casi appena visti: quali nodi abbiamo davanti mentre il modello impara? È la distinzione che più di ogni altra separa i metodi antichi da quelli moderni.
Immagina di dover indovinare l’argomento di ogni articolo in una biblioteca collegata da citazioni. In un caso hai già davanti tutti gli articoli, con le loro citazioni: di alcuni conosci l’argomento, di altri no, e devi solo riempire i buchi. Questo si dice modo transduttivo: il grafo è uno solo, fissato, e non arriverà mai nessun articolo nuovo.
In un altro caso, invece, vuoi imparare una regola che funzioni anche su articoli che non hai ancora visto, o addirittura su un’altra biblioteca. È il modo induttivo: si impara qualcosa di generale, che si applica a nodi e grafi mai incontrati durante l’addestramento. È la differenza tra imparare a memoria la mappa di una città e imparare a leggere le mappe: la seconda abilità funziona anche in una città nuova.
Nell’impostazione transduttiva l’addestramento e la predizione avvengono sullo stesso grafo fisso \(G\): tutti i nodi (etichettati e non) sono noti fin dall’inizio, e l’obiettivo è propagare le etichette dai nodi noti a quelli ignoti; è la classificazione di nodo semi-supervisionata. Nell’impostazione induttiva si impara invece una funzione \(f\) che generalizza a nodi o interi grafi mai visti in addestramento: indispensabile quando il grafo evolve nel tempo (un social in cui si iscrivono nuovi utenti) o quando ogni esempio è un grafo distinto (un dataset di molecole). Come vedremo tra poco, i primi metodi di rappresentazione (quelli basati sui cammini casuali) sono intrinsecamente transduttivi, e sarà proprio questo limite a spingere verso le reti neurali su grafo, induttive per costruzione [Ham20].
Un primo assaggio senza reti neurali: camminare a caso sul grafo#
Prima di tirare in ballo le reti neurali vale la pena vedere un’idea più semplice, che per qualche anno è stata il modo migliore che si conoscesse per descrivere i nodi di un grafo.
L’obiettivo è quello di sempre: dare a ogni nodo una fila di qualche decina di numeri, fatta in modo che due nodi vicini nel grafo ricevano due file che si somigliano, numero per numero. Un vettore costruito con questa intenzione (i simili vicini fra loro) ha un nome che il capitolo sul linguaggio ha già usato per le parole: si chiama embedding. Non è un oggetto nuovo, è sempre una fila di numeri: «embedding» dice a che scopo è stata costruita. Lì l’idea era che a ogni parola tocca un punto, e che parole di significato simile finiscono vicine; e «vicine» va preso alla lettera, come su una mappa, solo che le coordinate non sono due ma qualche decina.
E il trucco per ottenerlo su un grafo è sorprendente: si riusa, quasi senza modifiche, la stessa ricetta con cui si imparavano gli embedding delle parole.
Ricorda l’idea degli word embedding: una parola si conosce dalla compagnia che frequenta, cioè dalle parole che le compaiono accanto nelle frasi. Ma un grafo non ha frasi. E allora fabbrichiamocele: partiamo da un nodo e facciamo una passeggiata a caso, saltando ogni volta a un vicino scelto a sorte; annotiamo i nodi che tocchiamo, in ordine. Otteniamo una sequenza («nodo 3, nodo 1, nodo 2, nodo 3, nodo 4…») che possiamo trattare esattamente come una frase, in cui ogni nodo è una «parola».
Ripetiamo migliaia di volte, da tutti i nodi, e ci ritroviamo con un enorme «testo» fatto di passeggiate. A quel punto diamo in pasto queste finte frasi allo stesso algoritmo che imparava gli embedding delle parole: i nodi che capitano spesso vicini nelle passeggiate (cioè quelli ben connessi tra loro) riceveranno vettori simili. È l’idea di DeepWalk. Una variante di poco successiva, node2vec, aggiunge due manopole per decidere che tipo di passeggiata fare: più «esploratrice», che si allontana, oppure più «pigra», che gironzola attorno al punto di partenza; così si può scegliere se catturare comunità larghe o ruoli locali.
DeepWalk [PARS14] genera, da ogni nodo, un certo numero di cammini casuali di lunghezza fissa: da \(v\) si passa a un vicino scelto uniformemente, e si itera. Ogni cammino \((v_1, v_2, \dots, v_\ell)\) è trattato come una «frase» e dato a skip-gram: si massimizza la probabilità dei nodi del contesto (entro una finestra) dato il nodo centrale,
dove \(c\) è la mezza-ampiezza della finestra, \(\theta\) raccoglie gli embedding appresi e \(P_\theta\) è la solita softmax (in pratica approssimata con negative sampling o softmax gerarchica, per non normalizzare su tutti i nodi). node2vec [GL16] rende il cammino distorto (biased): due iperparametri \(p\) e \(q\) controllano la probabilità, a ogni passo, di tornare indietro, restare nei paraggi o allontanarsi. Regolando \(p\) e \(q\) si interpola con continuità tra un’esplorazione «in ampiezza» (di tipo BFS, che tende a cogliere l’equivalenza strutturale, nodi con ruoli simili, per esempio due «hub») e una «in profondità» (di tipo DFS, che esplora regioni più ampie e coglie l’omofilia, nodi della stessa comunità). In entrambi i casi l’embedding di un nodo è appreso come una riga di una tabella, esattamente come per le parole.
Questi metodi funzionano, e restano un ottimo termine di paragone contro cui misurare quelli nuovi. Ma portano scritti in fronte tre limiti, ed è illuminante metterli a fuoco, perché sono esattamente i punti che le reti neurali su grafo verranno a risolvere.
Sono transduttivi: quello che si impara è un elenco, un nodo per riga con accanto la sua fila di numeri, e ogni riga vale per quel nodo e per nessun altro. Arriva un nodo nuovo? Non ha nessuna riga, e bisogna riaddestrare. Non c’è modo di generalizzare a un grafo mai visto.
Ignorano le caratteristiche dei nodi: guardano solo chi è connesso a chi, buttando via la tabella \(\mathbf{X}\). Due nodi con le stesse connessioni ma contenuti diversissimi ricevono file di numeri identiche.
Non condividono niente fra un nodo e l’altro: ogni nodo ha la sua fila di numeri, imparata per conto suo, e non esiste una procedura riusabile che, dati i collegamenti e le caratteristiche, calcoli la rappresentazione di un nodo qualunque. Quel che si impara vale per quel nodo e basta, mentre nelle reti per immagini lo stesso filtro, imparato una volta, si riusa su tutta l’immagine, ed è proprio questa condivisione a renderle potenti.
Verso le reti neurali su grafo#
Tiriamo le somme. Le informazioni sul tavolo sono due: da una parte la struttura del grafo, chi è collegato a chi, cioè la tabella \(\mathbf{A}\); dall’altra le caratteristiche dei nodi, che cosa c’è scritto su ciascuno, cioè la tabella \(\mathbf{X}\). I cammini casuali usano solo la prima. Le reti ordinarie saprebbero usare la seconda, ma inciampano sull’assenza di ordine e sul numero variabile di vicini.
Ci serve dunque un modello che tenga insieme quattro richieste. Che usi collegamenti e caratteristiche insieme. Che sia induttivo, cioè che impari una procedura riusabile invece di una tabella di risultati. Che usi la stessa procedura per ogni nodo, come la convoluzione usa lo stesso filtro su tutti i pixel. E che non si accorga dell’ordine in cui gli elenchiamo i nodi, la proprietà da cui è partito tutto il ragionamento della cena.
L’idea che concilia tutte queste richieste è tanto semplice quanto feconda: far sì che ogni nodo aggiorni la fila di numeri che lo descrive ascoltando i vicini, e ripetere l’operazione a strati, con la stessa procedura ovunque. Ogni nodo, a ogni strato, raccoglie messaggi da chi gli sta intorno e li fonde con ciò che già sa. È il message passing, il meccanismo che dà il nome e la sostanza alle Graph Neural Network, e ha una sezione tutta per sé, la prossima. Prima però resta una cosa da fare, e sono cinque minuti: scrivere per esteso, su un grafo vero e piccolo, le tabelle di cui si è parlato fin qui.
Un esempio numerico: dalla figura alla matrice#
Mettiamo le mani nei numeri, sul grafo di cinque nodi della Fig. 28.2. Conviene dire prima di tutto perché si passa dal disegno alle tabelle, perché non è un vezzo: un grafo con cinque nodi si guarda, un social network con un miliardo di persone no. A un certo punto il disegno smette di esistere e resta solo l’elenco, e allora il grafo bisogna scriverlo. Il modo standard è una tabella quadrata con una riga e una colonna per nodo, in cui ogni casella dice se i due nodi corrispondenti sono collegati. Quello che segue non è un argomento nuovo: è la figura di prima scritta in un altro modo, e costruirla è solo contare vicini e riportare i conti. Chi trova le tabelle ostiche può guardarle di sfuggita e tirare dritto: la sostanza è nelle righe di testo fra l’una e l’altra.
I suoi archi sono: 1–2, 1–3, 2–3, 3–4 e 4–5. È un grafo non diretto e non pesato, quindi la matrice di adiacenza \(\mathbf{A}\) è simmetrica e fatta di soli 0 e 1. Riga per riga, mettiamo un 1 dove due nodi sono collegati:
Il grado di ogni nodo è la somma della sua riga: quante linee ne escono. Contando i vicini: il nodo 1 ne ha 2 (il 2 e il 3), il nodo 2 ne ha 2, il nodo 3 ne ha 3 (l’unico «snodo», evidenziato in figura), il nodo 4 ne ha 2, il nodo 5 ne ha 1 (solo il 4). Quindi i gradi sono \((2, 2, 3, 2, 1)\), e la loro somma vale \(2+2+3+2+1 = 10\): esattamente il doppio dei 5 archi, come dev’essere (ogni arco conta per i due nodi che collega). La matrice dei gradi \(\mathbf{D}\) è diagonale e porta questi valori:
C’è un’ultima mossa che ritroveremo di continuo nella prossima sezione: aggiungere a ogni nodo un arco che lo collega a sé stesso, cioè dichiarare ogni nodo vicino di sé. Un arco fatto così si chiama cappio (self-loop), e serve a far sì che, quando un nodo «ascolta» i vicini, non dimentichi sé stesso. In tabella significa mettere degli 1 sulla diagonale, cioè sommare la tabella che ha 1 lungo la diagonale e 0 in tutte le altre caselle: quella tabella si chiama matrice identità e si indica con \(\mathbf{I}\).
dove \(\tilde{\mathbf{A}}\), la \(\mathbf{A}\) con l’ondina sopra, è l’adiacenza «con i cappi». Ogni nodo guadagna così un vicino in più (sé stesso) e i gradi salgono tutti di uno: da \((2,2,3,2,1)\) a \((3,3,4,3,2)\).
Resta una cosa promessa e non ancora mostrata, ed è la più importante di tutte. Torniamo a \(\mathbf{A}\) e scambiamo i nomi di due nodi: chiamiamo «1» quello che finora chiamavamo «3», e viceversa. Il grafo è lo stesso, gli archi sono gli stessi cinque; ma la tabella diventa
che è un disegno di numeri completamente diverso dal primo. I gradi sono \((3,2,2,2,1)\): gli stessi cinque numeri di prima, in un altro ordine, come dev’essere, perché i nodi non sono cambiati, sono cambiati i loro nomi. Ecco il problema in una tabella: due fogli con numeri diversi, e dietro un unico grafo. Una rete che legga il foglio riga per riga vede due cose diverse; e nessuno le ha detto che non lo sono.
Ricapitoliamo a parole, che è tutto quello che serve portarsi via. La tabella quadrata è il grafo scritto: nella casella dove la riga del nodo 2 incrocia la colonna del nodo 3 c’è un \(1\) se i due sono collegati e uno \(0\) se non lo sono. Il grado di un nodo, cioè quanti vicini ha, non va calcolato: si legge, contando gli \(1\) nella sua riga.
E aggiungere «i cappi» vuol dire mettere un \(1\) anche là dove una riga incrocia la propria colonna, cioè dichiarare ogni nodo vicino di sé stesso: un vicino in più a testa, ed ecco perché i gradi salgono tutti di uno.
L’ultima cosa da portarsi via è quella del riquadro qui sopra: se ai nodi si cambiano i nomi, la tabella cambia da cima a fondo e il grafo no.
Queste tre matrici non sono un esercizio di contabilità: sono i mattoni con cui si costruisce la convoluzione su grafo. Il message passing della prossima sezione, nella sua forma più nota, non usa direttamente \(\tilde{\mathbf{A}}\) ma la sua versione normalizzata simmetricamente
dove \(\tilde{\mathbf{D}}\) è la matrice dei gradi di \(\tilde{\mathbf{A}}\) (quella con i cappi, qui \(\mathrm{diag}(3,3,4,3,2)\)). La normalizzazione serve a evitare che i nodi con tanti vicini dominino la somma dei messaggi, riscalando ogni contributo secondo i gradi delle due estremità dell’arco. I dettagli (perché proprio \(-1/2\) da entrambi i lati, e cosa c’entra il Laplaciano del grafo) sono il cuore della prossima sezione; qui basti aver visto da dove partono: da \(\mathbf{A}\), da \(\mathbf{D}\) e dal gesto elementare di aggiungere \(\mathbf{I}\).
Per chi programma, le tre tabelle sono tre righe di numpy, e i numeri che
stampa sono esattamente quelli scritti sopra. Chi non programma può saltare il
riquadro: non c’è dentro niente che il testo non abbia già detto.
import numpy as np
A = np.array([ # matrice di adiacenza (righe/colonne = nodi 1..5)
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 0],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
])
gradi = A.sum(axis=1) # somma di ogni riga -> [2 2 3 2 1]
D = np.diag(gradi) # matrice dei gradi (diagonale)
A_tilde = A + np.eye(5, dtype=int) # aggiunge i self-loop: A + I
print(gradi) # [2 2 3 2 1]
print(A_tilde.sum(axis=1)) # gradi con i cappi: [3 3 4 3 2]
Da ricordare
Un grafo è fatto di nodi (i puntini) e archi (le linee), che possono avere un verso e un peso. Ogni nodo porta con sé una fila di numeri, le sue caratteristiche, e una fila di numeri si chiama vettore.
Il grado di un nodo è quanti vicini ha. Il grafo si scrive in una tabella quadrata, una riga e una colonna per nodo, con un \(1\) dove due nodi sono collegati: serve perché un grafo grande non si può disegnare.
I grafi mettono in crisi le reti classiche per tre motivi: l’ordine in cui si elencano i nodi non conta (la cena non cambia se riordini l’elenco degli invitati), ogni nodo ha un numero diverso di vicini, e ogni grafo ha un numero diverso di nodi. Griglie di pixel e frasi non hanno nessuno dei tre problemi.
Tre tipi di domanda: su un nodo (questo account è un bot?), su un arco che ancora non c’è (queste due persone diventeranno amiche?), sull’intero grafo (questa molecola è tossica?). E due situazioni: o il grafo è uno solo e fisso, e si tratta di riempire i buchi, oppure si vuole imparare qualcosa che funzioni anche su nodi e grafi mai visti, come imparare a leggere le mappe invece di imparare a memoria una città.
I cammini casuali (DeepWalk, node2vec) fabbricano finte frasi passeggiando a caso sul grafo e le danno in pasto all’algoritmo degli embedding di parole. Funzionano, ma imparano un risultato per ogni nodo invece di una procedura: un nodo nuovo li spiazza, e delle caratteristiche dei nodi non sanno che farsene.
Le GNN nascono per superare questi limiti: usare collegamenti e caratteristiche insieme, con una procedura riusabile e la stessa per tutti i nodi, facendo aggiornare ogni nodo tramite i suoi vicini. Il come è il message passing della prossima sezione.
Da ricordare
Un grafo \(G=(V,E)\) è fatto di nodi e archi (diretti o no, pesati o no). La struttura sta nella matrice di adiacenza \(\mathbf{A}\), le caratteristiche dei nodi nella matrice delle feature \(\mathbf{X} \in \mathbb{R}^{N \times F}\); il grado di un nodo è la somma della sua riga, raccolto nella matrice diagonale dei gradi \(\mathbf{D}\).
I grafi sfidano le reti classiche perché i nodi non hanno ordine (serve invarianza/equivarianza a permutazione: \(f(\mathbf{P}\mathbf{A}\mathbf{P}^\top, \mathbf{P}\mathbf{X})\) vale \(f(\mathbf{A},\mathbf{X})\) oppure \(\mathbf{P} f(\mathbf{A},\mathbf{X})\)), hanno grado variabile e taglia variabile: né la griglia della CNN né la sequenza della RNN vanno bene.
Tre livelli di compito: nodo (classificare gli utenti), arco (link prediction: suggerire un’amicizia o un prodotto), grafo (una proprietà della molecola). E due regimi: transduttivo (grafo fisso) vs induttivo (generalizzare a nodi/grafi nuovi).
I cammini casuali (DeepWalk, node2vec) trattano le passeggiate sul grafo come «frasi» e riusano skip-gram: buoni embedding, ma transduttivi, ciechi alle feature e senza condivisione di parametri.
Le GNN nascono per superare questi limiti: combinare struttura e feature in modo induttivo e con pesi condivisi, facendo aggiornare ogni nodo tramite i suoi vicini. Il come è il message passing della prossima sezione.