Technische Samenvatting: Verdwaald in Tokenisatie: Fundamentele Afwegingen in Graph Tokenisatie voor Transformers

Probleemstelling

Transformers zijn een krachtige architectuur voor graph learning, maar hun toepassing op graph-gestructureerde data vereist een voorafgaande stap: tokenisatie. In tegenstelling tot sequenties of roosters ontbreekt het aan een canoniek continu invoerformaat voor graphs. Bijgevolg moet een graph-naar-token-mapping worden gekozen om te bepalen welke structurele informatie op de invoerlaag aan het model wordt blootgesteld.

Hoewel er diverse tokenisatiestrategieën bestaan (bijvoorbeeld spectrale, random-walk, adjacency), worden deze vaak behandeld als empirische ontwerpkeuzes of voorverwerkingsdetails. Dit artikel stelt dat de keuze van tokenisatie een fundamenteel onderdeel is van de expressiviteit van transformers. Het centrale probleem dat wordt aangepakt, is of verschillende tokenisaties uitwisselbaar zijn of dat ze verschillende rekenregimes induceren, specifiek met betrekking tot de diepte die nodig is om graph-taken op te lossen en het vermogen om structurele informatie te herstellen.

Methodologie

De auteurs formaliseren graph tokenisatie als een integraal onderdeel van het rekenmodel, waarbij ze de expressiviteit van Transformers met eindige diepte ($L$), breedte ($m$) en precisie ($p$) analyseren onder drie primaire tokenisatiefamilies:

1. Adjacency Tokenisatie: Codeert de lokale connectiviteit van elke knoop via zijn adjacency-rij. Het is verliesvrij maar blootlegt slechts lokale structuur.
2. Spectrale (Laplacian) Tokenisatie: Leidt tokens af uit de eigendecompositie van de graph Laplacian ($L = D - A$). Het vangt globale topologische eigenschappen, maar is permutatie-equivariant.
3. Random-Walk Tokenisatie: Codeert terugkeer-kansen van random walks met lengte $1$ tot $t(n)$. Het vangt diffusiepatronen, maar is inherent verliesrijk.

De methodologie combineert complexiteitstheoretische analyse met gecontroleerde experimenten.

• Theoretische Analyse: De auteurs stellen ondergrenzen en onmogelijkheidsresultaten vast door graph-taken te koppelen aan complexiteitsklassen (bijvoorbeeld $TC^0$, $NC^1$, $L$). Ze analyseren hoe specifieke taken (bijvoorbeeld $k$-gesloten-walk detectie, connectiviteit, driehoekentelling, planariteit) zich gedragen onder verschillende tokenisaties, rekening houdend met de beperkingen van eindige diepte en de wiskundige eigenschappen van de token-representaties (bijvoorbeeld conditiegetallen, informatieverlies).
• Empirische Validatie: Experimenten worden uitgevoerd op synthetische taken (validatie van dieptescheidingen) en real-world benchmarks (GraphBench, Open Graph Benchmark, ZINC). De studie evalueert Transformers met volledige en afgeknipte versies van elke tokenisatie, evenals gecombineerde tokenisaties, en vergelijkt de prestaties met DeepSet- en GIN-baselines.

Belangrijkste Bijdragen

1. Formalisering van Tokenisatie als Rekenbeperking

Het artikel formaliseert hoe de inputrepresentatie de expressiviteit van transformers bij eindige diepte beperkt. Het toont aan dat tokenisatie niet slechts een stap in feature engineering is, maar een bepalende factor voor welke structurele afhankelijkheden toegankelijk zijn voor het model.

2. Dieptescheidingen tussen Tokenisaties

De auteurs bewijzen dat dezelfde graph-berekening mogelijk zeer verschillende dieptes vereist, afhankelijk van de tokenisatie:

• Random-Walk versus Adjacency: Het detecteren van een $k$-gesloten-walk is oplosbaar in $O(1)$ diepte met Random-Walk tokenisatie (aangezien statistieken expliciet zijn), maar vereist $\Omega(\log k)$ diepte met Adjacency tokenisatie. Dit wordt bewezen via een reductie van het woordprobleem op de permutatiegroep $S_5$ (een $NC^1$-volledig probleem) naar graph-topologie, wat aantoont dat constant-diepte Transformers ($TC^0$) de sequentiële padtraversie die door Adjacency-tokens wordt vereist, niet kunnen simuleren.
• Adjacency versus Spectraal: Het oplossen van globale graph-connectiviteit vereist $\Omega(\log n)$ diepte met Adjacency tokenisatie, terwijl Spectrale tokenisatie dit in $O(1)$ diepte oplost.

3. Inherente Beperkingen en Verliesrijkheid

• Random-Walk is Bewezen Verliesrijk: Ongeacht de wandellengte kan Random-Walk tokenisatie graph-planariteit niet bepalen. De auteurs construeren planaire en niet-planaire graphs met identieke Random-Walk-verdelingen met behulp van Godsil-McKay (GM) switching, en bewijzen dat geen enkele Transformer-diepte of -breedte het topologische onderscheid kan herstellen.
• Spectrale Afkapping is Broos: Het afkappen van het Laplacian-spectrum (zelfs met één eigenwaarde) kan driehoekentelling onmogelijk maken. De auteurs tonen aan dat het toevoegen van een rand tussen symmetrische knopen slechts één eigenwaarde verandert; als deze eigenwaarde wordt afgekapt, kan de transformer de graphs niet onderscheiden.
• Adjacency Afkapping: Het afkappen van de dimensie van adjacency-tokens (via random projectie) vernietigt het vermogen om taken zoals driehoekentelling op te lossen, zoals bewezen via ondergrenzen voor communicatiecomplexiteit (Set Disjointness).

