💻 computer science

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers

Cet article démontre que le choix de la tokenisation des graphes dicte fondamentalement l'expressivité et les exigences de profondeur des transformateurs en établissant des compromis théoriques distincts — tels que la perte d'information versus le mauvais conditionnement — entre les représentations spectrales, par marche aléatoire et d'adjacence, tout en prouvant que la conversion entre ces vues incompatibles est souvent impossible pour les modèles à profondeur limitée.

Auteurs originaux : Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford, Amir Globerson, Joan Bruna

Publié 2026-05-22

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford, Amir Globerson, Joan Bruna

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'enseigner à un robot surdoué (un Transformer) comment comprendre une ville. La ville est un graphe : une carte des rues (arêtes) reliant des bâtiments (nœuds).

Le robot ne peut pas regarder une carte directement ; il a besoin que la carte soit traduite dans un langage qu'il comprend : une liste de tokens (comme des mots dans une phrase). Ce processus de traduction s'appelle la Tokenisation.

Cet article soutient que comment vous traduisez la carte est tout aussi important que le cerveau du robot lui-même. Selon la méthode de traduction que vous choisissez, le robot peut résoudre un problème instantanément, ou il peut avoir besoin de réfléchir très longtemps (ajouter de nombreuses couches de profondeur) pour le comprendre. Dans certains cas, peu importe à quel point le robot est intelligent ou profond, il ne peut tout simplement pas résoudre le problème parce que la traduction a jeté des informations cruciales.

Les auteurs ont testé trois manières spécifiques de traduire la carte de la ville :

1. La liste « Rue par Rue » (Tokenisation par adjacence)

L'analogie : Imaginez que vous donnez au robot une liste où, pour chaque bâtiment, vous notez exactement quels autres bâtiments lui sont directement connectés. « Le bâtiment A est connecté à B, C et D. »
La bonne nouvelle : C'est excellent pour les tâches locales. Si vous demandez : « Le bâtiment A est-il connecté au bâtiment B ? », le robot le voit immédiatement. C'est comme regarder un coin de rue ; vous savez exactement qui sont vos voisins.
La mauvaise nouvelle : Si vous demandez : « Toute la ville est-elle connectée ? » (Peut-on marcher du côté Nord au côté Sud sans se perdre ?), le robot doit faire beaucoup de calculs mentaux. Il doit sauter de voisin en voisin, étape par étape, pour tracer un chemin à travers toute la ville. L'article prouve que pour les grandes villes, cette méthode force le robot à être très « profond » (penser à de nombreuses couches) pour résoudre des problèmes globaux.

2. Le « Plan de la ville » (Tokenisation spectrale)

L'analogie : Au lieu de lister les voisins, vous donnez au robot un « plan » mathématique de la forme de la ville. Ce plan décrit la géométrie globale de la ville, comme ses vibrations ou ses fréquences. Il capture la « vue d'ensemble » de la façon dont la ville est assemblée.
La bonne nouvelle : Le robot peut instantanément voir si toute la ville est connectée ou comprendre sa forme globale. C'est comme regarder une photo satellite ; vous voyez toute la disposition d'un seul coup d'œil.
La mauvaise nouvelle : Cette méthode est terrible pour les détails locaux. Si vous demandez : « Y a-t-il une rue spécifique entre le bâtiment A et B ? », le robot lutte. Les mathématiques deviennent désordonnées et instables (mal conditionnées) lorsqu'on essaie de zoomer sur des détails minuscules. C'est comme essayer de lire un seul mot en plissant les yeux sur une photo satellite floue. De plus, si vous coupez une partie du plan pour économiser de l'espace (troncature), vous risquez d'effacer accidentellement la capacité de compter des formes spécifiques, comme des triangles de rues.

3. La « Promenade du Touriste » (Tokenisation par marche aléatoire)

