ULTRA Modelli di Fondazione per il Ragionamento del Grafo di Conoscenza

Prendi Bellezza con ULTRA Modelli Fondamentali per il Ragionamento del Grafo di Conoscenza

Cosa c’è di nuovo in Graph ML?

Un modello per governarli tutti

Addestrare un singolo modello generico per risolvere dataset arbitrari è sempre stato un sogno per i ricercatori di ML, specialmente nell’era dei modelli base. Mentre tali sogni sono stati realizzati in campi percettivi come immagini o linguaggi naturali, se possono essere riprodotti in campi di ragionamento (come i grafi) rimane una sfida aperta.

In questo post del blog, dimostriamo che esiste un modello di ragionamento generico, almeno per i grafi di conoscenza (KG). Creiamo ULTRA, un singolo modello di ragionamento pre-addestrato che generalizza a nuovi KG con vocabolari di entità e relazioni arbitrari, che funge da soluzione predefinita per qualsiasi problema di ragionamento KG.

Questo post si basa sul nostro recente paper (preprint) ed è stato scritto insieme a Xinyu Yuan (Mila), Zhaocheng Zhu (Mila) e Bruno Ribeiro (Purdue / Stanford). Segui Michael, Xinyu, Zhaocheng e Bruno su Twitter per ulteriori contenuti su Graph ML.

Sommario

1. Perché l’apprendimento rappresentativo KG è bloccato nel 2018
2. Teoria: Cosa rende un modello induttivo e trasferibile?
3. Teoria: Equivarianza nei grafi multi-relazionali
4. ULTRA: Un modello di base per il ragionamento KG
5. Esperimenti: Il migliore anche nell’inferenza zero-shot, Comportamento di scalabilità
6. Codice, Dati, Checkpoints

Perché l’apprendimento rappresentativo KG è bloccato nel 2018

Il paradigma di pre-addestramento e raffinamento è stato con noi dal 2018, quando ELMo e ULMFit hanno mostrato i primi risultati promettenti e sono stati successivamente consolidati con BERT e GPT.

• Come funziona Nightshade
• Il timestamp in Python Conversione e formattazione essenziali per principianti
• Ottimizzazione degli iperparametri GridSearchCV e RandomizedSearchCV, spiegati

Nell’era dei grandi modelli di linguaggio (LLM) e dei modelli di base (FM) più generali, spesso abbiamo un singolo modello (come GPT-4 o Llama-2) pre-addestrato su enormi quantità di dati e in grado di svolgere una vasta gamma di compiti linguistici in modo zero-shot (o almeno in grado di essere raffinato sul dataset specifico). Oggi, i modelli di base multimodali supportano anche linguaggio, visione, audio e altre modalità, tutto in un unico modello.

Le cose funzionano un po’ diversamente in Graph ML. In particolare, cosa succede con l’apprendimento di rappresentazioni sui KG alla fine del 2023? Le principali attività qui sono a livello di arco:

• Predizione delle entità (o completamento del knowledge graph) (h,r,?): dato un nodo iniziale e una relazione, classificare tutte le entità nel grafo che potrebbero potenzialmente essere le code corrette.
• Predizione delle relazioni (h,?,t): dati due nodi, prevedere il tipo di relazione tra di loro

Ciò che è emerso è che fino ad ora è stato da qualche parte prima del 2018. Il problema chiave è:

Ogni KG ha il suo insieme di entità e relazioni, non esiste un singolo modello preaddestrato che si possa adattare a qualsiasi grafo.

Ad esempio, se osserviamo Freebase (un KG dietro Google Knowledge Graph) e Wikidata (il più grande KG open source), hanno insiemi di entità (86M vs 100M) e relazioni (1500 vs 6000) completamente diversi. C’è qualche speranza che i metodi attuali di apprendimento delle rappresentazioni dei KG possano essere addestrati su un grafo e trasferirsi su un altro?

❌ I metodi transduttivi classici come TransE, ComplEx, RotatE e centinaia di altri metodi basati su embedding apprendono un insieme fisso di entità e tipi di relazione dal grafo di addestramento e non possono nemmeno supportare nuovi nodi aggiunti allo stesso grafo. I metodi poco profondi basati su embedding non si trasferiscono (in realtà, crediamo che non ci sia alcun punto nello sviluppare tali metodi, tranne che per alcuni esercizi di progetto degli studenti).

