Riepilogo Tecnico: Persi nella Tokenizzazione: Compromessi Fondamentali nella Tokenizzazione di Grafi per i Transformer

Enunciato del Problema

I Transformer sono emersi come un'architettura potente per l'apprendimento su grafi, tuttavia la loro applicazione ai dati strutturati a grafo richiede un passaggio preliminare: la tokenizzazione. A differenza delle sequenze o delle griglie, i grafi mancano di un formato di input continuo canonico. Di conseguenza, deve essere scelta una mappa grafo-a-token per determinare quali informazioni strutturali sono esposte al modello a livello di input.

Sebbene esistano diverse strategie di tokenizzazione (ad esempio, spettrale, cammino casuale, adiacenza), esse sono spesso trattate come scelte progettuali empiriche o dettagli di pre-elaborazione. Questo lavoro sostiene che la scelta della tokenizzazione è un componente fondamentale dell'espressività dei Transformer. Il problema centrale affrontato è se le diverse tokenizzazioni siano intercambiabili o se inducano regimi computazionali distinti, specificamente riguardo alla profondità necessaria per risolvere compiti su grafi e alla capacità di recuperare informazioni strutturali.

Metodologia

Gli autori formalizzano la tokenizzazione dei grafi come parte integrante del modello computazionale, analizzando l'espressività dei Transformer con profondità finita ($L$), larghezza ($m$) e precisione ($p$) sotto tre famiglie principali di tokenizzazione:

1. Tokenizzazione per Adiacenza: Codifica la connettività locale di ciascun nodo tramite la sua riga di adiacenza. È senza perdita ma espone solo la struttura locale.
2. Tokenizzazione Spettrale (Laplaciana): Deriva i token dalla decomposizione spettrale del Laplaciano del grafo ($L = D - A$). Cattura proprietà topologiche globali ma è equivariante per permutazione.
3. Tokenizzazione per Cammino Casuale: Codifica le probabilità di ritorno di cammini casuali di lunghezza da $1$a$t(n)$. Cattura pattern di diffusione ma è intrinsecamente con perdita.

La metodologia combina analisi di complessità teorica con esperimenti controllati.

• Analisi Teorica: Gli autori stabiliscono limiti inferiori e risultati di impossibilità mappando i compiti sui grafi a classi di complessità (ad esempio, $TC^0$, $NC^1$, $L$). Analizzano come compiti specifici (ad esempio, rilevamento di cammini chiusi di lunghezza $k$, connettività, conteggio di triangoli, planarità) si comportano sotto diverse tokenizzazioni, considerando i vincoli della profondità finita e le proprietà matematiche delle rappresentazioni dei token (ad esempio, numeri di condizione, perdita di informazioni).
• Validazione Empirica: Gli esperimenti sono condotti su compiti sintetici (validando le separazioni di profondità) e su benchmark reali (GraphBench, Open Graph Benchmark, ZINC). Lo studio valuta i Transformer utilizzando versioni complete e troncate di ciascuna tokenizzazione, nonché tokenizzazioni combinate, confrontando le prestazioni con le linee di base DeepSet e GIN.

Contributi Chiave

1. Formalizzazione della Tokenizzazione come Vincolo Computazionale

Il lavoro formalizza come la rappresentazione di input vincoli l'espressività del Transformer a profondità finita. Dimostra che la tokenizzazione non è meramente un passaggio di ingegneria delle caratteristiche, ma un determinante di quali dipendenze strutturali sono accessibili al modello.

2. Separazioni di Profondità tra Tokenizzazioni

Gli autori dimostrano che lo stesso calcolo su grafi può richiedere profondità drasticamente diverse a seconda della tokenizzazione:

• Cammino Casuale vs. Adiacenza: Il rilevamento di un cammino chiuso di lunghezza $k$ è risolvibile in profondità $O(1)$ con la tokenizzazione per Cammino Casuale (poiché le statistiche sono esplicite) ma richiede profondità $\Omega(\log k)$ con la tokenizzazione per Adiacenza. Ciò è dimostrato tramite una riduzione dal problema della parola sul gruppo di permutazione $S_5$ (un problema completo per $NC^1$) alla topologia del grafo, mostrando che i Transformer a profondità costante ($TC^0$) non possono simulare la traversazione sequenziale del percorso richiesta dai token di adiacenza.
• Adiacenza vs. Spettrale: Risolvere la connettività globale del grafo richiede profondità $\Omega(\log n)$ con la tokenizzazione per Adiacenza, mentre la tokenizzazione Spettrale la risolve in profondità $O(1)$.

3. Limitazioni Intrinseche e Perdita di Informazioni