L'analogie : Imaginez un touriste commençant à un bâtiment et se promenant au hasard. Vous donnez au robot un rapport sur la probabilité que le touriste revienne au bâtiment de départ après 1 étape, 2 étapes, 3 étapes, etc.
La bonne nouvelle : C'est incroyable pour repérer les boucles. Si vous demandez : « Peut-on marcher en cercle et revenir au départ ? », le robot voit la réponse immédiatement car le rapport énumère littéralement les probabilités de retour.
La mauvaise nouvelle : Cette méthode est avec perte. Elle jette des informations. L'article prouve que deux agencements de ville complètement différents (l'un pouvant être dessiné sur une carte plate, et l'autre non) peuvent produire le rapport de touriste exactement identique. Peu importe à quel point le robot est intelligent, il ne peut pas faire la différence entre ces deux villes car la traduction a effacé le détail crucial. C'est comme essayer d'identifier une personne uniquement par sa pointure de chaussures ; beaucoup de personnes différentes ont la même pointure.

Les grandes conclusions

1. Vous ne pouvez pas simplement « réparer » une mauvaise traduction
Vous pourriez penser : « Si je donne au robot la liste « Rue par Rue », ne peut-il pas simplement apprendre à la transformer en « Plan de la ville » à l'intérieur de son cerveau ? »
L'article dit non. Si le robot est limité en taille (profondeur), il ne peut pas convertir un style de traduction en un autre. Si vous commencez avec un rapport de « Promenade du Touriste », le robot ne pourra jamais récupérer la carte complète, peu importe combien il réfléchit. L'information est perdue à jamais.

2. Différents travaux nécessitent différentes cartes

Besoin de trouver un voisin spécifique ? Utilisez la liste Rue par Rue.
Besoin de comprendre la forme globale de la ville ? Utilisez le Plan de la ville.
Besoin de trouver des boucles ? Utilisez la Promenade du Touriste.
Essayer d'utiliser une seule carte pour tout rend le robot inefficace ou incapable de résoudre le problème.

3. La « meilleure » solution est un mélange
Dans leurs expériences, les auteurs ont constaté que lorsqu'ils donnaient au robot les trois traductions à la fois, il performait le mieux. Il pouvait utiliser la liste « Rue » pour les détails locaux et le « Plan » pour la forme globale, combinant les forces de chaque point de vue.

Résumé

L'article conclut que la Tokenisation n'est pas juste une première étape ennuyeuse ; c'est une partie fondamentale de l'intelligence du robot. Choisir la mauvaise méthode de traduction crée un « goulot d'étranglement » qu'aucune quantité supplémentaire de puissance de calcul ne peut facilement réparer. Pour construire la meilleure IA d'apprentissage de graphes, vous devez choisir la méthode de traduction qui correspond à la question spécifique que vous posez.

Résumé technique : Perdu dans la tokenisation : Compromis fondamentaux dans la tokenisation de graphes pour les Transformers

Énoncé du problème

Les Transformers sont devenus une architecture puissante pour l'apprentissage sur les graphes, mais leur application aux données structurées en graphes nécessite une étape préliminaire : la tokenisation. Contrairement aux séquences ou aux grilles, les graphes ne possèdent pas de format d'entrée continu canonique. Par conséquent, une carte graphe-vers-jeton doit être choisie pour déterminer quelles informations structurelles sont exposées au modèle au niveau de la couche d'entrée.

Bien que diverses stratégies de tokenisation existent (par exemple, spectrale, marche aléatoire, adjacence), elles sont souvent traitées comme des choix de conception empiriques ou des détails de prétraitement. Cet article postule que le choix de la tokenisation est un composant fondamental de l'expressivité des Transformers. Le problème central abordé est de savoir si différentes tokenisations sont interchangeables ou si elles induisent des régimes de calcul distincts, spécifiquement en ce qui concerne la profondeur requise pour résoudre des tâches sur les graphes et la capacité à récupérer des informations structurelles.

Méthodologie

Les auteurs formalisent la tokenisation de graphes comme une partie intégrante du modèle de calcul, en analysant l'expressivité des Transformers avec une profondeur finie ( $L$ ), une largeur ( $m$ ) et une précision ( $p$ ) sous trois familles principales de tokenisation :

