Introduzione all’apprendimento automatico su grafi

'Introduzione all'apprendimento su grafi'

In questo post del blog, affrontiamo le basi del machine learning su grafi.

Prima studiamo cosa sono i grafi, perché vengono utilizzati e come rappresentarli al meglio. Poi descriviamo brevemente come le persone imparano sui grafi, dai metodi pre-neurali (esplorando le caratteristiche del grafo allo stesso tempo) a quelli comunemente chiamati Graph Neural Networks. Infine, diamo uno sguardo al mondo dei Transformers per i grafi.

Grafi

Cosa è un grafo?

In essenza, un grafo è una descrizione di elementi collegati da relazioni.

Esempi di grafi includono reti sociali (Twitter, Mastodon, qualsiasi rete di citazioni che collega articoli e autori), molecole, grafi di conoscenza (come diagrammi UML, enciclopedie e qualsiasi sito web con collegamenti ipertestuali tra le sue pagine), frasi espresse come alberi sintattici, qualsiasi mesh 3D e altro ancora! Quindi, non è esagerato dire che i grafi sono ovunque.

• IA per lo sviluppo dei giochi Creazione di un gioco di fattoria in 5 giorni. Parte 2
• Similarità delle immagini con Hugging Face Datasets e Transformers
• Benvenuto PaddlePaddle nell’Hugging Face Hub

Gli elementi di un grafo (o rete) sono chiamati nodi (o vertici), e le loro connessioni sono i suoi archi (o collegamenti). Ad esempio, in una rete sociale, i nodi sono gli utenti e gli archi sono le loro connessioni; in una molecola, i nodi sono gli atomi e gli archi sono i loro legami molecolari.

• Un grafo con nodi o archi tipizzati viene chiamato eterogeneo (ad esempio, le reti di citazioni con elementi che possono essere articoli o autori hanno nodi tipizzati, e i diagrammi XML in cui le relazioni sono tipizzate hanno archi tipizzati). Non può essere rappresentato solamente attraverso la sua topologia, ha bisogno di informazioni aggiuntive. Questo post si concentra sui grafi omogenei.
• Un grafo può anche essere orientato (come una rete di follower, in cui A segue B ma non implica che B segue A) o non orientato (come una molecola, in cui la relazione tra gli atomi avviene in entrambi i sensi). Gli archi possono collegare nodi diversi o un nodo a se stesso (autoarchi), ma non tutti i nodi devono essere collegati.

Se vuoi utilizzare i tuoi dati, devi prima considerare la sua migliore caratterizzazione (omogeneo/eterogeneo, orientato/non orientato, e così via).

Per cosa vengono utilizzati i grafi?

Analizziamo una serie di possibili compiti che possiamo svolgere sui grafi.

A livello di grafo, i principali compiti sono:

• generazione di grafi, utilizzata nella scoperta di farmaci per generare nuove molecole plausibili,
• evoluzione del grafo (dato un grafo, prevedere come si evolverà nel tempo), utilizzata in fisica per prevedere l’evoluzione dei sistemi,
• previsione a livello di grafo (compiti di categorizzazione o regressione dai grafi), come la previsione della tossicità delle molecole.

A livello di nodo, di solito si tratta di una previsione delle proprietà del nodo. Ad esempio, Alphafold utilizza la previsione delle proprietà del nodo per prevedere le coordinate tridimensionali degli atomi dati il grafo complessivo della molecola e quindi prevedere come le molecole si pieghino nello spazio tridimensionale, un problema difficile di biochimica.

A livello di arco, si tratta di una previsione delle proprietà dell’arco o della previsione di un arco mancante. La previsione delle proprietà dell’arco aiuta la previsione degli effetti collaterali dei farmaci a prevedere gli effetti collaterali avversi dati una coppia di farmaci. La previsione di un arco mancante viene utilizzata nei sistemi di raccomandazione per prevedere se due nodi in un grafo sono correlati.

È anche possibile lavorare a livello di sottografo per la rilevazione delle comunità o la previsione delle proprietà del sottografo. Le reti sociali utilizzano la rilevazione delle comunità per determinare come le persone sono connesse. La previsione delle proprietà del sottografo può essere trovata nei sistemi di itinerario (come Google Maps) per prevedere i tempi di arrivo stimati.

Lavorare su questi compiti può essere fatto in due modi.