• Il Cammino Casuale è Provabilmente Con Perdita: Indipendentemente dalla lunghezza del cammino, la tokenizzazione per Cammino Casuale non può determinare la planarità del grafo. Gli autori costruiscono grafi planari e non planari con distribuzioni identiche di Cammino Casuale utilizzando lo switching di Godsil-McKay (GM), dimostrando che nessuna profondità o larghezza del Transformer può recuperare la distinzione topologica.
• La Troncatura Spettrale è Fragile: Troncare lo spettro del Laplaciano (anche di un singolo autovalore) può rendere impossibile il conteggio dei triangoli. Gli autori mostrano che aggiungere un arco tra nodi simmetrici cambia solo un autovalore; se questo autovalore viene troncato, il transformer non può distinguere i grafi.
• Troncamento dell'Adiacenza: Troncare la dimensione dei token di adiacenza (tramite proiezione casuale) distrugge la capacità di risolvere compiti come il conteggio dei triangoli, come dimostrato tramite limiti inferiori di complessità di comunicazione (Disgiunzione di Insiemi).

4. Cattivo Condizionamento della Tokenizzazione Spettrale per Compiti Locali

Sebbene la tokenizzazione Spettrale catturi la topologia globale, è matematicamente mal condizionata per compiti locali come la previsione degli archi. Il lavoro deriva un limite inferiore che mostra come le norme dei parametri richieste per decodificare un arco locale da uno spettro globale scalino con il grado massimo ($d_{max}$). Questo impone un compromesso: o il modello soffre di saturazione della Softmax (gradienti che svaniscono) o richiede pesi esplosivi, rendendo l'ottimizzazione difficile.

5. Impossibilità di Conversione a Profondità Limitata

Il lavoro stabilisce che convertire tra famiglie di tokenizzazione è generalmente impossibile a profondità limitata.

• Un Transformer non può convertire efficientemente i token di Adiacenza in statistiche di Cammino Casuale (richiede profondità $\Omega(\log k)$).
• Un Transformer non può recuperare rappresentazioni complete di Adiacenza o Laplaciano dai token di Cammino Casuale (a causa della perdita di informazioni).
• La conversione tra visioni globali (Spettrale) e locali (Adiacenza) comporta colli di bottiglia computazionali gravi o instabilità nell'ottimizzazione.

Risultati

Risultati Teorici:

• Separazioni di Profondità: La validazione empirica conferma che la tokenizzazione Spettrale risolve compiti di connettività con $L=1$ su tutte le dimensioni del grafo, mentre la tokenizzazione per Adiacenza collassa a prestazioni casuali per grafi più grandi ($n \ge 128$).
• Limiti di Recupero: Quando si addestra un Transformer a prevedere le probabilità di ritorno del Cammino Casuale dai token di Adiacenza, l'errore cresce con la lunghezza del cammino $k$, coerentemente con il requisito di profondità $\Omega(\log k)$.
• Planarità: I modelli che utilizzano token di Cammino Casuale non riescono a distinguere grafi planari da non planari, anche con profondità aumentata, confermando il risultato teorico di impossibilità.

Risultati Empirici:

• Dipendenza dal Compito: Nessuna singola tokenizzazione domina.
  • Compiti Locali: La tokenizzazione per Adiacenza performa meglio su compiti governati da vincoli locali espliciti (ad esempio, Massimo Clique, Ordinamento Topologico).
  • Compiti Globali: La tokenizzazione Spettrale (Laplaciana) performa meglio su compiti dipendenti dalla geometria globale (ad esempio, previsione di proprietà molecolari su Tox21).
  • Approccio Combinato: Combinare tokenizzazioni complementari (Adiacenza + Spettrale + Cammino Casuale) spesso produce le migliori prestazioni, permettendo al modello di sfruttare segnali strutturali distinti.
• Effetti della Troncatura: Le tokenizzazioni troncate degradano generalmente le prestazioni, in particolare per compiti che richiedono un recupero strutturale esatto (ad esempio, conteggio dei triangoli), validando la "fragilità" teorica della troncatura.

Significato e Affermazioni

Il lavoro afferma che la tokenizzazione dei grafi è un compromesso fondamentale piuttosto che un dettaglio di pre-elaborazione. La scelta della tokenizzazione detta la "visione" del grafo che il Transformer riceve, vincolando di conseguenza la classe di dipendenze strutturali che il modello può esprimere a profondità finita.

I punti chiave enfatizzati dagli autori includono:

1. Non Intercambiabilità: Le tokenizzazioni per Adiacenza, Spettrale e Cammino Casuale non sono intercambiabili; inducono regimi di profondità distinti e limiti di espressività.
2. Limitazioni Inerenti: Specifiche tokenizzazioni hanno punti ciechi provabili (ad esempio, il Cammino Casuale non può vedere la planarità; lo Spettrale è mal condizionato per gli archi locali).
3. Barriere di Conversione: I Transformer non possono semplicemente "imparare" a convertire efficientemente tra queste rappresentazioni se la tokenizzazione iniziale è svantaggiosa; la profondità richiesta per colmare questi divari può essere proibitiva.
4. Implicazione Pratica: La tokenizzazione ottimale dipende dalla natura strutturale del compito downstream. Combinare visioni complementari è una strategia robusta per superare i limiti di qualsiasi singola rappresentazione.

Gli autori concludono che, sebbene la loro analisi si concentri sulle tokenizzazioni a livello di nodo, i risultati suggeriscono un principio più ampio: la rappresentazione di input è un asse critico di complessità nell'apprendimento su grafi, e il lavoro futuro dovrebbe esplorare le sfide di ottimizzazione e le tokenizzazioni a livello di arco.