Tokenisation par adjacence : Encode la connectivité locale de chaque nœud via sa ligne d'adjacence. Elle est sans perte mais n'expose que la structure locale.
Tokenisation spectrale (Laplacienne) : Dérive les jetons de la décomposition en valeurs propres du Laplacien du graphe ( $L = D - A$ ). Elle capture les propriétés topologiques globales mais est équivariante par permutation.
Tokenisation par marche aléatoire : Encode les probabilités de retour des marches aléatoires de longueur $1 $à$ t(n)$. Elle capture les motifs de diffusion mais est intrinsèquement avec perte.

La méthodologie combine une analyse de complexité théorique avec des expériences contrôlées.

Analyse théorique : Les auteurs établissent des bornes inférieures et des résultats d'impossibilité en mappant les tâches sur graphes vers des classes de complexité (par exemple, $TC^0$ , $NC^1$ , $L$ ). Ils analysent comment des tâches spécifiques (par exemple, détection de $k$ -cycles fermés, connectivité, comptage de triangles, planarité) se comportent sous différentes tokenisations, en tenant compte des contraintes de profondeur finie et des propriétés mathématiques des représentations de jetons (par exemple, nombres de conditionnement, perte d'information).
Validation empirique : Des expériences sont menées sur des tâches synthétiques (validant les séparations de profondeur) et des benchmarks réels (GraphBench, Open Graph Benchmark, ZINC). L'étude évalue les Transformers utilisant des versions complètes et tronquées de chaque tokenisation, ainsi que des tokenisations combinées, en comparant les performances par rapport aux bases de référence DeepSet et GIN.

Contributions clés

1. Formalisation de la tokenisation comme contrainte de calcul

L'article formalise comment la représentation d'entrée contraint l'expressivité des Transformers à profondeur finie. Il démontre que la tokenisation n'est pas simplement une étape d'ingénierie des caractéristiques, mais un déterminant des dépendances structurelles accessibles au modèle.

2. Séparations de profondeur entre tokenisations

Les auteurs prouvent que le même calcul sur un graphe peut nécessiter des profondeurs très différentes selon la tokenisation :

Marche aléatoire vs Adjacence : La détection d'un $k$ -cycle fermé est soluble en profondeur $O(1)$ avec la tokenisation par marche aléatoire (car les statistiques sont explicites) mais nécessite une profondeur $\Omega(\log k)$ avec la tokenisation par adjacence. Cela est prouvé par une réduction du problème du mot sur le groupe de permutations $S_5$ (un problème $NC^1$ -complet) vers la topologie du graphe, montrant que les Transformers à profondeur constante ( $TC^0$ ) ne peuvent pas simuler la traversal de chemin séquentiel requise par les jetons d'adjacence.
Adjacence vs Spectrale : La résolution de la connectivité globale du graphe nécessite une profondeur $\Omega(\log n)$ avec la tokenisation par adjacence, tandis que la tokenisation spectrale la résout en profondeur $O(1)$ .

3. Limitations intrinsèques et perte d'information

La marche aléatoire est prouvée avec perte : Indépendamment de la longueur de la marche, la tokenisation par marche aléatoire ne peut pas déterminer la planarité d'un graphe. Les auteurs construisent des graphes planaires et non planaires avec des distributions de marche aléatoire identiques en utilisant le basculement Godsil-McKay (GM), prouvant qu'aucune profondeur ou largeur de Transformer ne peut récupérer la distinction topologique.
La troncature spectrale est fragile : Tronquer le spectre du Laplacien (même d'une seule valeur propre) peut rendre le comptage de triangles impossible. Les auteurs montrent que l'ajout d'une arête entre des nœuds symétriques ne change qu'une seule valeur propre ; si cette valeur propre est tronquée, le transformer ne peut pas distinguer les graphes.
Troncature par adjacence : Tronquer la dimension des jetons d'adjacence (via une projection aléatoire) détruit la capacité à résoudre des tâches comme le comptage de triangles, comme prouvé par des bornes inférieures de complexité de communication (Disjonction d'ensembles).

4. Mauvais conditionnement de la tokenisation spectrale pour les tâches locales

Bien que la tokenisation spectrale capture la topologie globale, elle est mathématiquement mal conditionnée pour les tâches locales comme la prédiction d'arêtes. L'article dérive une borne inférieure montrant que les normes de paramètres requises pour décoder une arête locale à partir d'un spectre global évoluent avec le degré maximal ( $d_{max}$ ). Cela force un compromis : soit le modèle souffre de saturation Softmax (gradients disparaissants), soit il nécessite des poids explosifs, rendant l'optimisation difficile.