Quando si vuole prevedere l’evoluzione di un grafo specifico, si lavora in un contesto transduttivo, in cui tutto (addestramento, convalida e test) viene fatto sullo stesso singolo grafo. Se questa è la tua configurazione, fai attenzione! Creare set di dati di addestramento/validazione/test da un singolo grafo non è banale. Tuttavia, gran parte del lavoro viene svolto utilizzando grafi diversi (divisioni separate di addestramento/validazione/test), che viene chiamato un contesto induttivo.

Come rappresentiamo i grafi?

I modi comuni per rappresentare un grafo per elaborarlo e operare su di esso sono:

• come insieme di tutti i suoi archi (eventualmente integrato con l’insieme di tutti i suoi nodi)
• o come matrice di adiacenza tra tutti i suoi nodi. Una matrice di adiacenza è una matrice quadrata (di dimensione nodo * nodo) che indica quali nodi sono direttamente collegati ad altri (dove (A_{ij} = 1) se (n_i) e (n_j) sono collegati, altrimenti 0). Nota: la maggior parte dei grafi non è densamente connessa e quindi ha matrici di adiacenza sparse, il che può rendere i calcoli più complessi.

Tuttavia, anche se queste rappresentazioni sembrano familiari, non lasciarti ingannare!

I grafi sono molto diversi dagli oggetti tipici usati nell’apprendimento automatico perché la loro topologia è più complessa di una semplice “sequenza” (come testo e audio) o di una “griglia ordinata” (come immagini e video): anche se possono essere rappresentati come liste o matrici, la loro rappresentazione non dovrebbe essere considerata un oggetto ordinato!

Ma cosa significa? Se hai una frase e mescoli le sue parole, crei una nuova frase. Se hai un’immagine e riorganizzi le sue colonne, crei una nuova immagine.

Questo non è il caso di un grafo: se mescoli l’elenco dei suoi archi o le colonne della sua matrice di adiacenza, è comunque lo stesso grafo. (Spieghiamo questo in modo più formale un po’ più avanti, cerca la invarianza per permutazione).

Rappresentazioni dei grafi attraverso l’Apprendimento Automatico

Il processo solito per lavorare sui grafi con l’apprendimento automatico è prima generare una rappresentazione significativa per gli elementi di interesse (nodi, archi o grafi completi a seconda del tuo compito), quindi utilizzare queste per addestrare un predittore per il tuo compito target. Vogliamo (come in altre modalità) vincolare le rappresentazioni matematiche dei tuoi oggetti in modo che gli oggetti simili siano matematicamente vicini. Tuttavia, questa somiglianza è difficile da definire in modo rigoroso in ML dei grafi: ad esempio, due nodi sono più simili quando hanno le stesse etichette o gli stessi vicini?

Nota: Nelle sezioni seguenti ci concentreremo sulla generazione di rappresentazioni dei nodi. Una volta ottenute le rappresentazioni a livello di nodo, è possibile ottenere informazioni a livello di arco o di grafo. Per informazioni a livello di arco, è possibile concatenare le rappresentazioni delle coppie di nodi o effettuare un prodotto scalare. Per informazioni a livello di grafo, è possibile eseguire un pooling globale (media, somma, ecc.) sul tensore concatenato di tutte le rappresentazioni a livello di nodo. Tuttavia, ciò renderà più uniformi e perderà informazioni sul grafo – un pooling gerarchico ricorsivo può avere più senso, o aggiungere un nodo virtuale, connesso a tutti gli altri nodi nel grafo, e utilizzare la sua rappresentazione come rappresentazione complessiva del grafo.

Approcci pre-neurali

Semplicemente utilizzando caratteristiche progettate

Prima delle reti neurali, i grafi e i loro elementi di interesse potevano essere rappresentati come combinazioni di caratteristiche, in modo specifico per il compito. Ora, queste caratteristiche vengono ancora utilizzate per l’aumento dei dati e l’apprendimento semi-supervisionato, anche se esistono metodi più complessi per la generazione delle caratteristiche; può essere essenziale trovare il modo migliore per fornirle alla tua rete a seconda del tuo compito.

Le caratteristiche a livello di nodo possono fornire informazioni sull’importanza (quanto è importante questo nodo per il grafo?) e/o basate sulla struttura (qual è la forma del grafo intorno al nodo?) e possono essere combinate.