🟡 I metodi induttivi per le entità come NodePiece e Neural Bellman-Ford Nets non apprendono embedding delle entità. Invece, parametrizzano i nodi di addestramento (visibili) e l’inferenza di nuovi nodi (non visibili) come funzione di relazioni fisse. Poiché apprendono solo gli embedding delle relazioni, ciò consente loro di trasferirsi su grafi con nuovi nodi ma il trasferimento su nuovi grafi con relazioni diverse (come da Freebase a Wikidata) è ancora oltre la portata.

Cosa fare se hai entrambe nuove entità e nuove relazioni al momento dell’inferenza (un grafo completamente nuovo)? Se non si apprendono embedding di entità o relazioni, è teoricamente possibile il trasferimento? Esaminiamo allora la teoria.

Teoria: Cosa rende un modello induttivo e trasferibile?

Definiamo il setup in modo più formale:

• I KG sono grafi diretti e multirelazionali con insiemi arbitrari di nodi e tipi di relazione
• I grafi arrivano senza funzionalità, ovvero non assumiamo l’esistenza di descrizioni testuali (né vettori di caratteristiche precomputati) di entità e relazioni.
• Dato una query (head, relazione, ?), vogliamo classificare tutti i nodi nel grafo sottostante (grafo di inferenza) e massimizzare la probabilità di restituire una vera coda.
• Setup transduttivo: l’insieme di nodi ed entità è lo stesso durante l’addestramento e l’inferenza.
• Setup induttivo (entità): l’insieme di relazioni deve essere fissato durante l’addestramento, ma i nodi possono essere diversi durante l’addestramento e l’inferenza
• Setup induttivo (entità e relazione): sono consentite sia nuove entità non viste che nuove relazioni durante l’inferenza

Cosa imparano le reti neurali per poter generalizzare a nuovi dati? Il riferimento primario – il libro su Geometric Deep Learning di Bronstein, Bruna, Cohen e Veličković – sostiene che si tratta di una questione di simmetrie e invarianze.

Cosa sono le invarianze apprendibili nei modelli di fondazione? LLM vengono addestrati su un vocabolario fisso di token (unità di sotto-word, byte o addirittura vettori inizializzati casualmente come in LLM Lexinvariante), i modelli di visione imparano funzioni per proiettare patch di immagini, i modelli audio imparano a proiettare patch audio.

Cosa sono le invarianze apprendibili per i grafi multi-relazionali?

Prima di tutto, introdurremo le invarianze (equivarianze) nei grafi omogenei standard.

Modelli standard (singoli) per grafi equivarianti alle permutazioni: Un grande passo avanti in ML di grafi è arrivato quando i primi lavori sui GNN (Scarselli et al. 2008, Xu et al. 2018, Morris et al. 2018) hanno dimostrato che i compiti induttivi sui grafi hanno enormemente beneficiato dal presupporre che gli ID dei vertici siano arbitrari, in modo che le previsioni di un modello di grafo non debbano cambiare se assegnassimo diversi ID ai vertici. Questo è noto come equivarianza alle permutazioni dell’ID del nodo della rete neurale. Questa realizzazione ha creato grande entusiasmo e una profusione di nuovi metodi di rappresentazione dei grafi, fintanto che la rete neurale è equivariante alle permutazioni dell’ID del nodo, possiamo chiamarla un modello di grafo.

L’equivarianza alle permutazioni dell’ID del nodo consente ai GNN di trasferire in modo induttivo (zero-shot) i modelli appresi da un grafo di addestramento a un altro grafo di prova (diverso). Questo è una conseguenza dell’equivarianza, poiché la rete neurale non può utilizzare gli ID dei nodi per produrre embedding, deve utilizzare la struttura del grafo. Ciò crea ciò che conosciamo come rappresentazioni strutturali nei grafi (vedi Srinivasan & Ribeiro (ICLR 2020)).

Equivarianza in grafi multi-relazionali

Ora, i bordi nei grafi potrebbero avere diversi tipi di relazione – esiste una teoria GNN per tali grafi?

1️⃣ Nel nostro lavoro precedente, Weisfeiler and Leman Go Relational (con Pablo Barceló, Christopher Morris e Miguel Romero Orth, LoG 2022), abbiamo derivato Relational WL: una gerarchia di espressività WL per grafi multi-relazionali che si concentra maggiormente su compiti a livello di nodo. Il grande lavoro di continuazione di Huang et al (NeurIPS 2023) ha esteso la teoria alla predizione dei collegamenti, formalizzando il passaggio di messaggi condizionale e l’espressività logica utilizzando Relational WL. ✍️ Ricordiamo il passaggio di messaggi condizionale – ne avremo bisogno in seguito – migliora in modo provabile le prestazioni di predizione dei collegamenti.