5. Impossibilité de conversion à profondeur limitée

L'article établit que la conversion entre familles de tokenisation est généralement impossible à profondeur limitée.

Un Transformer ne peut pas convertir efficacement les jetons d'adjacence en statistiques de marche aléatoire (nécessite une profondeur $\Omega(\log k)$ ).
Un Transformer ne peut pas récupérer les représentations complètes d'adjacence ou de Laplacien à partir de jetons de marche aléatoire (en raison de la perte d'information).
La conversion entre vues globales (Spectrale) et locales (Adjacence) entraîne des goulots d'étranglement de calcul sévères ou une instabilité d'optimisation.

Résultats

Résultats théoriques :

Séparations de profondeur : La validation empirique confirme que la tokenisation spectrale résout les tâches de connectivité avec $L=1$ pour toutes les tailles de graphes, tandis que la tokenisation par adjacence s'effondre vers une performance aléatoire pour les graphes plus grands ( $n \ge 128$ ).
Limites de récupération : Lors de l'entraînement d'un Transformer pour prédire les probabilités de retour de marche aléatoire à partir de jetons d'adjacence, l'erreur augmente avec la longueur de marche $k$ , ce qui est cohérent avec l'exigence de profondeur $\Omega(\log k)$ .
Planarité : Les modèles utilisant des jetons de marche aléatoire échouent à distinguer les graphes planaires des graphes non planaires, même avec une profondeur accrue, confirmant le résultat d'impossibilité théorique.

Résultats empiriques :

Dépendance à la tâche : Aucune tokenisation unique ne domine.
- Tâches locales : La tokenisation par adjacence fonctionne le mieux sur des tâches gouvernées par des contraintes locales explicites (par exemple, Clique maximale, ordonnancement topologique).
- Tâches globales : La tokenisation spectrale (Laplacienne) fonctionne le mieux sur des tâches dépendant de la géométrie globale (par exemple, prédiction de propriétés moléculaires Tox21).
- Approche combinée : Combiner des tokenisations complémentaires (Adjacence + Spectrale + Marche aléatoire) donne souvent les meilleures performances, permettant au modèle de tirer parti de signaux structurels distincts.
Effets de troncature : Les tokenisations tronquées dégradent généralement les performances, en particulier pour les tâches nécessitant une récupération structurelle exacte (par exemple, comptage de triangles), validant la « fragilité » théorique de la troncature.

Importance et affirmations

L'article affirme que la tokenisation de graphes est un compromis fondamental plutôt qu'un détail de prétraitement. Le choix de la tokenisation dicte la « vue » du graphe que le Transformer reçoit, contraignant ainsi la classe de dépendances structurelles que le modèle peut exprimer à profondeur finie.

Les points clés soulignés par les auteurs incluent :

Non-interchangeabilité : Les tokenisations par adjacence, spectrale et marche aléatoire ne sont pas interchangeables ; elles induisent des régimes de profondeur et des limites d'expressivité distincts.
Limitations inhérentes : Des tokenisations spécifiques ont des angles morts prouvés (par exemple, la marche aléatoire ne peut pas voir la planarité ; la spectrale est mal conditionnée pour les arêtes locales).
Barrières de conversion : Les Transformers ne peuvent pas simplement « apprendre » à convertir efficacement entre ces représentations si la tokenisation initiale est défavorable ; la profondeur requise pour combler ces écarts peut être prohibitif.
Implication pratique : La tokenisation optimale dépend de la nature structurelle de la tâche en aval. Combiner des vues complémentaires est une stratégie robuste pour surmonter les limitations de toute représentation unique.

Les auteurs concluent que, bien que leur analyse se concentre sur les tokenisations au niveau des nœuds, les résultats suggèrent un principe plus large : la représentation d'entrée est un axe critique de complexité dans l'apprentissage sur les graphes, et les travaux futurs devraient explorer les défis d'optimisation et les tokenisations au niveau des arêtes.