La centralità del nodo misura l’importanza del nodo nel grafo. Può essere calcolata in modo ricorsivo sommando la centralità dei vicini di ciascun nodo fino alla convergenza, o tramite misure della distanza più breve tra i nodi, ad esempio. Il grado del nodo è la quantità di vicini diretti che ha. Il coefficiente di clustering misura quanto sono connessi i vicini del nodo. I vettori di grado dei grafoletti contano quanti grafoletti diversi hanno origine da un dato nodo, dove i grafoletti sono tutti i mini grafi che puoi creare con un certo numero di nodi connessi (con tre nodi connessi, puoi avere una linea con due archi, o un triangolo con tre archi).

Le caratteristiche a livello di arco completano la rappresentazione con informazioni più dettagliate sulla connessione dei nodi, e includono la distanza più breve tra due nodi, i loro vicini comuni e il loro indice di Katz (che è il numero di percorsi possibili fino a una certa lunghezza tra due nodi – può essere calcolato direttamente dalla matrice di adiacenza).

Le caratteristiche a livello di grafo contengono informazioni di alto livello sulla somiglianza e le specificità del grafo. I conteggi totali dei grafoletti, sebbene computazionalmente costosi, forniscono informazioni sulla forma dei sotto-grafi. I metodi del kernel misurano la somiglianza tra i grafi attraverso diversi metodi “bag of nodes” (simili a bag of words).

Approcci basati su passeggiate

Gli approcci basati su passeggiate utilizzano la probabilità di visitare un nodo j da un nodo i in una passeggiata casuale per definire metriche di somiglianza; questi approcci combinano informazioni locali e globali. Node2Vec, ad esempio, simula passeggiate casuali tra i nodi di un grafo, quindi elabora queste passeggiate con un skip-gram, proprio come faremmo con le parole nelle frasi, per calcolare gli embedding. Questi approcci possono anche essere utilizzati per accelerare i calcoli del metodo Page Rank, che assegna un punteggio di importanza a ciascun nodo (sulla base della sua connessione ad altri nodi, valutata come la sua frequenza di visita durante una passeggiata casuale, ad esempio).

Tuttavia, questi metodi hanno dei limiti: non possono ottenere embedding per nuovi nodi, non catturano la similarità strutturale tra nodi in modo fine e non possono utilizzare funzionalità aggiuntive.

Reti Neurali su Grafi

Le reti neurali possono generalizzare a dati invisibili. Date le restrizioni di rappresentazione che abbiamo evocato in precedenza, quale dovrebbe essere una buona rete neurale per lavorare su grafi?

Dovrebbe:

• essere invariante rispetto alla permutazione:
  • Equazione: f ( P ( G ) ) = f ( G ) f(P(G))=f(G) f ( P ( G ) ) = f ( G ) con f la rete, P la funzione di permutazione, G il grafo
  • Spiegazione: la rappresentazione di un grafo e delle sue permutazioni dovrebbe essere la stessa dopo essere passate attraverso la rete
• essere equivariante alla permutazione
  • Equazione: P ( f ( G ) ) = f ( P ( G ) ) P(f(G))=f(P(G)) P ( f ( G ) ) = f ( P ( G ) ) con f la rete, P la funzione di permutazione, G il grafo
  • Spiegazione: permutare i nodi prima di passarli alla rete dovrebbe essere equivalente a permutare le loro rappresentazioni

Le tipiche reti neurali, come le RNN o le CNN, non sono invarianti rispetto alla permutazione. È quindi stata introdotta una nuova architettura, la rete neurale su grafi (Graph Neural Network, GNN) (inizialmente come una macchina basata sullo stato).

Una GNN è composta da livelli successivi. Un livello di GNN rappresenta un nodo come la combinazione ( aggregazione ) delle rappresentazioni dei suoi vicini e di se stesso dal livello precedente ( passaggio del messaggio ), più di solito un’attivazione per aggiungere non linearità.

Confronto con altri modelli : Una CNN può essere vista come una GNN con dimensioni di vicinato fisse (attraverso la finestra scorrevole) e ordinamento (non è equivariante alla permutazione). Un Transformer senza embedding posizionali può essere visto come una GNN su un grafo di input completamente connesso.

Aggregazione e passaggio del messaggio