L’aggiunta proposta di un vettore di aggregazione globale indotto dalla direzione dei bordi entranti/uscenti assomiglia al recente lavoro di Emanuele Rossi et al sulla studio della direzionalità nei MPNN omogenei (leggi l’articolo sul blog su VoAGI per ulteriori dettagli). Tuttavia, questi lavori non prevedono il caso in cui anche le relazioni durante il test siano inedite.

2️⃣ Modelli di grafi equivarianti alla doppia permutazione (multi-relazionali): Recentemente, Gao et al. 2023 hanno proposto il concetto di equivarianza doppia per grafi multi-relazionali. L’equivarianza doppia costringe la rete neurale ad essere equivariante alle permutazioni congiunte di entrambi gli ID dei nodi e degli ID delle relazioni. Ciò garantisce che la rete neurale apprenda i pattern strutturali tra nodi e relazioni, il che le consente di trasferire in modo induttivo (zero-shot) i modelli appresi a un altro grafo con nuovi nodi e nuove relazioni.

➡️ Nel nostro lavoro, troviamo l’invarianza delle interazioni delle relazioni, cioè anche se le identità delle relazioni sono diverse, le loro interazioni fondamentali rimangono le stesse e queste interazioni fondamentali possono essere catturate da un grafo delle relazioni. Nel grafo delle relazioni, ogni nodo è un tipo di relazione dal grafo originale. Due nodi in questo grafo saranno connessi se gli archi con quei tipi di relazione nel grafo originale sono incidenti (cioè condividono un nodo head o un nodo tail). A seconda dell’incidenza, distinguiamo 4 tipi di archi nel grafo delle relazioni:

• Head-to-head (h2h) – due relazioni possono partire dalla stessa entità head;
• Tail-to-head (t2h) – l’entità tail di una relazione può essere una testa di un’altra relazione;
• Head-to-tail (h2t) – l’entità head di una relazione può essere una tail di un’altra relazione;
• Tail-to-tail (t2t) – due relazioni possono avere la stessa entità tail.

Alcune proprietà interessanti del grafo delle relazioni:

• Può essere costruito da qualsiasi grafo multi-relazionale (con semplici moltiplicazioni di matrici sparse)
• Le 4 interazioni fondamentali non cambiano mai perché codificano semplicemente la topologia di base – nei grafi diretti ci saranno sempre nodi head e tail, e le relazioni avranno quei modelli di incidenza

In sostanza, l’apprendimento delle rappresentazioni nel grafo delle relazioni può essere trasferito a qualsiasi grafo multi-relazionale! Questa è l’invarianza apprendibile.

In effetti, può essere dimostrato (stiamo già lavorando sulle prove formali che saranno disponibili in un prossimo lavoro 😉) che la rappresentazione delle relazioni tramite le loro interazioni in un grafo delle relazioni è un modello di doppia equivarianza! Ciò significa che le rappresentazioni di relazioni apprese sono indipendenti dalle identità ma si basano sulle interazioni congiunte tra relazioni, nodi e nodi e relazioni.

ULTRA: Un Modello Fondamentale per il Ragionamento sui KG

Con tutte le fondamenta teoriche che ci supportano, siamo pronti ora per introdurre ULTRA.

ULTRA è un metodo per rappresentazioni grafiche unificate, apprendibili e trasferibili. ULTRA sfrutta le invarianze (ed equivarianze) del grafo delle relazioni con le sue interazioni fondamentali e applica conditional message passing per ottenere rappresentazioni relative di relazioni. Forse il fatto più interessante è che

un singolo modello pre-addestrato di ULTRA può eseguire inferenza senza addestramento su qualsiasi possibile grafo multi-relazionale e può essere perfezionato su qualsiasi grafo target di interesse.

In altre parole, ULTRA è praticamente un modello fondamentale che può eseguire inferenza su qualsiasi input grafico (con già buone prestazioni) e può essere perfezionato su qualsiasi grafo target di interesse.

