Apprendimento automatico su grafi @ ICML 2023

Automatic Graph Learning @ ICML 2023

Novità in Graph ML

Avanzamenti recenti e tendenze calde, edizione di agosto 2023

Meravigliose spiagge e paesaggi tropicali delle Hawaii 🌴 non hanno scoraggiato i coraggiosi scienziati dal partecipare alla Conferenza Internazionale sul Machine Learning a Honolulu e presentare i loro recenti lavori! Scopriamo cosa c’è di nuovo nella nostra area preferita del Graph Machine Learning.

Grazie a Santiago Miret per la revisione del post.

Per rendere il post meno noioso riguardo agli articoli, ho scattato alcune foto intorno a Honolulu 📷

Indice dei contenuti (cliccabile):

1. Graph Transformers: più sparsi, più veloci e diretti
2. Teoria: VC dimension dei GNN, approfondimento su over-squashing
3. Nuove architetture GNN: ritardi e half-hops
4. Modelli generativi – Diffusione stabile per le molecole, diffusione discreta
5. Apprendimento geometrico: Geometric WL, Algebra di Clifford
6. Molecole: preallenamento 2D-3D, stima dell’incertezza in MD
7. Materiali e proteine: CLIP per le proteine, Ewald Message Passing, Augmentazioni equivarianti
8. Applicazioni interessanti: Ragionamento algoritmico, Completamento KG induttivo, GNN per spettri di massa
9. La parte conclusiva del meme

Graph Transformers: più sparsi, più veloci e diretti

Abbiamo presentato GraphGPS circa un anno fa ed è piacevole vedere molti articoli ICML che si basano sul nostro framework e ampliano ulteriormente le capacità dei GT.

• Esplorazione del linguaggio di programmazione Julia MongoDB
• Differenziabilità di una Funzione Data il suo Grafico
• Come, in quanto studente, uso ChatGPT per aumentare la mia produttività del 10x

➡️ Exphormer di Shirzad, Velingker, Venkatachalam et al aggiunge un pezzo mancante di attenzione sparsa motivata dal grafo ai GT: invece di BigBird o Performer (originariamente progettati per sequenze), l’attenzione di Exphormer si basa su archi a 1-hop, nodi virtuali (connessi a tutti i nodi in un grafo) e un’idea intelligente di archi expanders. I grafi expanders hanno un grado costante e si è dimostrato che approssimano i grafi completamente connessi. Tutti i componenti combinati, l’attenzione costa O(V+E) invece di O(V²). Ciò consente ad Exphormer di superare GraphGPS quasi ovunque e di scalare verso grafi molto grandi fino a 160k nodi. Ottimo lavoro e tutte le possibilità di fare di Exphormer il meccanismo di attenzione sparsa standard nei GT 👏.

➡️ Contestualmente ai graph transformers, i grafi expanders possono già essere utilizzati per migliorare le prestazioni di qualsiasi architettura MPNN come mostrato in Expander Graph Propagation di Deac, Lackenby e Veličković.

Nello stesso spirito, Cai et al mostrano che gli MPNN con nodi virtuali possono approssimare un’attenzione lineare simile a Performer, in modo che anche i classici GCN e GatedGCN dotati di nodi virtuali mostrino una performance praticamente di SOTA (State-of-the-Art) in compiti di grafi a lunga distanza (abbiamo rilasciato il benchmark LGRB l’anno scorso proprio per misurare le capacità a lunga distanza di GNN e GT).

➡️ Alcuni approcci di sottocampionamento basati su patch per GT ispirati ai modelli di visione: “Una generalizzazione di ViT/MLP-Mixer per i grafi” di He et al suddivide l’input in diverse patch, codifica ogni patch con un GNN in un token e esegue un transformer su quei token.

In GOAT di Kong et al, le caratteristiche dei nodi vengono proiettate in un libro dei codici di K cluster con K-Means, e un vicinato a 3-hop campionato di ciascun nodo partecipa al libro dei codici. GOAT è un modello a 1 livello e si adatta a grafi di milioni di nodi.