Esistono molti modi per aggregare i messaggi dai nodi vicini, come sommare, fare la media, ad esempio. Alcuni lavori notevoli che seguono questa idea includono:

• Le Graph Convolutional Networks fanno la media della rappresentazione normalizzata dei vicini di un nodo (la maggior parte delle GNN sono in realtà GCN);
• Le Graph Attention Networks imparano a pesare i diversi vicini in base alla loro importanza (come i transformer);
• Le GraphSAGE campionano vicini a diverse distanze prima di aggregare le loro informazioni in più passaggi con max pooling.
• Le Graph Isomorphism Networks aggregano la rappresentazione applicando un MLP alla somma delle rappresentazioni dei nodi vicini.

Scegliendo un’aggregazione : Alcune tecniche di aggregazione (in particolare media/max pooling) possono incontrare casi di fallimento quando si creano rappresentazioni che differenziano finemente i nodi con vicinato di nodi simili (ad esempio, attraverso il mean pooling, un vicinato con 4 nodi, rappresentato come 1,1,-1,-1, mediato come 0, non sarà diverso da uno con solo 3 nodi rappresentati come -1, 0, 1).

Forma delle GNN e il problema dell’eccessiva smussatura

Ad ogni nuovo livello, la rappresentazione del nodo include sempre più nodi.

Un nodo, attraverso il primo livello, è l’aggregazione dei suoi vicini diretti. Attraverso il secondo livello, è ancora l’aggregazione dei suoi vicini diretti, ma questa volta, le loro rappresentazioni includono i loro stessi vicini (dal primo livello). Dopo n livelli, la rappresentazione di tutti i nodi diventa un’aggregazione di tutti i loro vicini a distanza n, quindi, del grafo completo se il suo diametro è inferiore a n!

Se la tua rete ha troppi livelli, c’è il rischio che ogni nodo diventi un’aggregazione del grafo completo (e che le rappresentazioni dei nodi convergano alla stessa per tutti i nodi). Questo è chiamato il problema dell’eccessiva smussatura

Ciò può essere risolto:

• ridimensionando la GNN in modo che abbia un numero di livelli sufficientemente piccolo da non approssimare ogni nodo come l’intera rete (analizzando prima il diametro e la forma del grafo)
• aumentando la complessità dei livelli
• aggiungendo livelli non di passaggio messaggio per elaborare i messaggi (come semplici MLP)
• aggiungendo collegamenti di salto.

Il problema dell’eccessiva smussatura è un’area di studio importante nell’apprendimento automatico su grafi, poiché impedisce alle GNN di scalare come dimostrato dai Transformers in altre modalità.

Graph Transformers

Un Transformer senza il suo strato di encoding posizionale è invariante alla permutazione e i Transformers sono noti per scalare bene, quindi di recente le persone hanno iniziato a considerare l’adattamento dei Transformers ai grafi (Survey). La maggior parte dei metodi si concentra sulle migliori modalità di rappresentazione dei grafi cercando le migliori caratteristiche e le migliori modalità di rappresentazione delle informazioni posizionali e modificando l’attenzione per adattarla a questi nuovi dati.

Ecco alcuni metodi interessanti che hanno ottenuto risultati di primo piano o vicini su uno dei benchmark più difficili disponibili al momento, il Stanford’s Open Graph Benchmark:

• Graph Transformer per l’apprendimento da grafico a sequenza (Cai e Lam, 2020) ha introdotto un Encoder grafico, che rappresenta i nodi come una concatenazione delle loro embedding e degli embedding posizionali, le relazioni tra i nodi come i percorsi più brevi tra di essi e li combina in un’attenzione self-augmentata con le relazioni.
• Ripensare i Graph Transformer con l’attenzione spettrale (Kreuzer et al, 2021) ha introdotto le Reti di Attenzione Spettrale (SANs). Queste combinano le caratteristiche dei nodi con l’encoding posizionale appreso (calcolato dagli autovettori/valori del Laplaciano) da utilizzare come chiavi e query nell’attenzione, con i valori di attenzione che rappresentano le caratteristiche degli archi.
• GRPE: Codifica Posizionale Relativa per il Graph Transformer (Park et al, 2021) ha introdotto il Graph Relative Positional Encoding Transformer. Rappresenta un grafo combinando un encoding posizionale a livello di grafo con le informazioni del nodo, un encoding posizionale a livello di arco con le informazioni del nodo e li combina nell’attenzione.
• Global Self-Attention come sostituto della convoluzione sui grafi (Hussain et al, 2021) ha introdotto l’Edge Augmented Transformer. Questa architettura incorpora i nodi e gli archi separatamente e li aggrega in un’attenzione modificata.
• I Transformer funzionano davvero male per la rappresentazione dei grafi (Ying et al, 2021) introduce il Graphormer di Microsoft, che ha vinto il primo posto nell’OGB quando è stato presentato. Questa architettura utilizza le caratteristiche dei nodi come query/chiavi/valori nell’attenzione e somma la loro rappresentazione con una combinazione di encoding di centralità, spaziali e degli archi nel meccanismo di attenzione.

