Message passing: il cuore delle GNN#
C’è un gioco che tutti conosciamo: il telefono senza fili. Una persona sussurra una frase all’orecchio del vicino, quello la ripete al suo, e così via. Cambiamo le regole. Invece di ascoltare un vicino, ognuno ascolta tutti i propri vicini in una volta sola, riassume ciò che ha sentito e si fa un’idea aggiornata; poi si ricomincia. Dopo un giro, ogni persona sa qualcosa dei suoi amici diretti. Dopo due giri, anche degli amici degli amici. Dopo \(K\) giri, la voce partita da un capo della rete è arrivata a chi sta a \(K\) strette di mano di distanza.
Questo passaparola a giri è, alla lettera, il modo in cui una rete neurale su grafo elabora l’informazione. La sezione «Il mondo come grafo» ha messo il dato in forma di tabelle, e per seguire queste pagine basta ricordare che cosa dicono: chi è collegato a chi e che cosa c’è scritto su ogni nodo. I nomi propri sono quattro: la matrice di adiacenza \(\mathbf{A}\) (chi è collegato a chi), la matrice delle feature dei nodi \(\mathbf{X}\) (le file di numeri dei nodi), la matrice diagonale dei gradi \(\mathbf{D}\) (quanti vicini ha ciascuno) e la versione con i cappi \(\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}\) (la prima, con ogni nodo dichiarato vicino di sé stesso).
L’introduzione al capitolo ha dato un nome al meccanismo: message passing, «scambio di messaggi». Qui lo apriamo: prima nella sua forma generale, poi nella sua incarnazione più usata, la Graph Convolutional Network. Di quella vedremo, in quest’ordine, la formula, i conti che ne escono su un grafo minuscolo, la ragione per cui è fatta così e infine da dove salta fuori.
Un nodo, i suoi vicini, tre mosse#
L’idea si regge su un’operazione sola, ripetuta a ogni giro e uguale per ogni nodo: guarda i vicini, riassumili, aggiornati. La Fig. 31.4 la mostra tutta in un colpo d’occhio.
Fig. 31.4 Un passo di message passing su un nodo \(v\): i messaggi dei vicini (le loro file di numeri) si aggregano in un unico riassunto che non dipende dall’ordine in cui arrivano, poi la mossa di aggiornamento fonde quel riassunto con quello che il nodo sapeva già di sé. In basso: impilando due strati, il pezzo di grafo che un nodo riesce a sentire (il suo campo recettivo) cresce dai vicini diretti ai vicini dei vicini.#
Ogni nodo è una persona con una scheda su cui scrive «chi sono». Sulla scheda non c’è una frase: c’è una fila di numeri, uno per ogni caratteristica, come le tre caselline accanto a ogni nodo nella figura della sezione «Il mondo come grafo» (14 anni, 2 sport, 300 messaggi al giorno). È quella fila di numeri a viaggiare lungo gli archi.
A ogni giro un nodo fa tre cose, sempre nello stesso ordine. Prima ascolta, e ogni amico gli passa un bigliettino con sopra la propria fila di numeri (sono i messaggi). Poi riassume, e siccome i bigliettini sono file di numeri «riassumere» vuol dire fare i conti casella per casella, gli anni con gli anni, gli sport con gli sport. Il riassunto non deve dipendere dall’ordine in cui arrivano i bigliettini, perché tra amici non c’è un «primo» e un «ultimo», e la somma va bene proprio per questo: cambi l’ordine degli addendi e il totale non cambia. Vanno bene anche la media e il massimo, cioè il più grande dei numeri arrivati in quella casella. Infine aggiorna la propria scheda, mettendo insieme il riassunto degli amici e quello che già sapeva di sé.
Fatto questo per tutti i nodi, il giro è finito e se ne può fare un altro. È lo stesso identico meccanismo per ogni persona della rete: nessuno ha una regola speciale. Proprio come nella convoluzione delle immagini, dove lo stesso piccolo filtro scorre su tutti i pixel: solo che qui i «vicini» non sono i quattro pixel accanto, ma gli amici sul grafo, che possono essere due o dieci.
E se la domanda riguarda la comitiva intera invece della singola persona, finiti i giri si mettono insieme le schede di tutti, di nuovo in un modo che non guarda l’ordine.
Il quadro generale è la Message Passing Neural Network (MPNN) di Gilmer e colleghi [GSR+17], che unifica sotto un’unica notazione quasi tutte le GNN. Sia \(\mathbf{h}_v^{(k)}\) il vettore di stato del nodo \(v\) dopo \(k\) giri, con \(\mathbf{h}_v^{(0)} = \mathbf{x}_v\) (la sua feature iniziale). Un passo si scrive in due mosse:
Qui \(\mathcal{N}(v)\) è l’insieme dei vicini di \(v\); \(M_k\) è la funzione messaggio (una rete, che può usare anche la feature dell’arco \(\mathbf{e}_{vu}\)); il simbolo \(\bigoplus\) è l’aggregazione, un’operazione invariante alla permutazione dei vicini (tipicamente \(\sum\), la media o il massimo) che produce il messaggio aggregato \(\mathbf{m}_v^{(k)}\); e \(U_k\) è la funzione di aggiornamento che fonde lo stato precedente con \(\mathbf{m}_v^{(k)}\).
Di che oggetti si parla è il punto su cui la formula si legge o non si legge: sono tutti vettori. Lo stato è \(\mathbf{h}_v^{(k)} \in \mathbb{R}^{d_k}\), il messaggio è \(\mathbf{m}_v^{(k)} \in \mathbb{R}^{d_m}\), e quindi \(M_k \colon \mathbb{R}^{d_{k-1}} \times \mathbb{R}^{d_{k-1}} \times \mathbb{R}^{d_e} \to \mathbb{R}^{d_m}\) e \(U_k \colon \mathbb{R}^{d_{k-1}} \times \mathbb{R}^{d_m} \to \mathbb{R}^{d_k}\). Il \(\bigoplus\) opera componente per componente su un numero variabile di vettori tutti della stessa lunghezza \(d_m\) e ne restituisce uno solo, sempre di lunghezza \(d_m\): è per questo che il grado variabile non rompe le dimensioni. (Attenzione al simbolo: qui \(\bigoplus\) è l’aggregazione, mentre nel resto del libro \(\oplus\) indica la concatenazione, che in questo capitolo si scrive \(\|\).) Dopo \(K\) passi, per un compito sull’intero grafo si applica una funzione di lettura (\(\mathrm{READOUT}\)), anch’essa invariante alla permutazione, \(\hat{y}_G = R\big(\{\, \mathbf{h}_v^{(K)} : v \in V \,\}\big)\).
L’invarianza di \(\bigoplus\) è ciò che garantisce l’equivarianza alla permutazione anticipata nell’introduzione: rinumerare i nodi non cambia i messaggi, perché una somma non ha un primo addendo. Ed è la stessa forma astratta («aggrega dai vicini, poi aggiorna») dello schema \(\mathrm{AGGREGATE}\)/\(\mathrm{UPDATE}\) visto in apertura del capitolo, qui resa esplicita nelle sue tre componenti apprendibili.
Dalla formula alla matrice: la GCN#
Lo schema delle tre mosse è un telaio, non un modello: per avere qualcosa che gira bisogna decidere come si scrive il bigliettino, come si riassumono e come si riscrive la scheda. La scelta più celebre (semplice, veloce, e ancora oggi il primo modello che si prova su un grafo) è la Graph Convolutional Network (GCN), presentata nel 2017 da Thomas Kipf e Max Welling [KW17].
Una parola sul vocabolario, perché da qui in avanti le due si alternano: ogni giro di passaparola è uno strato della rete. Sono la stessa cosa detta dai due lati, dal lato di chi ascolta e dal lato di chi la rete la costruisce.
La regola di propagazione della GCN, da uno strato al successivo, sta in una riga:
Ogni simbolo ha un ruolo preciso, e la riga si può leggere a due profondità.
È la scena dei bigliettini scritta in forma abbreviata, tutta in una riga e per tutti i nodi insieme.
\(\mathbf{H}^{(l)}\) è la pila delle schede al giro \(l\): una riga per nodo e, al giro zero, quello che ogni nodo sa di sé.
La \(\mathbf{A}\) col cappello è la rubrica di chi è collegato a chi, ritoccata in due punti: ogni nodo vi figura anche come vicino di sé stesso (sono i cappi della sezione «Il mondo come grafo»: chi ascolta gli altri non deve dimenticare la propria scheda) e ogni collegamento porta un peso, calcolato in modo che chi ha tanti vicini non copra la voce degli altri. Moltiplicare la pila delle schede per questa rubrica è il giro di raccolta dei bigliettini.
\(\mathbf{W}^{(l)}\) è la ricetta con cui ogni nodo riscrive la propria scheda dopo la raccolta, la stessa per tutti, come il filtro che scorre identico su tutta l’immagine in una rete convoluzionale; ed è qui che stanno i numeri che la rete impara. Infine \(\sigma\) è il solito ritocco finale, una funzione come la ReLU che ci accompagna fin dalle prime reti neurali. Un giro intero di passaparola, per l’intera rete, in una riga.
Resta la coda della formula, quella con l’ondina e gli esponenti: è soltanto il modo compatto di scrivere «i pesi da mettere sui collegamenti», e dice quel che si è appena detto a parole. Adesso quei pesi li vediamo all’opera su un grafo di quattro nodi, e subito dopo si dirà perché sono fatti così.
\(\mathbf{H}^{(l)} \in \mathbb{R}^{N \times d_l}\) raccoglie, riga per riga, gli stati di tutti i nodi allo strato \(l\); si parte da \(\mathbf{H}^{(0)} = \mathbf{X}\), le feature d’ingresso.
\(\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}\) è l’adiacenza con i cappi (self-loop): aggiungere la matrice identità \(\mathbf{I}\) mette ogni nodo tra i propri vicini, così che nell’aggregazione un nodo tenga conto anche di sé stesso e non dimentichi la propria feature.
\(\tilde{\mathbf{D}}\) è la matrice diagonale dei gradi di \(\tilde{\mathbf{A}}\), cioè \(\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}\) (il numero di vicini del nodo \(i\), più uno per il cappio).
\(\hat{\mathbf{A}} = \tilde{\mathbf{D}}^{-1/2}\,\tilde{\mathbf{A}}\,\tilde{\mathbf{D}}^{-1/2}\) è l’adiacenza normalizzata in modo simmetrico: il pezzo che pesa i messaggi.
\(\mathbf{W}^{(l)} \in \mathbb{R}^{d_l \times d_{l+1}}\) è la matrice dei pesi appresi dello strato (la stessa per tutti i nodi, come il filtro di una CNN) e \(\sigma\) una non-linearità (di solito la ReLU). È lei a decidere la larghezza del passo successivo: \(\mathbf{H}^{(l)}\mathbf{W}^{(l)}\) manda \(N \times d_l\) in \(N \times d_{l+1}\).
Letta nodo per nodo, la riga matriciale dice esattamente «aggrega, poi aggiorna»:
dove \(\tilde{d}_v\) è il grado di \(v\) in \(\tilde{\mathbf{A}}\). Il messaggio del vicino \(u\) è la sua feature trasformata da \(\mathbf{W}^{(l)}\); l’aggregazione è una somma pesata, con pesi fissi \(1/\sqrt{\tilde{d}_v\,\tilde{d}_u}\); l’aggiornamento è la non-linearità \(\sigma\). È un caso particolare della MPNN in cui la funzione messaggio è lineare e l’aggregazione è la somma normalizzata.
Il conto, coi numeri#
Vale più di mille formule vedere i conti tornare, e conviene farlo subito, su un grafo piccolissimo: quattro nodi in fila (1–2–3–4), ciascuno con un solo numero sulla scheda invece di una fila, cioè \(\mathbf{X} = (1,\, 2,\, 3,\, 4)^\top\). (La \(\top\) in alto vuol dire solo che quei quattro numeri vanno letti in colonna, uno per nodo, invece che in riga: è una convenzione di scrittura e non cambia niente.)
Delle tre mosse ne teniamo una sola. La ricetta di riscrittura e il ritocco finale li mettiamo a riposo (in formule, \(\mathbf{W} = \mathbf{I}\) e \(\sigma\) uguale all’identità: due modi di dire «per stavolta, lascia le cose come stanno»), così quello che si vede è l’effetto della sola raccolta dei bigliettini.
Ogni collegamento porta un peso, e il peso è tanto più piccolo quanti più vicini hanno i due nodi che collega, contando anche il cappio che ciascuno ha verso sé stesso. Qui i pesi sono tre: \(0{,}500\) sui due cappi dei nodi di bordo, che di vicini ne hanno uno solo; \(0{,}408\) sui due archi che uniscono un nodo di bordo a uno interno; \(0{,}333\) sull’arco fra i due nodi interni e sui loro cappi. Il nuovo valore di un nodo è la somma dei valori dei vicini (e del proprio), ciascuno moltiplicato per il peso del collegamento: da lì in poi è una moltiplicazione e un’addizione.
La matrice di adiacenza e quella con i cappi (\(\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}\)) sono
Sommando le righe di \(\tilde{\mathbf{A}}\) si contano i vicini di ciascun nodo, cappio compreso: sono i gradi \(\tilde{\mathbf{d}} = (2,\, 3,\, 3,\, 2)\), perché i due nodi di bordo hanno un vicino e i due interni ne hanno due, più in tutti e quattro i casi sé stessi. Dunque
dove l’esponente \(-1/2\) vuol dire soltanto «uno diviso la radice quadrata»: \(2^{-1/2} = 1/\sqrt{2} \approx 0{,}707\). Quei quattro numeri, uno per nodo, sono la porzione di peso che ciascuno mette in ogni suo collegamento, e il peso dell’arco è il prodotto delle porzioni delle due estremità: \(0{,}707 \cdot 0{,}707 = 0{,}5\) sul cappio di un nodo di bordo, \(0{,}707 \cdot 0{,}577 \approx 0{,}408\) fra un bordo e un interno, \(0{,}577 \cdot 0{,}577 \approx 0{,}333\) fra due interni. La tabella dei pesi così ottenuta si chiama adiacenza normalizzata, e si scrive \(\hat{\mathbf{A}}\), la \(\mathbf{A}\) col cappello: «normalizzare» vuol dire appunto questo, dividere per rimettere tutti sulla stessa scala, e il perché lo si vede appena finito il conto. In una riga sola: \(\hat{A}_{vu} = \tilde{A}_{vu} / \sqrt{\tilde{d}_v\,\tilde{d}_u}\), cioè \(\hat{A}_{12} = 1/\sqrt{2\cdot 3} = 1/\sqrt{6} \approx 0{,}408\) e \(\hat{A}_{22} = 1/\sqrt{3\cdot 3} = 1/3 \approx 0{,}333\). La matrice completa è
La tabella è simmetrica, e non poteva essere altrimenti: gli archi qui non hanno un verso, quindi se il 2 è vicino dell’1 anche l’1 è vicino del 2, e il peso del collegamento è lo stesso letto nei due sensi. Il passo di propagazione è \(\mathbf{H}' = \hat{\mathbf{A}}\,\mathbf{X}\), cioè per ogni nodo la somma pesata di sé e dei suoi vicini:
Le moltiplicazioni sono fatte con i pesi esatti (\(\tfrac{1}{3}\) e \(\tfrac{1}{\sqrt6}\)) e arrotondate solo alla fine: chi le rifà con i valori tondi della tabella, \(0{,}333\) e \(0{,}408\), trova le ultime cifre diverse (per esempio \(0{,}333 \cdot 3 = 0{,}999\) e non \(1{,}000\)), e non ha sbagliato niente.
Il risultato è \(\mathbf{H}' \approx (1{,}316,\, 2{,}075,\, 3{,}300,\, 3{,}225)^\top\), e racconta bene cosa fa la GCN: i quattro valori si stringono. Partivano da \(1\) e arrivavano a \(4\), tre punti fra il più basso e il più alto; adesso vanno da \(1{,}32\) a \(3{,}30\), due punti scarsi. Il nodo 1, che valeva \(1\), sale a \(1{,}316\) perché è tirato in alto dal vicino 2; il nodo 4, che valeva \(4\), scende a \(3{,}225\) perché è tirato in basso dal 3.
I due nodi di mezzo salgono invece tutti e due, e conviene non nasconderlo, perché smonta una scorciatoia che verrebbe naturale: questa non è la media dei vicini. Se lo fosse, il nodo 3, che vale \(3\) e sta fra un \(2\) e un \(4\), resterebbe a \(3\); invece sale a \(3{,}300\). La ragione è che i pesi di una riga non sommano a uno (in quella del nodo 3 fanno \(1{,}07\)), quindi ogni giro non è una media ma una somma pesata, che può alzare il livello generale. Quello che la GCN garantisce è che, ripetendo, le differenze di partenza si consumino, e non che ciascuno vada verso i suoi vicini a ogni singolo passo. Il livellamento si vedrà succedere, giro dopo giro, su questi stessi quattro numeri.
Perché normalizzare così#
Nel conto appena fatto ogni collegamento portava un suo peso, e i pesi erano tutti più piccoli di uno: qualcosa è stato diviso. Perché? Perché non sommare e basta i bigliettini dei vicini?
Un riassunto fatto sommando e basta, senza dividere niente. Un nodo con dieci amici riceve dieci bigliettini e li somma: un numerone. Un nodo con due amici ottiene un numero piccolo. Dopo qualche giro, i nodi «popolari» hanno valori enormi e quelli isolati valori minuscoli, non perché contino di più, ma solo perché hanno più connessioni. La rete finirebbe per confondere «essere importante» con «avere tanti amici».
La divisione rimette tutti sulla stessa scala: dieci opinioni o due, quello che conta è il tenore e non il numero.
Dividere, però, si può in due modi. Nel primo chi ascolta divide per il numero dei propri amici, e fa la media di quello che ha sentito. Nel secondo il peso di ogni collegamento si spartisce fra le due estremità, un po’ chi parla e un po’ chi ascolta: il messaggio di un amico molto popolare arriva più leggero, perché la sua attenzione è «spalmata» su tanti, come il consiglio di chi conosce mezzo mondo vale un filo meno di quello dell’amico che hai solo tu.
Sulla scala i due modi si equivalgono, quindi la scelta si gioca altrove. La GCN prende il secondo perché quel che passa fra due amici pesa uguale nei due versi, mentre con la media lo stesso collegamento conta di più quando il popolare parla al solitario che nel verso opposto. Sembra eleganza, e invece è la simmetria che tiene in piedi il conto da cui la formula è uscita.
Ci sono due normalizzazioni naturali. Quella per righe, \(\tilde{\mathbf{D}}^{-1}\tilde{\mathbf{A}}\), fa la media dei vicini: ogni riga somma a \(1\), è la matrice di transizione di una passeggiata aleatoria. La GCN usa invece quella simmetrica, \(\hat{\mathbf{A}} = \tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}\), in cui il peso dell’arco \((v,u)\) è \(1/\sqrt{\tilde{d}_v\,\tilde{d}_u}\): si sconta il grado di entrambi gli estremi.
L’argomento che viene spontaneo, e che non regge, è la scala. Le due matrici sono simili,
quindi hanno esattamente lo stesso spettro, contenuto in \([-1,1]\) con il massimo pari a \(1\). Tenere le attivazioni e i gradienti su una scala stabile, strato dopo strato, è il guadagno della normalizzazione in quanto tale rispetto a \(\tilde{\mathbf{A}}\) nuda (che sui nodi ad alto grado amplifica i valori in modo incontrollato): è il collegamento diretto con il problema dei gradienti nelle reti profonde, discusso nella sezione sulla backpropagation, ed è la sola cosa che Kipf e Welling rivendicano quando chiamano renormalization trick il passaggio da \(\mathbf{I}_N + \mathbf{D}^{-1/2}\mathbf{A}\,\mathbf{D}^{-1/2}\), che ha autovalori in \([0,2]\), alla forma \(\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}\) con \(\tilde{\mathbf{D}}\) calcolata su \(\tilde{\mathbf{A}}\), cappi inclusi. Attenzione a non leggerci più di quanto ci sia: scala stabile non vuol dire informazione conservata, perché tutto ciò che non giace lungo l’autovettore dominante svanisce comunque.
Quel che distingue davvero la forma simmetrica è la simmetria stessa: \(\hat{\mathbf{A}}\) è autoaggiunta, quindi ha autovalori reali e una base di autovettori ortonormale, mentre \(\tilde{\mathbf{D}}^{-1}\tilde{\mathbf{A}}\) non è simmetrica e i suoi autovettori non sono ortogonali. È questa proprietà, e non il controllo delle scale, a rendere lecito tutto ciò che segue: decomporre un segnale sui nodi nelle sue «frequenze» con \(\mathbf{U}^\top\), moltiplicarle una per una e ricomporre con \(\mathbf{U}\) presuppone una base ortonormale, e senza di essa la lettura spettrale non sta in piedi.
Ed è anche la ragione per cui quella forma è caduta dal conto invece di essere scelta. Qui sta il secondo punto, l’origine spettrale. La GCN nasce come approssimazione al prim’ordine di una convoluzione definita nel dominio spettrale del grafo: i filtri polinomiali di Čebyšëv di Defferrard, Bresson e Vandergheynst [DBV16]. Troncare quel polinomio al primo grado e legare i due coefficienti che restano lascia \(\mathbf{I}_N + \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\), che il renormalization trick sostituisce con \(\hat{\mathbf{A}}\): è da lì che la normalizzazione simmetrica «cade» dal conto, e non è una scelta arbitraria. Rispetto al modello originale di Scarselli e colleghi [SGT+09], che iterava fino a un punto fisso, la GCN fissa un numero piccolo di strati e si addestra come una qualunque rete profonda.
Da dove viene la formula: le frequenze di un grafo#
Arrivati qui la domanda viene da sé: quella formula da dove esce? Nessuno l’ha inventata a tavolino: è quel che resta di un conto più grande, e conviene raccontare che conto sia. Rifarlo per intero vorrebbe strumenti che qui non servono; ma l’idea si dice a parole in mezza pagina, ed è un buon affare, perché in fondo c’è un premio: spiega da sola il difetto più famoso delle GNN.
Su un’immagine, quanto in fretta le cose cambiano da un punto al punto accanto si chiama frequenza: bassa vuol dire zone di colore che cambiano piano, alta vuol dire dettagli fitti e bordi netti. Un filtro che «sfoca» toglie le alte e tiene le basse.
Su un grafo la stessa parola ha un senso preciso, e basta cambiare che cosa si guarda. Una configurazione di numeri sui nodi è a bassa frequenza se nodi collegati portano valori simili, ad alta frequenza se lungo ogni arco il valore salta: al minimo un valore che non salta lungo nessun arco, se non per quanti vicini ha ciascuno; al massimo una scacchiera, dove ogni vicino ha il segno opposto.
Queste configurazioni, dalla più liscia alla più a scacchiera, hanno un nome proprio: si chiamano gli autovettori del laplaciano del grafo. È un nome da registrare, perché nell’ultima sezione del capitolo torna a fare un mestiere che nessuno si aspetta: dire a ogni nodo dove sta nel grafo, come i Transformer dicono a ogni parola dove sta nella frase.
Da qui si può copiare il mestiere di chi lavora sui suoni e sulle immagini: si scrivono i numeri sui nodi come somma di quelle configurazioni, si decide quanto tenere di ciascuna alzando le une e abbassando le altre, e si rimette tutto insieme. È ciò che i primi lavori sulle reti convoluzionali su grafo hanno fatto, e il computer ci metteva un tempo proibitivo: per scrivere quelle configurazioni bisogna prima calcolarle, e su un grafo grande è un lavoro immane. E c’era un secondo guaio: alzare o abbassare una configurazione tocca in un colpo tutto il grafo, mentre il passaparola vuole sentire soltanto i vicini.
La GCN è quello che resta dopo aver tagliato tutto il superfluo, e il taglio rimedia a tutti e due i guai: niente più calcolo immane, e quel che resta arriva a un salto per volta, come il passaparola. È un filtro che attenua le alte frequenze, cioè che smussa le differenze fra vicini.
Una frase da tenere a mente, questa, perché torna presto con un’aria molto meno amichevole.
Si parte dal laplaciano normalizzato del grafo,
simmetrico e semidefinito positivo, quindi diagonalizzabile con autovettori ortonormali \(\mathbf{U}\) e autovalori reali \(\lambda_i \in [0, 2]\).
Che gli autovalori siano «frequenze» non è un’analogia vaga: si legge dalla forma quadratica del laplaciano normalizzato, che vale
dove la somma percorre ogni arco non diretto una volta sola. È una somma di quadrati di differenze lungo gli archi, e la differenza è fra i valori divisi per la radice del grado: in un autovettore con \(\lambda\) piccolo è \(x_u/\sqrt{d_u}\) a variare poco fra nodi collegati, in uno con \(\lambda\) grande ad alternare. Su un autovettore di norma unitaria questa quantità è l’autovalore stesso, perché coincide con il quoziente di Rayleigh \(R(\mathbf{x}) = \mathbf{x}^\top \mathbf{L} \mathbf{x} / \mathbf{x}^\top \mathbf{x}\): la forma quadratica e il quoziente sono due oggetti distinti, da non confondere, ma su \(\lVert \mathbf{x} \rVert = 1\) dicono la stessa cosa, ed è il quoziente (con il principio di minimax) a caratterizzare gli autovalori come minimi della variazione. Su una griglia regolare gli autovettori del laplaciano sono seni e coseni, e questa costruzione si riduce alla trasformata di Fourier di sempre.
Definita la trasformata come \(\hat{\mathbf{x}} = \mathbf{U}^\top \mathbf{x}\), un filtro è una moltiplicazione punto per punto nello spettro e un ritorno indietro:
che è la rete spettrale di Bruna e colleghi [BZSL14]. Ha due difetti fatali: richiede la diagonalizzazione di \(\mathbf{L}\), cioè \(O(N^3)\), e i filtri appresi non sono localizzati, perché un \(g_\theta(\boldsymbol{\Lambda})\) arbitrario mescola nodi a distanza qualunque.
Entrambi si curano con lo stesso trucco: approssimare \(g_\theta\) con un polinomio di grado \(K\), e in particolare con i polinomi di Čebyšëv [HVG11],
con \(T_k(x) = 2x\,T_{k-1}(x) - T_{k-2}(x)\), \(T_0 = 1\), \(T_1 = x\). Il guadagno è doppio. Primo, poiché \(\mathbf{U} f(\boldsymbol{\Lambda}) \mathbf{U}^\top = f(\mathbf{L})\) per qualunque polinomio \(f\), gli autovettori spariscono dal conto: restano prodotti fra la matrice sparsa \(\mathbf{L}\) e un vettore, uno per grado, cioè \(O(K|E|)\) invece di \(O(N^3)\). Secondo, una potenza \(\mathbf{L}^k\) è non nulla in \((u,v)\) solo se esiste un cammino di lunghezza \(\le k\) fra \(u\) e \(v\): un polinomio di grado \(K\) è quindi automaticamente \(K\)-localizzato, tocca soltanto i vicini entro \(K\) salti. È ChebNet [DBV16], ed è già una GNN: la localizzazione, che nella lettura spaziale era il punto di partenza, qui emerge dal troncamento.
L’ultimo passo è di Kipf e Welling [KW17], e consiste nel rinunciare a quasi tutto. Si pone \(K = 1\) (un solo salto per strato, la profondità la darà lo stack) e si approssima \(\lambda_{\max} \approx 2\), il che manda \(\tilde{\mathbf{L}} = \frac{2}{\lambda_{\max}} \mathbf{L} - \mathbf{I}_N\) in \(-\mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}\). Restano due parametri liberi:
Legandoli con \(\theta = \theta'_0 = -\theta'_1\), per ridurre l’overfitting e i parametri a uno solo per canale, si ottiene
La matrice fra parentesi ha autovalori in \([0, 2]\) e applicarla ripetutamente fa esplodere i valori: da qui il renormalization trick, cioè sostituirla con \(\hat{\mathbf{A}} = \tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}\) dove \(\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}_N\) e \(\tilde{\mathbf{D}}\) è la matrice dei gradi di \(\tilde{\mathbf{A}}\). È la formula della GCN, e il conto rimasto in sospeso è saldato: la normalizzazione simmetrica è quel che resta di una convoluzione spettrale dopo due approssimazioni, e non una scelta di comodo.
I cappi, per inciso, non riscalano soltanto: rendono il grafo non bipartito e staccano il fondo dello spettro da \(-1\) (su una catena di otto nodi il minimo passa da \(-1\) a \(-0{,}30\), su un ciclo di otto da \(-1\) a \(-0{,}33\)), cioè smorzano la componente a frequenza più alta [WSZ+19]. È già il filtro passa-basso che, applicato molte volte, appiattisce i nodi uno sull’altro, ed è comparso mentre credevamo di stare solo mettendo in sicurezza i numeri.
Il premio annunciato arriva adesso.
Riprendi la frase da tenere a mente: la GCN è un filtro che smussa le differenze fra vicini. Ogni giro di bigliettini ne cancella un po’; e se i giri sono tanti? Le differenze finiscono.
Si vede sulla catena di quattro nodi di poco fa, quella che partiva da 1, 2, 3 e 4. Rifacendo il giro più volte, sempre con la ricetta di riscrittura e il ritocco finale a riposo, i quattro valori vanno così:
dopo |
nodo 1 |
nodo 2 |
nodo 3 |
nodo 4 |
|---|---|---|---|---|
\(0\) giri |
\(1{,}00\) |
\(2{,}00\) |
\(3{,}00\) |
\(4{,}00\) |
\(1\) giro |
\(1{,}32\) |
\(2{,}07\) |
\(3{,}30\) |
\(3{,}22\) |
\(5\) giri |
\(1{,}95\) |
\(2{,}57\) |
\(2{,}88\) |
\(2{,}50\) |
\(20\) giri |
\(2{,}22\) |
\(2{,}72\) |
\(2{,}73\) |
\(2{,}23\) |
Guarda l’ultima riga. Il nodo che partiva da \(1\) e quello che partiva da \(4\) sono finiti praticamente sullo stesso numero, e così i due di mezzo. Delle differenze di partenza non è rimasto niente, e i due valori diversi che si vedono ancora (\(2{,}2\) e \(2{,}7\)) non dicono chi era il nodo: dicono soltanto quanti vicini ha, uno i due di bordo e due i due interni.
Il perché si vede a occhio. Se a ogni giro ognuno si rimescola con i vicini, e i vicini fanno lo stesso con i loro, dopo un po’ nessuno ha più niente di suo: è la classe in cui tutti copiano un po’ dal compagno di banco, e dopo un’ora i compiti si somigliano tutti e non si capisce più chi la lezione la sapeva davvero. Due classi in aule separate si livellano però ciascuna per conto suo: la copiatura non passa i muri, e i due gruppi restano diversi. E la ricetta di riscrittura, lasciata a riposo qui, non è una difesa sicura: con numeri grandi tiene in vita qualche differenza, con numeri piccoli il livellamento arriva lo stesso.
Chiamiamo \(\lambda_i(\hat{\mathbf{A}})\) gli autovalori dell’operatore appena ottenuto: stanno in \([-1, 1]\), il più grande vale esattamente \(1\), e il suo autovettore è \(\tilde{\mathbf{D}}^{1/2}\mathbf{1}\), cioè la radice dei gradi. Uno strato GCN (a meno di \(\mathbf{W}\) e della non linearità) è la moltiplicazione per \(\hat{\mathbf{A}}\); \(K\) strati sono \(\hat{\mathbf{A}}^K\). Ma elevare alla \(K\) una matrice eleva alla \(K\) i suoi autovalori, e ogni autovalore di modulo minore di \(1\) svanisce: dopo abbastanza strati sopravvive solo la componente lungo l’autovettore dominante, che è la stessa per tutti i nodi a meno del loro grado. (Vale su un grafo connesso: se le componenti connesse sono più d’una, l’autovalore \(1\) ha la loro molteplicità e il collasso avviene dentro ciascuna componente separatamente. E capita davvero, perché un batch di molecole in PyTorch Geometric è un unico grafo sconnesso, una componente per molecola, e l’oversmoothing non le mescola fra loro.)
Sulla catena di quattro nodi, con \(\mathbf{X} = (1,2,3,4)^\top\), i quattro autovalori di \(\hat{\mathbf{A}}\) valgono \(1\), \(0{,}729\), \(0{,}167\) e \(-0{,}229\). Applicando \(\hat{\mathbf{A}}\) venti volte a \(\mathbf{X}\), il rapporto fra il valore di ogni nodo e la radice del suo grado con cappio vale \(1{,}5714\), \(1{,}5724\), \(1{,}5739\), \(1{,}5748\): i quattro nodi, che partivano da valori distinti, coincidono ormai nelle prime due cifre decimali. Il divario fra il più alto e il più basso è \(3{,}4 \cdot 10^{-3}\) e si stringe come la potenza \(K\)-esima del secondo autovalore, \(0{,}729^K\): a cinquanta applicazioni vale \(2{,}6 \cdot 10^{-7}\) e a cento \(3{,}5 \cdot 10^{-14}\). Anche lì i quattro numeri restano diversi fra loro (in doppia precisione li separano ancora un centinaio e mezzo di passi elementari, il gradino minimo fra due numeri rappresentabili, e quanti esattamente dipende dall’ordine in cui si fanno le moltiplicazioni), ma è una differenza che nessun modello può più usare: al passo successivo della rete, moltiplicata per pesi dell’ordine dell’unità, resta quello che era.
A rigore l’argomento vale per l’operatore lineare \(\hat{\mathbf{A}}^K\), cioè per la GCN privata di \(\mathbf{W}\) e della non linearità. Nella rete completa i pesi possono contrastare il collasso, e Oono e Suzuki [OS20] dimostrano che avviene comunque quando le norme dei pesi restano sotto una soglia legata allo spettro di \(\hat{\mathbf{A}}\): per l’operatore è algebra, per la rete intera è un teorema con le sue condizioni.
Questo appiattimento ha un nome, oversmoothing, cioè «levigatura eccessiva», e l’ultima sezione del capitolo lo elencherà fra i limiti delle GNN. Adesso però sappiamo che è quello che fa, per costruzione, un filtro che smussa le differenze (in gergo un filtro passa-basso) quando lo si applica molte volte di fila. Non c’è nessun errore di programmazione da andare a cercare. C’è da decidere quanti strati mettere, oppure da cambiare filtro.
Il conto sta in poche righe, e stampa insieme i quattro valori giro dopo giro, i quattro autovalori e il divario che si consuma.
import numpy as np
# la catena 1–2–3–4: adiacenza, cappi, gradi
A = np.array([[0., 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]])
A_tilde = A + np.eye(4)
d = A_tilde.sum(1) # gradi col cappio: [2 3 3 2]
A_hat = A_tilde / np.sqrt(np.outer(d, d)) # normalizzazione simmetrica
X = np.array([1., 2., 3., 4.])
for giri in (0, 1, 5, 20):
H = np.linalg.matrix_power(A_hat, giri) @ X
print(f"{giri:>2} giri: " + " ".join(f"{v:.2f}" for v in H))
print("autovalori:", np.round(np.sort(np.linalg.eigvalsh(A_hat))[::-1], 3))
r = (np.linalg.matrix_power(A_hat, 20) @ X) / np.sqrt(d)
print("valore diviso la radice del grado:", np.round(r, 4))
print(f"divario fra il più alto e il più basso: {r.max() - r.min():.1e}")
0 giri: 1.00 2.00 3.00 4.00
1 giri: 1.32 2.07 3.30 3.22
5 giri: 1.95 2.57 2.88 2.50
20 giri: 2.22 2.72 2.73 2.23
autovalori: [ 1. 0.729 0.167 -0.229]
valore diviso la radice del grado: [1.5714 1.5724 1.5739 1.5748]
divario fra il più alto e il più basso: 3.4e-03
Impilare gli strati: il campo recettivo a \(K\) salti#
Come vada a finire se si esagera lo sappiamo già. Resta da dire perché, fino a un certo punto, impilare gli strati conviene, e conviene molto: un solo strato di GCN fa vedere a ogni nodo i suoi vicini diretti, e il bello comincia appunto quando gli strati sono più d’uno.
Nella catena 1–2–3–4 il nodo 1 ha un vicino solo, il nodo 2, e al primo giro parla soltanto con lui. Ma nello stesso giro anche il nodo 2 ha parlato col nodo 3. Così, al secondo giro, quando il nodo 1 riascolta il nodo 2, dentro il nodo 2 c’è già un pezzo di nodo 3. Senza essersi mai «visti» direttamente, l’informazione del nodo 3 è arrivata al nodo 1 in due passi. Al terzo giro arriverebbe anche quella del nodo 4.
È esattamente ciò che succede in una rete convoluzionale, dove impilando i livelli ogni neurone «vede» una porzione via via più grande dell’immagine: il suo campo recettivo cresce con la profondità. Sul grafo vale la stessa legge, contata in salti: con \(K\) strati, ogni nodo raccoglie informazione da tutto ciò che sta entro \(K\) passi da lui. La striscia in basso nella Fig. 31.4 mostra proprio questo salto da uno a due.
Quanti giri servono, allora? Tanti quanti i passi che separano un nodo dall’informazione che gli serve, e di solito sono pochi: se ognuno ha una decina di amici, in due giri se ne sono già sentiti un centinaio.
Impilare \(K\) strati di GCN corrisponde ad applicare \(K\) volte l’operatore di propagazione: lo stato finale \(\mathbf{h}_v^{(K)}\) dipende da tutti i nodi \(u\) per cui esiste un cammino di lunghezza \(\le K\) fino a \(v\) (il campo recettivo a \(K\) salti, l’analogo esatto del campo recettivo che cresce con la profondità nelle CNN). Da qui due indicazioni pratiche. Primo, la profondità va scelta in base a quanti salti di distanza sta l’informazione che serve: due o tre strati bastano quasi sempre, perché il numero di nodi raggiunti cresce in fretta col grado. Secondo, andare troppo profondi è controproducente: applicando molte volte \(\hat{\mathbf{A}}\) le rappresentazioni dei nodi convergono verso un unico punto e diventano indistinguibili; il fenomeno dell’oversmoothing, per cui in pratica le GCN molto profonde rendono peggio di quelle a due strati.
Fig. 31.5 Il campo recettivo che si allarga: al giro \(k=1\) arrivano a \(v\) solo i vicini diretti; al giro \(k=2\) i messaggi partono dai nodi a due salti, passano per i vicini e arrivano anch’essi.#
La Fig. 31.5 rende evidente il punto che rende delicata la profondità: l’informazione lontana non salta, transita. Ogni strato in più la fa passare per un altro nodo, che la mescola con la propria, ed è proprio questa mescolanza ripetuta a produrre, alla lunga, l’oversmoothing.
Addestrare: classificare i nodi con poche etichette#
Con lo schema in mano, addestrare una GCN non richiede niente di nuovo: si misura quanto la rete sbaglia, si calcola in che direzione muovere i pesi per sbagliare meno e ci si muove di un passo. Sono la loss, il gradiente e la backpropagation del capitolo sulle reti neurali. Cambia solo la forma del dato.
Il banco di prova classico è Cora, ed è un grafo di articoli scientifici. I nodi sono circa 2700 articoli e gli archi le citazioni: c’è un arco ogni volta che un articolo ne cita un altro, e in tutto sono circa 5400. Su ogni nodo c’è una fila di 1433 numeri, che dice quali parole compaiono nell’articolo. Il compito è assegnare a ciascun articolo una di 7 categorie tematiche.
La particolarità è che conosciamo l’argomento di pochissimi articoli (nella versione standard di Cora appena 20 per categoria, 140 nodi in tutto su 2700) e vogliamo indovinare quello di tutti gli altri. Come si fa con così poche risposte in mano? Sfruttando i collegamenti: un articolo tende a citare articoli del suo stesso campo. Lungo le citazioni scorrono le parole degli articoli, e dopo due giri ogni articolo porta addosso anche un po’ di quelli che cita; le venti risposte per categoria servono a insegnare alla rete che cosa cercare in quel miscuglio. È come indovinare gli hobby di una comitiva conoscendone solo alcuni: chi frequenta i patiti di scacchi, probabilmente gioca a scacchi anche lui.
Il trucco è che, pur pagando solo gli errori sui 140 articoli di cui sappiamo la risposta, per rispondere su quei 140 la rete ha dovuto far girare l’informazione su tutto il grafo. Aggiustandosi per i 140, quindi, migliora la fila di numeri di tutti: anche quella degli altri articoli, più di duemilacinquecento, su cui non le abbiamo mai detto se aveva ragione. Un apprendimento che parte da poche risposte e tanta struttura si chiama semi-supervisionato.
Formalmente è node classification semi-supervisionata in regime transduttivo: il grafo intero, feature comprese, è visibile in addestramento, ma solo un piccolo insieme \(\mathcal{V}_{\text{train}}\) di nodi è etichettato. Una GCN a due strati produce i logit per tutti i nodi,
e la loss è la cross-entropia calcolata sui soli nodi etichettati:
dove \(y_{vc}\) è l’etichetta one-hot del nodo \(v\) per la classe \(c\) e \(C\) il numero di classi. Il punto sottile è che \(\mathbf{z}_v\) dipende, tramite \(\hat{\mathbf{A}}\), dalle feature dell’intero vicinato a due salti: il gradiente di \(\mathcal{L}\) fluisce quindi indietro anche attraverso nodi non etichettati, che partecipano all’addestramento pur senza comparire nella somma. Nel loro articolo Kipf e Welling riportano su Cora l’\(81{,}5\%\) di accuratezza contro il \(75{,}7\%\) del miglior metodo che confrontano: quel salto, ottenuto con appena due strati e \(140\) nodi etichettati, è la ragione per cui la GCN si è imposta.
Uno strato GCN in PyTorch#
Tradurre la regola \(\mathbf{H}^{(l+1)} = \sigma(\hat{\mathbf{A}}\,\mathbf{H}^{(l)}\,\mathbf{W}^{(l)})\) in codice è sorprendentemente breve. Uno strato è una trasformazione lineare seguita dal prodotto con l’adiacenza normalizzata, precalcolata una volta sola:
import torch
import torch.nn as nn
import torch.nn.functional as F
class GCNLayer(nn.Module):
def __init__(self, in_dim, out_dim):
super().__init__()
self.lin = nn.Linear(in_dim, out_dim, bias=False) # la matrice W
def forward(self, H, A_hat):
# H: (N, in_dim) stati dei nodi; A_hat: (N, N) adiacenza normalizzata
return A_hat @ self.lin(H) # Â (H W)
class GCN(nn.Module):
def __init__(self, in_dim, hid, n_classi):
super().__init__()
self.gc1 = GCNLayer(in_dim, hid)
self.gc2 = GCNLayer(hid, n_classi)
def forward(self, H, A_hat):
H = F.relu(self.gc1(H, A_hat)) # primo strato + ReLU
H = self.gc2(H, A_hat) # secondo strato: logit per nodo
return H
L’addestramento è un normale ciclo di discesa del gradiente, con l’unico accorgimento di mascherare la loss sui soli nodi etichettati:
model = GCN(in_dim=1433, hid=16, n_classi=7)
opt = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)
for epoca in range(200):
model.train()
opt.zero_grad()
logit = model(H, A_hat) # tutti i nodi
loss = F.cross_entropy(logit[mask_train], y[mask_train]) # solo etichettati
loss.backward() # backprop su tutto il grafo
opt.step()
In pratica non serve scrivere lo strato a mano: la libreria PyTorch
Geometric offre GCNConv, che aggiunge i cappi e applica la normalizzazione
simmetrica al volo. Al posto della matrice \(\hat{\mathbf{A}}\) intera prende il
grafo in un formato compatto, edge_index, che è la sola lista degli archi (di
forma (2, num_archi)). È l’unica strada praticabile sui grafi grandi, dove
\(\hat{\mathbf{A}}\) per intero non entrerebbe in memoria:
from torch_geometric.nn import GCNConv
conv = GCNConv(in_channels=1433, out_channels=16)
# forward: conv(x, edge_index), con x di forma (N, 1433)
Da qui in avanti le domande diventano: e se i vicini fossero troppi per guardarli tutti? E se alcuni contassero più di altri? Sono le questioni dell’ultima sezione del capitolo, «Oltre la GCN», dove incontreremo il campionamento dei vicini di GraphSAGE e i pesi di attenzione delle Graph Attention Network. Prima però c’è una sezione che allarga il campo in un’altra direzione: che cosa succede quando gli archi non sono tutti uguali e ciascuno porta scritto sopra un verbo.
Da ricordare
Il passaparola (message passing) aggiorna ogni nodo in tre mosse, ripetute a ogni giro: ogni vicino passa un bigliettino con quello che sa, i bigliettini si riassumono in un modo che non guarda l’ordine (somma, media, massimo) e il nodo riscrive la propria scheda unendo il riassunto a quello che già sapeva di sé. È lo schema generale, valido per quasi tutte le reti su grafo [GSR+17].
La GCN [KW17] è la versione più usata: la raccolta dei bigliettini segue la rubrica di chi è collegato a chi, in cui ogni nodo figura anche come vicino di sé stesso per non dimenticare la propria scheda; poi una ricetta di riscrittura uguale per tutti i nodi (sono i numeri che la rete impara) e un ritocco finale non lineare.
I bigliettini si pesano invece di sommarli e basta: chi ha tanti vicini non deve coprire la voce degli altri, e il peso di ogni collegamento si spartisce fra chi parla e chi ascolta, secondo quanti vicini ha ciascuno dei due. Serve anche a tenere i valori sulla stessa scala giro dopo giro.
Anche su un grafo si può parlare di frequenze: bassa se nodi collegati portano valori simili, alta se lungo ogni collegamento il valore salta. Un giro di GCN è un filtro che attenua le alte, cioè smussa le differenze fra vicini; e la sua formula è ciò che resta, dopo aver tagliato il superfluo, dei filtri che si usano sui suoni e sulle immagini [DBV16].
Ogni strato in più allarga l’orecchio di un salto: con due giri arrivano gli amici degli amici, con tre quelli ancora dopo, come in una rete per immagini il campo visivo di un neurone cresce con la profondità. Ma smussando a ogni giro, troppi giri cancellano le differenze e i nodi diventano indistinguibili (è l’oversmoothing, la classe in cui tutti copiano dal compagno di banco finché i compiti si somigliano tutti): è quello che il metodo fa per costruzione, non un errore di programmazione.
L’addestramento tipico è indovinare la categoria di tutti i nodi conoscendola per pochissimi (Cora): si pagano solo gli errori su quei pochi, ma per rispondere la rete ha dovuto far girare l’informazione su tutto il grafo, e così impara a rappresentare bene anche gli altri.
Da ricordare
Il message passing aggiorna ogni nodo in tre mosse ripetute a ogni strato: calcola i messaggi dei vicini, li aggrega con una funzione invariante all’ordine (somma, media, max) e aggiorna lo stato del nodo. È il telaio generale delle MPNN [GSR+17].
La GCN [KW17] è l’istanza più usata: \(\mathbf{H}^{(l+1)} = \sigma(\hat{\mathbf{A}}\,\mathbf{H}^{(l)}\,\mathbf{W}^{(l)})\) con \(\hat{\mathbf{A}} = \tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}\) e \(\tilde{\mathbf{A}} = \mathbf{A}+\mathbf{I}\).
Normalizzare impedisce ai nodi ad alto grado di dominare e tiene gli autovalori in \([-1,1]\), stabilizzando le scale attraverso gli strati: vale però per entrambe le forme, quella per righe e quella simmetrica, che sono matrici simili e hanno lo stesso spettro. La GCN sceglie la simmetrica perché \(\hat{\mathbf{A}}\) è autoaggiunta, quindi ha autovettori ortonormali, ed è questo a rendere lecita la lettura spettrale da cui la formula discende (filtri di Čebyšëv, [DBV16]).
Sul grafo le frequenze hanno un senso preciso: un segnale è a bassa frequenza se nodi collegati portano valori simili, e gli autovalori del laplaciano le misurano. Una convoluzione spettrale costa \(O(N^3)\); troncarla a un polinomio di Čebyšëv di grado \(K\) la rende sparsa e \(K\)-localizzata, e il caso \(K=1\) con \(\lambda_{\max}\approx 2\) è la GCN.
Impilare \(K\) strati dà a ogni nodo un campo recettivo a \(K\) salti, l’esatto analogo della profondità nelle CNN. Ma uno strato GCN è un filtro passa-basso, e applicarlo molte volte lascia sopravvivere solo l’autovettore dominante di \(\hat{\mathbf{A}}\): è l’oversmoothing, e non è un incidente ma una conseguenza algebrica.
L’addestramento tipico è la classificazione dei nodi semi-supervisionata (Cora): cross-entropia sui soli nodi etichettati, ma gradienti che fluiscono su tutto il grafo, con la solita discesa del gradiente.