➡️ I grafi diretti hanno ricevuto anche un po’ di amore da parte dei transformer 💗. “Transformers Meet Directed Graphs” di Geisler et al introduce il Laplaciano Magnetico – una generalizzazione di un Laplaciano per grafi diretti con una matrice di adiacenza non simmetrica. Gli autovettori del Laplaciano Magnetico abbinati a cammini casuali diretti sono forti caratteristiche di input per il transformer che consentono di impostare un nuovo SOTA sul dataset di previsione delle proprietà dei grafi OGB Code2 con un buon margine!

🏅 Per ultimo, ma non meno importante, abbiamo un nuovo SOTA GT sul dataset standard della comunità ZINC – GRIT di Ma, Lin, et al incorpora la matrice di cammino casuale d-dimensionale completa, chiamata probabilità di cammino casuale relativa (RRWP), come caratteristiche di arco per il calcolo dell’attenzione (a confronto, le caratteristiche RWSE popolari sono solo gli elementi diagonali di questa matrice). Le RRWP sono provabilmente più potenti delle caratteristiche della distanza del percorso più breve e stabiliscono un MAE record di 0,059 su ZINC (rispetto a 0,070 di GraphGPS). GRIT spesso supera GPS anche in altri benchmark 👏. Nello stesso spirito, Eliasof et al propongono un’idea interessante per combinare caratteristiche casuali e spettrali come codifiche posizionali che superano RWSE ma non sono state provate con GT.

Teoria: Dimensione VC delle GNN, approfondimento sull’eccessiva compressione

➡️ La dimensione VC misura la capacità e l’espressività del modello. È ben studiata per gli algoritmi di ML classici, ma sorprendentemente non è mai stata applicata allo studio delle GNN. In “WL meet VC” di Morris et al, finalmente viene scoperta la connessione tra il test WL e la dimensione VC – si scopre che la dimensione VC può essere limitata dalla lunghezza in bit dei pesi delle GNN, cioè i pesi float32 implicherebbero una dimensione VC di 32. Inoltre, la dimensione VC dipende logaritmicamente dal numero di colori WL unici nel compito specifico e polinomialmente dalla profondità e dal numero di strati. Questo è un ottimo risultato teorico e ti incoraggio a darci un’occhiata!

🍊🖐️ L’effetto di eccessiva compressione – perdita di informazioni quando si cerca di inserire messaggi da troppi nodi vicini – è un altro problema comune delle MPNNs, e non comprendiamo completamente come affrontarlo correttamente. Quest’anno, sono stati dedicati 3 articoli a questo argomento. Forse il più fondamentale è il lavoro di Di Giovanni et al che spiega come la larghezza, la profondità e la topologia del grafo delle MPNNs influenzino l’eccessiva compressione.

Risulta che la larghezza potrebbe aiutare (ma con problemi di generalizzazione), la profondità in realtà non aiuta molto, e la topologia del grafo (caratterizzata dal tempo di commutazione tra i nodi) svolge il ruolo più importante. Possiamo ridurre il tempo di commutazione mediante diverse strategie di riconfigurazione del grafo (aggiungendo e rimuovendo archi basati su proprietà spaziali o spettrali), e ce ne sono molte (potresti aver sentito parlare della riconfigurazione basata sul flusso di Ricci che ha vinto il premio Outstanding Paper a ICLR 2022). In effetti, c’è un lavoro successivo a questo studio che va ancora più in profondità e deriva alcune affermazioni di impossibilità riguardo all’eccessiva compressione e alcune proprietà delle MPNNs – ti incoraggio vivamente a leggerlo anche!

➡️ La resistenza effettiva è un esempio di strategie di riconfigurazione spaziale e Black et al lo studiano in dettaglio. La riconfigurazione basata sul flusso di Ricci lavora sulla curvatura del grafo ed è studiata ulteriormente nel lavoro di Nguyen et al.

➡️ Le GNN dei sottografi continuano ad essere al centro dell’attenzione: due lavori (Zhang, Feng, Du, et al e Zhou, Wang, Zhang) derivano contemporaneamente gerarchie di espressività delle GNN dei sottografi recentemente proposte e la loro relazione con i test di WL di ordine 1 e superiore.

Nuove architetture GNN: Ritardi e Mezzi-hop

Se sei stanco di un’altra variazione di GCN o GAT, ecco alcune idee fresche che possono funzionare con qualsiasi GNN a tua scelta:

⏳ Come sappiamo dalla sezione Teoria, la riconfigurazione aiuta a contrastare l’eccessiva compressione. Gutteridge et al introducono “DRew: Dynamically Rewired Message Passing with Delay” che gradualmente densifica il grafo in strati GNN successivi in modo che i nodi a lunga distanza vedano gli stati originali dei nodi precedenti (la versione originale di DRew) oppure vengono aggiunte connessioni saltate in base al ritardo, a seconda della distanza tra due nodi (la versione vDRew). Ad esempio (🖼️👇), nel passaggio di messaggi ritardato vDRew, un nodo di partenza dal livello 0 mostrerà il suo stato ai vicini a 2 hop nel livello 1 e mostrerà il suo stato a un vicino a 3 hop nel livello 2. DRew migliora significativamente la capacità di GNN vanilla di svolgere compiti a lungo raggio – infatti, un GCN abilitato da DRew è il SOTA attuale nell’insieme di dati Peptides-func dal Long Range Graph Benchmark 👀

🦘 Un’altra idea interessante di Azabou et al è rallentare il passaggio dei messaggi inserendo nuovi nodi lenti su ciascun arco con un particolare schema di connettività – solo una connessione in entrata dal nodo di partenza e un arco simmetrico con il nodo di destinazione. I nodi lenti migliorano le prestazioni delle GNN vanilla su benchmark eterofili di gran lunga, ed è anche possibile utilizzare nodi lenti per l’apprendimento auto-supervisionato creando visualizzazioni con diverse posizioni di nodi lenti per lo stesso grafo originale. HalfHop è un componente SSL che non richiede pensieri per migliorare le prestazioni e dovrebbe essere incluso in una suite standard di molte librerie GNN 👍.

Modelli generativi – Diffusione stabile per molecole, Diffusione discreta

➡️ I modelli di diffusione possono funzionare nello spazio delle caratteristiche (ad esempio, lo spazio dei pixel nella generazione di immagini come l’originale DDPM) o nello spazio latente (come Stable Diffusion). Nello spazio delle caratteristiche, è necessario progettare il processo di rumore per rispettare simmetrie ed equivarianze dello spazio delle caratteristiche. Nello spazio latente, è sufficiente aggiungere rumore gaussiano alle caratteristiche prodotte dall’encoder (pre-allenato). La maggior parte dei modelli di generazione di molecole 3D lavora nello spazio delle caratteristiche (come un pionieristico EDM), e il nuovo modello GeoLDM di Xu et al (autori del prominente GeoDiff) è il primo a definire la diffusione latente per la generazione di molecole 3D. Cioè, dopo aver addestrato un autoencoder EGNN, GeoLDM è addestrato sull’obiettivo di denoising in cui il rumore è campionato da una gaussiana standard. GeoLDM porta miglioramenti significativi rispetto a EDM e altre approcci di diffusione non latenti 👏.

➡️ Nel campo dei grafi non geometrici (con solo un’adiacenza e forse caratteristiche di nodi categoriche), la diffusione di grafi discreti, pionieristica da DiGress (ICLR’23), sembra l’opzione più applicabile. Chen et al propongono EDGE, un modello di diffusione discreta guidato dalla distribuzione dei gradi dei nodi. A differenza di DiGress, il grafo target finale in EDGE è un grafo disconnesso senza archi, un modello di rumore in avanti rimuove gli archi attraverso una distribuzione di Bernoulli, e un processo inverso aggiunge archi ai nodi attivi più recenti (attivi sono i nodi i cui gradi sono cambiati nel passaggio precedente). Grazie alla sparsità introdotta dalla guida dei gradi, EDGE può generare grafi piuttosto grandi fino a 4k nodi e 40k archi!

➡️ Infine, “Modelli di diffusione strutturati graficamente” di Weilbach et al colma il divario tra modelli generativi continui e modelli grafici probabilistici che inducono una certa struttura nel problema di interesse, spesso problemi di natura combinatoria. L’idea centrale è codificare la struttura del problema come una maschera di attenzione che rispetta le invarianze di permutazione e utilizzare questa maschera nel calcolo dell’attenzione nell’encoder del Transformer (che per definizione è equivariante alla permutazione dei token di input a meno che non si utilizzino embedding posizionali). GSDM può affrontare la fattorizzazione continua di matrici binarie, circuiti booleani, può generare sudoku e svolgere operazioni di ordinamento. Particolarmente piacevole è un pizzico di ironia con cui l’articolo è scritto 🙃.