4. Slecht Geconditioneerdheid van Spectrale Tokenisatie voor Lokale Taken

Hoewel Spectrale tokenisatie globale topologie vastlegt, is het wiskundig slecht geconditioneerd voor lokale taken zoals randvoorspelling. Het artikel leidt een ondergrens af die aantoont dat de normen van de parameters die nodig zijn om een lokale rand te decoderen uit een globaal spectrum, schalen met de maximale graad ($d_{max}$). Dit dwingt een afweging af: of het model lijdt aan Softmax-saturatie (verdwijnende gradiënten) of vereist exploderende gewichten, wat optimalisatie moeilijk maakt.

5. Onmogelijkheid van Conversie bij Beperkte Diepte

Het artikel stelt vast dat het converteren tussen tokenisatiefamilies over het algemeen onmogelijk is bij beperkte diepte.

• Een Transformer kan Adjacency-tokens niet efficiënt converteren naar Random-Walk-statistieken (vereist $\Omega(\log k)$ diepte).
• Een Transformer kan geen volledige Adjacency- of Laplacian-representaties herstellen uit Random-Walk-tokens (vanwege informatieverlies).
• Het converteren tussen globale (Spectrale) en lokale (Adjacency) weergaven leidt tot ernstige rekenkundige knelpunten of optimalisatie-instabiliteit.

Resultaten

Theoretische Bevindingen:

• Dieptescheidingen: Empirische validatie bevestigt dat Spectrale tokenisatie connectiviteitstaken oplost met $L=1$ voor alle graphgroottes, terwijl Adjacency tokenisatie voor grotere graphs ($n \ge 128$) instort tot toevalsprestaties.
• Herstelgrenzen: Wanneer een Transformer wordt getraind om Random-Walk terugkeer-kansen te voorspellen uit Adjacency-tokens, groeit de fout met de wandellengte $k$, in overeenstemming met de $\Omega(\log k)$ diepte-eis.
• Planariteit: Modellen die Random-Walk-tokens gebruiken, slagen er niet in planaire van niet-planaire graphs te onderscheiden, zelfs niet met verhoogde diepte, wat het theoretische onmogelijkheidsresultaat bevestigt.

Empirische Bevindingen:

• Taakafhankelijkheid: Geen enkele tokenisatie domineert.
  • Lokale Taken: Adjacency tokenisatie presteert het beste op taken die worden gedomineerd door expliciete lokale beperkingen (bijvoorbeeld Max Clique, Topologische Ordening).
  • Globale Taken: Spectrale (Laplacian) tokenisatie presteert het beste op taken die afhankelijk zijn van globale geometrie (bijvoorbeeld Tox21 moleculaire eigendomsvoorspelling).
  • Gecombineerde Aanpak: Het combineren van complementaire tokenisaties (Adjacency + Spectraal + Random-Walk) levert vaak de beste prestaties op, waardoor het model verschillende structurele signalen kan benutten.
• Effecten van Afkapping: Afgeknipte tokenisaties degraderen over het algemeen de prestaties, vooral voor taken die exacte structurele herstel vereisen (bijvoorbeeld driehoekentelling), wat de theoretische "broosheid" van afkapping valideert.

Betekenis en Claims

Het artikel claimt dat graph tokenisatie een fundamentele afweging is in plaats van een voorverwerkingsdetail. De keuze van tokenisatie dicteert het "zicht" op de graph dat de transformer ontvangt, waardoor de klasse van structurele afhankelijkheden die het model bij eindige diepte kan uitdrukken, wordt beperkt.

Belangrijke kernpunten die door de auteurs worden benadrukt, zijn:

1. Niet-uitwisselbaarheid: Adjacency, Spectrale en Random-Walk tokenisaties zijn niet uitwisselbaar; ze induceren verschillende diepteregimes en expressiviteitslimieten.
2. Inherente Beperkingen: Specifieke tokenisaties hebben bewezen blinde vlekken (bijvoorbeeld Random-Walk kan planariteit niet zien; Spectraal is slecht geconditioneerd voor lokale randen).
3. Conversiebarrières: Transformers kunnen niet zomaar "leren" om efficiënt tussen deze representaties te converteren als de initiële tokenisatie ongunstig is; de diepte die nodig is om deze kloven te overbruggen, kan prohibitief zijn.
4. Praktische Implicatie: De optimale tokenisatie hangt af van de structurele aard van de downstream-taak. Het combineren van complementaire weergaven is een robuuste strategie om de beperkingen van elke enkele representatie te overwinnen.

De auteurs concluderen dat, hoewel hun analyse zich richt op knoop-niveau tokenisaties, de bevindingen een breder principe suggereren: de inputrepresentatie is een kritieke as van complexiteit in graph learning, en toekomstig werk moet optimalisatie-uitdagingen en rand-niveau tokenisaties verkennen.