Il componente cruciale di ULTRA è rappresentato dalle rappresentazioni relative delle relazioni costruite dal grafo delle relazioni. Dato una query (Michael Jackson, genere, ?), iniziamo prima il nodo genere nel grafo delle relazioni con il vettore tutto-uno (tutti gli altri nodi vengono inizializzati con zeri). Eseguendo un GNN, le rappresentazioni dei nodi risultanti del grafo delle relazioni sono condizionate dal nodo genere – ciò significa che ogni relazione inizializzata avrà una propria matrice di caratteristiche relazionali, e questo è molto utile da molti aspetti teorici e pratici.

In pratica, dato un KG di input e una query (h, r, ?) ULTRA esegue le seguenti azioni:

1. Costruzione del grafico delle relazioni;
2. Ottieni le caratteristiche delle relazioni dal GNN di messaggistica condizionale sul grafico delle relazioni (condizionato sulla relazione di query inizializzata r);
3. Utilizza le rappresentazioni relazionali ottenute per il GNN predittore dei link induttivi condizionato sul nodo inizializzato capo h;

Le fasi 2 e 3 sono implementate attraverso modifiche leggermente diverse della rete di Bellman-Ford neurale (NBFNet). ULTRA apprende solo le rappresentazioni delle 4 interazioni fondamentali (h2t, t2t, t2h, h2h) e i pesi del GNN, che sono in totale abbastanza piccoli. Il modello principale con cui abbiamo sperimentato ha solo 177k parametri.

Esperimenti: Migliori anche nella inferenza senza training e nella Fine-tuning

Abbiamo pre-allenato ULTRA su 3 KG standard basati su Freebase, Wikidata e Wordnet, e poi eseguito predizioni di collegamenti a distanza zero su oltre 50 KG di varie dimensioni da 1k a 120k nodi e da 2k a 1,1M archi.

Sulla base dei dataset conosciuti, in media un singolo modello pre-allenato ULTRA è migliore nella modalità di inferenza a distanza zero rispetto ai modelli SOTA esistenti addestrati specificamente su ciascun grafo 🚀Il fine-tuning migliora ulteriormente le prestazioni anche del 10%. È particolarmente sorprendente che un unico modello ULTRA addestrato possa adattarsi a grafi di dimensioni così diverse (differenza di dimensioni dei nodi di 100 volte e delle dimensioni degli archi di 500 volte), mentre si sa che le GNN soffrono di problemi di generalizzazione delle dimensioni (vedi i lavori importanti di Yehudai et al, ICML 2021 e Zhou et al, NeurIPS 2022).

🙃 In effetti, con 57 grafi testati, abbiamo esaurito i KG su cui testare ULTRA. Quindi, se hai un nuovo benchmark nascosto da qualche parte, faccelo sapere!

Comportamento di scaling

Possiamo aumentare ulteriormente le prestazioni zero-shot aggiungendo più grafi alla miscela di pre-training, anche se osserviamo una certa saturazione delle prestazioni dopo il training su 4+ grafi.

La chiesa delle Scaling Laws predice prestazioni ancora migliori con modelli più grandi addestrati su dati di qualità maggiore, quindi è sicuramente nel nostro programma.

Conclusioni: Codice, Dati, Checkpoints

Quindi finalmente abbiamo i modelli di base per il reasoning di KG, abbiamo superato quella soglia del 2018! Un singolo modello ULTRA pre-addestrato può effettuare previsioni di collegamento su qualsiasi KG (grafo multi-relazionale) di qualsiasi dominio. Hai solo bisogno di un grafo con più di 1 tipo di collegamento per iniziare.

📈 Praticamente, ULTRA dimostra già performance molto promettenti su una varietà di benchmark di KG anche in modalità 0-shot, ma è possibile aumentare ulteriormente le prestazioni con un breve fine-tuning.

Metteniamo a disposizione tutto il codice, i dati di addestramento e i checkpoint dei modelli pre-addestrati su GitHub, in modo che tu possa iniziare a eseguire ULTRA sui tuoi dati immediatamente!

📜 Preprint: arxiv

🛠️ Codice, dati: Repo Githtub

🍪 Checkpoints: 2 checkpoint (2 MB ciascuno) nel repo di Github

🌎 Sito web del progetto: qui

Come osservazione finale, il reasoning di KG rappresenta solo una frazione dei molti problemi interessanti nel dominio del reasoning, e la maggior parte ancora non ha una soluzione generica. Crediamo che il successo del reasoning di KG porterà a nuovi progressi in altri domini del reasoning (ad esempio, abbiamo recentemente scoperto che LLM può effettivamente imparare ed utilizzare regole testuali). Rimaniamo ottimisti per il futuro del reasoning!