<strongApprendimento geometrico: Geometric WL, Algebra di Clifford

L’Apprendimento Profondo Geometrico prospera! Ci sono stati così tanti interessanti articoli presentati che richiederebbero praticamente l’intero post, quindi ne evidenzierò solo alcuni.

➡️ Geometric WL è finalmente arrivato nel lavoro di Joshi, Bodnar, et al. Geometric WL estende la nozione di test WL con caratteristiche geometriche (ad esempio, coordinate o velocità) e deriva l’ordine di espressività fino a GWL di ordine k. I punti chiave sono: 1️⃣ i modelli equivarianti sono più espressivi dei modelli invarianti (con una nota che nei grafi completamente connessi la differenza scompare), 2️⃣ l’ordine tensore delle caratteristiche migliora l’espressività, 3️⃣ l’ordine corpo delle caratteristiche migliora l’espressività (vedi l’immagine 👇). Quindi, sferico > cartesiano > scalari e interazioni di molti corpi > solo distanze. L’articolo presenta anche l’incredibile fonte di apprendimento Geometric GNN Dojo, dove è possibile derivare e implementare la maggior parte dei modelli SOTA dai principi fondamentali!

➡️ Andando oltre i vettori alle algebre di Clifford, Ruhe et al derivano Geometric Clifford Algebra Networks (GCANs). Le algebre di Clifford supportano naturalmente interazioni di ordine superiore tramite bivettori, trivettori e (in generale) multivettori. L’idea principale è il teorema di Cartan-Dieudonné secondo cui ogni trasformazione ortogonale può essere decomposta in riflessioni in iperpiani e le algebre geometriche rappresentano i dati come gli elementi del gruppo Pin(p,q,r). GCANs introducono una nozione di strati lineari, normalizzazioni, non linearità e come possono essere parametrizzati con reti neurali. Gli esperimenti includono la modellazione della dinamica dei fluidi e delle equazioni di Navier-Stokes.

In effetti, c’è già un lavoro successivo che introduce le reti neurali di Clifford equivarianti – puoi saperne di più sulle fondamenta delle algebre di Clifford e sugli articoli più recenti su CliffordLayers supportate da Microsoft Research.

💊 Gli GNN equivarianti (EGNN) sono l’aspirina del DL geometrico che viene applicata a quasi ogni compito ed ha visto un buon numero di miglioramenti. Eijkelboom et al combinano EGNN con reti simpliciali che operano su strutture di ordine superiore (in particolare, complessi simpliciali) in EMPSN. Questo è uno dei primi esempi che combina caratteristiche geometriche e topologiche ed ha un grande potenziale di miglioramento! Infine, Passaro e Zitnick trovano un trucco ingegnoso per ridurre le convoluzioni SO(3) a SO(2), riducendo la complessità da O(L⁶) a O(L³) ma con garanzie di equivalenza matematica 👀. Questa scoperta permette di scalare i modelli geometrici su set di dati più grandi come OpenCatalyst ed è già stata inclusa in Equiformer V2 – presto in molte altre librerie per modelli geometrici 😉

Molecole: pretraining 2D-3D, stima di incertezza in MD

➡️ Liu, Du, et al propongono MoleculeSDE, un nuovo framework per il pretraining congiunto 2D-3D su dati molecolari. Oltre alla perdita di contrasto standard, gli autori aggiungono due componenti generative: la ricostruzione degli input 2D -> 3D e 3D -> 2D mediante la generazione a diffusione basata sui punteggi. Utilizzando i modelli 2D e 3D standard GIN e SchNet, MoleculeSDE viene pre-trainato su PCQM4M v2 e si comporta bene nei compiti di fine-tuning successivi.

➡️ Wollschläger et al conducono uno studio completo sulla stima di incertezza negli GNN per la dinamica molecolare e i campi di forza. Identificando principi chiave informati dalla fisica e focalizzati sull’applicazione, gli autori propongono un Localized Neural Kernel, un’estensione basata su Gaussian Process per qualsiasi GNN geometrico che opera su quantità invarianti ed equivarianti (testato su SchNet, DimeNet e NequIP). In molti casi, le stime di LNK da un modello sono all’altezza o migliori rispetto all’ensemble costoso in cui sarebbe necessario addestrare diversi modelli.