L’approccio più recente è Pure Transformers are Powerful Graph Learners (Kim et al, 2022), che ha introdotto TokenGT. Questo metodo rappresenta i grafi di input come una sequenza di embedding di nodi e archi (aumentati con identificatori di nodi ortogonali e identificatori di tipo trainabili), senza embedding posizionale, e fornisce questa sequenza ai Transformers come input. È estremamente semplice, ma intelligente!

Un po’ diverso, Recipe for a General, Powerful, Scalable Graph Transformer (Rampášek et al, 2022) introduce, non un modello, ma un framework chiamato GraphGPS. Consente di combinare facilmente le reti di passaggio dei messaggi con i transformer lineari (a lungo raggio) per creare reti ibride. Questo framework contiene anche diversi strumenti per calcolare encoding posizionali e strutturali (a livello di nodo, grafo, arco), augmentazione delle caratteristiche, random walks, ecc.

L’utilizzo dei transformer per i grafi è ancora un campo molto giovane, ma sembra promettente, poiché potrebbe alleviare diverse limitazioni delle GNN, come la scalabilità a grafi più grandi/più densi o l’aumento delle dimensioni del modello senza eccessiva smussatura.

Se vuoi approfondire, puoi dare un’occhiata a alcuni di questi corsi:

• Formato accademico
  • Machine Learning with Graphs di Stanford
  • Graph Representation Learning di McGill
• Formato video
  • Corso di Geometric Deep Learning
• Libri
  • Graph Representation Learning*, Hamilton
• Sondaggi
  • Graph Neural Networks Study Guide
• Orientamenti di ricerca
  • GraphML in 2023 riassume le possibili direzioni interessanti per GraphML nel 2023.

Belle librerie per lavorare sui grafi sono PyGeometric o Deep Graph Library (per il machine learning sui grafi) e NetworkX (per manipolare i grafi in generale).

Se hai bisogno di benchmark di qualità, puoi dare un’occhiata a:

• OGB, l’Open Graph Benchmark: i dataset di benchmark di riferimento per i grafi, per diverse attività e dimensioni dei dati.
• Benchmarking GNNs: libreria e dataset per valutare le reti di machine learning sui grafi e la loro espressività. L’articolo associato studia in particolare quali dataset sono rilevanti dal punto di vista statistico, quali proprietà del grafo consentono di valutare e quali dataset non dovrebbero più essere utilizzati come benchmark.
• Benchmark di grafi a lungo raggio: benchmark recente (novembre 2022) che esamina le informazioni sui grafi a lungo raggio.
• Tassonomia dei benchmark nel Graph Representation Learning: articolo pubblicato alla conferenza Learning on Graphs 2022, che analizza e classifica i dataset di benchmark esistenti.

Per ulteriori dataset, vedi:

• Paper con il codice Graph tasks Leaderboards: Leaderboard per dataset pubblici e benchmark – attenzione, non tutti i benchmark in questa leaderboard sono ancora rilevanti
• Dataset TU: Raccolta di dataset disponibili pubblicamente, ora ordinati per categorie e caratteristiche. La maggior parte di questi dataset può essere caricata anche con PyG, e alcuni di essi sono stati portati su Datasets
• Dataset SNAP: Stanford Large Network Dataset Collection:
• Dataset MoleculeNet
• Repository di dataset relazionali

Attribuzione delle immagini esterne

Gli emoji nella miniatura provengono da Openmoji (CC-BY-SA 4.0), la figura Graphlets proviene da Biological network comparison using graphlet degree distribution (Pržulj, 2007).