Materiali e Proteine: CLIP per proteine, Ewald Message Passing, Augmentazioni equivarianti

CLIP e i suoi discendenti sono diventati un elemento standard nei modelli di testo-immagine. Possiamo fare lo stesso ma per testo-proteina? Sì!

➡️ Xu, Yuan, et al presentano ProtST, un framework per apprendere rappresentazioni congiunte di descrizioni di proteine testuali (tramite PubMedBERT) e sequenze di proteine (tramite ESM). Oltre a una perdita di contrasto, ProtST ha un obiettivo di predizione di maschere multimodale, ad esempio mascherando il 15% dei token nel testo e nella sequenza di proteine e prevedendo congiuntamente quelli basati su rappresentazioni latenti e perdite di predizione di maschere basate su sequenze o solo linguaggio. Inoltre, gli autori progettano un nuovo dataset ProtDescribe con 550K coppie allineate di sequenze e descrizioni di proteine. ProtST eccelle in molti compiti di modellazione delle proteine nel benchmark PEER, compresa l’annotazione e la localizzazione delle funzioni delle proteine, ma consente anche il recupero di proteine in zero-shot direttamente dalla descrizione testuale (vedi un esempio qui sotto). Sembra che ProtST abbia un futuro brillante nel essere una base per molti modelli generativi di proteine 😉

In realtà, ICML presenta diversi lavori sulla generazione di proteine come GENIE di Lin e AlQuraishi e FrameDiff di Yim, Trippe, De Bortoli, Mathieu, et al — questi non sono ancora condizionati a descrizioni testuali, quindi l’incorporazione di ProtST sembra essere un miglioramento delle prestazioni scontato 📈.

⚛️ MPNN su molecole ha una forte tendenza alla località che inibisce la modellazione delle interazioni a lungo raggio. Kosmala et al derivano Ewald Message Passing e applicano l’idea della somma di Ewald che scompone il potenziale di interazione in termini a corto raggio e a lungo raggio. L’interazione a corto raggio è modellata da qualsiasi GNN mentre l’interazione a lungo raggio è nuova e viene modellata con una trasformata di Fourier 3D e passaggio di messaggi su frequenze di Fourier. Risulta che questo termine a lungo raggio è piuttosto flessibile e può essere applicato a qualsiasi rete che modella sistemi periodici e aperiodici (come cristalli o molecole) come SchNet, DimeNet o GemNet. Il modello è stato valutato su dataset OC20 e OE62. Se sei interessato a ulteriori dettagli, dai un’occhiata alla presentazione di un’ora di Arthur Kosmala al LOG2 Reading Group!

Un’idea simile di utilizzare la somma di Ewald per cristalli 3D è utilizzata in PotNet di Lin et al, dove la connessione a lungo raggio viene modellata con funzioni di Bessel incomplete. PotNet è stato valutato sui dataset del Progetto Materiali e JARVIS — quindi leggendo questi due articoli puoi avere una buona comprensione dei benefici apportati dalla somma di Ewald per molte attività legate ai cristalli 😉

➡️ Un altro approccio per dotare qualsiasi GNN di equivarianza per cristalli e molecole è dato da Duval, Schmidt, et al in FAENet. Un modo standard è incorporare certe simmetrie ed equivarianze direttamente nell’architettura delle GNN (come in EGNN, GemNet e Ewald Message Passing) — questo è un modo sicuro ma computazionalmente costoso (soprattutto quando si tratta di armoniche sferiche e prodotti tensoriali). Un’altra opzione spesso utilizzata in visione — mostrare molte trasformazioni di uno stesso input e il modello dovrebbe alla fine apprendere le stesse invarianze nelle trasformazioni. Gli autori scelgono la seconda strada e progettano un modo rigoroso per campionare trasformazioni invarianti o equivarianti di dati 2D / 3D (ad esempio, per energia o forze, rispettivamente) il tutto con prove sofisticate ✍️. A tal fine, il processo di data augmentation include la proiezione degli input 2D / 3D in una rappresentazione canonica (basata sulla PCA della matrice di covarianza delle distanze) da cui possiamo campionare uniformemente rotazioni.

Il proposto FAENet è un modello semplice che utilizza solo le distanze ma mostra ottime prestazioni con l’augmentation dei frame stocastici, essendo anche 6-20 volte più veloce. Funziona anche per strutture cristalline!

Applicazioni interessanti: Ragionamento Algoritmico, Completamento KG Induttivo, GNN per Spettri di Massa

Alcuni articoli in questa sezione non rientrano nelle categorie sopra menzionate, ma sono comunque degni della tua attenzione.

➡️ “Ragionamento Algoritmico Neurale con Regolarizzazione Causale” di Bevilacqua et al affronta un problema comune nell’apprendimento dei grafi: la generalizzazione OOD a input più grandi durante il test. Studiando la generalizzazione OOD nei problemi di ragionamento algoritmico, gli autori osservano che esistono molti input diversi che effettuano calcoli identici in un certo passaggio. Allo stesso tempo, ciò significa che alcune subset di input non influenzano (o non dovrebbero influenzare) il risultato della previsione. Questa assunzione consente di progettare un obiettivo auto-supervisionato (chiamato Hint-ReLIC) che preferisce un passaggio “significativo” a un gruppo di passaggi che non influenzano il risultato della previsione. Il nuovo obiettivo migliora significativamente le prestazioni su molti task CLRS-30, raggiungendo una micro-F1 superiore al 90%. È interessante chiedersi se potremmo sfruttare lo stesso principio nella propagazione generale dei messaggi e migliorare il trasferimento OOD in altri task di apprendimento dei grafi 🤔

Se sei ancora interessato al ragionamento algoritmico neurale, dai un’occhiata agli atti del workshop Knowledge and Logical Reasoning che contiene ancora più lavori su questo argomento.

➡️ “InGram: Incorporazione di Grafi di Conoscenza Induttivi tramite Grafi di Relazioni” di Lee et al sembra essere uno dei pochi articoli sui grafi di conoscenza a ICML’23 (per quanto ho potuto vedere). InGram è uno dei primi approcci che può generalizzare induttivamente sia alle entità non viste che alle relazioni non viste durante il test. In precedenza, i modelli di grafi di conoscenza induttivi dovevano imparare almeno le incapsulazioni delle relazioni per generalizzare ai nuovi nodi e in questo paradigma, le nuove relazioni non viste sono complesse da modellare. InGram costruisce un grafo di relazioni sopra il grafo multi-relazionale originale, ovvero un grafo di tipi di relazioni, e apprende le rappresentazioni delle relazioni basandosi su questo grafo attraverso l’esecuzione di un GAT. Le rappresentazioni delle entità vengono ottenute dall’inizializzazione casuale e da un codificatore GNN. Avendo sia le rappresentazioni delle entità che delle relazioni, viene applicato un decodificatore DistMult come funzione di punteggio. Vi sono buone probabilità che InGram per le relazioni non viste possa essere altrettanto influente come GraIL (ICML 2020) per le entità non viste 😉.

🌈 “Previsione efficiente di spettri di massa ad alta risoluzione con reti neurali di grafo” di Murphy et al è un’applicazione interessante delle GNN a un vero problema di fisica, la previsione degli spettri di massa. La scoperta principale è che la maggior parte del segnale negli spettri di massa è spiegata da un piccolo numero di componenti (formule di ioni di prodotto e perdite neutre). Ed è possibile estrarre un vocabolario di queste formule dai dati di addestramento. Il problema può quindi essere formulato come classificazione dei grafi (o previsione delle proprietà dei grafi) quando, dato un grafo molecolare, prevediamo token da un vocabolario che corrispondono a determinati valori dello spettro di massa. L’approccio, GRAFF-MS, costruisce la rappresentazione del grafo molecolare attraverso GIN con caratteristiche degli archi, con caratteristiche laplaciane (tramite SignNet) e raggruppate con caratteristiche covariate. Rispetto alla linea di base CFM-ID, GRAFF-MS esegue l’inferenza in circa 19 minuti rispetto a 126 ore raggiungendo prestazioni molto superiori 👀.

La parte conclusiva del meme

Il meme del 2022 si è finalmente converito su Michael Bronstein!