Resumen Técnico: Perdidos en la Tokenización: Compensaciones Fundamentales en la Tokenización de Grafos para Transformers

Declaración del Problema

Los Transformers han surgido como una arquitectura poderosa para el aprendizaje en grafos, sin embargo, su aplicación a datos con estructura de grafo requiere un paso preliminar: la tokenización. A diferencia de las secuencias o las cuadrículas, los grafos carecen de un formato de entrada continuo canónico. En consecuencia, debe elegirse un mapa de grafo a token para determinar qué información estructural se expone al modelo en la capa de entrada.

Aunque existen diversas estrategias de tokenización (por ejemplo, espectral, de paseo aleatorio, de adyacencia), a menudo se tratan como elecciones de diseño empíricas o detalles de preprocesamiento. Este trabajo postula que la elección de la tokenización es un componente fundamental de la expresividad del Transformer. El problema central abordado es si las diferentes tokenizaciones son intercambiables o si inducen regímenes computacionales distintos, específicamente en lo que respecta a la profundidad requerida para resolver tareas de grafos y la capacidad de recuperar información estructural.

Metodología

Los autores formalizan la tokenización de grafos como parte integral del modelo computacional, analizando la expresividad de los Transformers con profundidad finita ($L$), ancho ($m$) y precisión ($p$) bajo tres familias principales de tokenización:

1. Tokenización de Adyacencia: Codifica la conectividad local de cada nodo a través de su fila de adyacencia. Es sin pérdida pero expone únicamente la estructura local.
2. Tokenización Espectral (Laplaciana): Deriva los tokens de la descomposición espectral del Laplaciano del grafo ($L = D - A$). Captura propiedades topológicas globales pero es equivariante a permutaciones.
3. Tokenización de Paseo Aleatorio: Codifica las probabilidades de retorno de paseos aleatorios de longitud $1$a$t(n)$. Captura patrones de difusión pero es inherentemente con pérdida.

La metodología combina análisis de teoría de la complejidad con experimentos controlados.

• Análisis Teórico: Los autores establecen cotas inferiores y resultados de imposibilidad mapeando tareas de grafos a clases de complejidad (por ejemplo, $TC^0$, $NC^1$, $L$). Analizan cómo tareas específicas (por ejemplo, detección de $k$-caminos cerrados, conectividad, conteo de triángulos, planitud) se comportan bajo diferentes tokenizaciones, considerando las restricciones de profundidad finita y las propiedades matemáticas de las representaciones de los tokens (por ejemplo, números de condición, pérdida de información).
• Validación Empírica: Se realizan experimentos en tareas sintéticas (validando separaciones de profundidad) y en benchmarks del mundo real (GraphBench, Open Graph Benchmark, ZINC). El estudio evalúa Transformers utilizando versiones completas y truncadas de cada tokenización, así como tokenizaciones combinadas, comparando el rendimiento frente a las líneas base de DeepSet y GIN.

Contribuciones Clave

1. Formalización de la Tokenización como una Restricción Computacional

El trabajo formaliza cómo la representación de entrada restringe la expresividad del Transformer a profundidad finita. Demuestra que la tokenización no es meramente un paso de ingeniería de características, sino un determinante de qué dependencias estructurales son accesibles para el modelo.

2. Separaciones de Profundidad entre Tokenizaciones

Los autores prueban que el mismo cálculo de grafo puede requerir profundidades muy diferentes dependiendo de la tokenización:

• Paseo Aleatorio vs. Adyacencia: La detección de un $k$-camino cerrado es resoluble en profundidad $O(1)$ con tokenización de Paseo Aleatorio (ya que las estadísticas son explícitas), pero requiere una profundidad de $\Omega(\log k)$ con tokenización de Adyacencia. Esto se prueba mediante una reducción del problema de la palabra en el grupo de permutaciones $S_5$ (un problema completo en $NC^1$) a la topología del grafo, mostrando que los Transformers de profundidad constante ($TC^0$) no pueden simular el recorrido secuencial de caminos requerido por los tokens de Adyacencia.
• Adyacencia vs. Espectral: Resolver la conectividad global del grafo requiere una profundidad de $\Omega(\log n)$ con tokenización de Adyacencia, mientras que la tokenización Espectral lo resuelve en profundidad $O(1)$.

3. Limitaciones Intrínsecas y Pérdida de Información

• El Paseo Aleatorio es Probablemente Con Pérdida: Independientemente de la longitud del paseo, la tokenización de Paseo Aleatorio no puede determinar la planitud del grafo. Los autores construyen grafos planos y no planos con distribuciones idénticas de Paseo Aleatorio utilizando el cambio de Godsil-McKay (GM), demostrando que ninguna profundidad o ancho de Transformer puede recuperar la distinción topológica.
• La Truncación Espectral es Frágil: Truncar el espectro del Laplaciano (incluso por un solo valor propio) puede hacer imposible el conteo de triángulos. Los autores muestran que añadir una arista entre nodos simétricos cambia solo un valor propio; si este valor propio se trunca, el Transformer no puede distinguir los grafos.
• Truncamiento de Adyacencia: Truncar la dimensión de los tokens de adyacencia (mediante proyección aleatoria) destruye la capacidad de resolver tareas como el conteo de triángulos, según se demuestra mediante cotas inferiores de complejidad de comunicación (Disjunción de Conjuntos).

4. Mal Acondicionamiento de la Tokenización Espectral para Tareas Locales

Aunque la tokenización Espectral captura la topología global, está matemáticamente mal acondicionada para tareas locales como la predicción de aristas. El trabajo deriva una cota inferior que muestra que las normas de los parámetros requeridas para decodificar una arista local a partir de un espectro global escalan con el grado máximo ($d_{max}$). Esto fuerza una compensación: o bien el modelo sufre saturación de Softmax (gradientes que se desvanecen) o requiere pesos que explotan, lo que dificulta la optimización.

5. Imposibilidad de Conversión a Profundidad Limitada

El trabajo establece que la conversión entre familias de tokenización es generalmente imposible a profundidad limitada.

• Un Transformer no puede convertir eficientemente tokens de Adyacencia en estadísticas de Paseo Aleatorio (requiere una profundidad de $\Omega(\log k)$).
• Un Transformer no puede recuperar representaciones completas de Adyacencia o Laplaciana a partir de tokens de Paseo Aleatorio (debido a la pérdida de información).
• La conversión entre vistas globales (Espectral) y locales (Adyacencia) incurre en cuellos de botella computacionales severos o inestabilidad de optimización.

Resultados

Hallazgos Teóricos:

• Separaciones de Profundidad: La validación empírica confirma que la tokenización Espectral resuelve tareas de conectividad con $L=1$ en todos los tamaños de grafo, mientras que la tokenización de Adyacencia colapsa a un rendimiento aleatorio para grafos más grandes ($n \ge 128$).
• Límites de Recuperación: Al entrenar un Transformer para predecir probabilidades de retorno de Paseo Aleatorio a partir de tokens de Adyacencia, el error crece con la longitud del paseo $k$, lo cual es consistente con el requisito de profundidad de $\Omega(\log k)$.
• Planitud: Los modelos que utilizan tokens de Paseo Aleatorio no logran distinguir grafos planos de no planos, incluso con mayor profundidad, confirmando el resultado teórico de imposibilidad.

Hallazgos Empíricos:

• Dependencia de la Tarea: Ninguna tokenización única domina.
  • Tareas Locales: La tokenización de Adyacencia funciona mejor en tareas gobernadas por restricciones locales explícitas (por ejemplo, Máximo Clique, Ordenamiento Topológico).
  • Tareas Globales: La tokenización Espectral (Laplaciana) funciona mejor en tareas dependientes de la geometría global (por ejemplo, predicción de propiedades moleculares en Tox21).
  • Enfoque Combinado: Combinar tokenizaciones complementarias (Adyacencia + Espectral + Paseo Aleatorio) a menudo produce el mejor rendimiento, permitiendo que el modelo aproveche señales estructurales distintas.
• Efectos de la Truncación: Las tokenizaciones truncadas generalmente degradan el rendimiento, particularmente para tareas que requieren una recuperación estructural exacta (por ejemplo, conteo de triángulos), validando la "fragilidad" teórica de la truncación.

Significado y Afirmaciones

El trabajo afirma que la tokenización de grafos es una compensación fundamental y no un detalle de preprocesamiento. La elección de la tokenización dicta la "vista" del grafo que recibe el Transformer, restringiendo así la clase de dependencias estructurales que el modelo puede expresar a profundidad finita.

Las conclusiones clave enfatizadas por los autores incluyen:

1. No Intercambiabilidad: Las tokenizaciones de Adyacencia, Espectral y de Paseo Aleatorio no son intercambiables; inducen regímenes de profundidad distintos y límites de expresividad.
2. Limitaciones Inherentes: Tokenizaciones específicas tienen puntos ciegos probables (por ejemplo, el Paseo Aleatorio no puede ver la planitud; la Espectral está mal acondicionada para aristas locales).
3. Barreras de Conversión: Los Transformers no pueden simplemente "aprender" a convertir entre estas representaciones de manera eficiente si la tokenización inicial es desfavorable; la profundidad requerida para cerrar estas brechas puede ser prohibitiva.
4. Implicación Práctica: La tokenización óptima depende de la naturaleza estructural de la tarea posterior. Combinar vistas complementarias es una estrategia robusta para superar las limitaciones de cualquier representación única.

Los autores concluyen que, aunque su análisis se centra en tokenizaciones a nivel de nodo, los hallazgos sugieren un principio más amplio: la representación de entrada es un eje crítico de complejidad en el aprendizaje de grafos, y el trabajo futuro debería explorar desafíos de optimización y tokenizaciones a nivel de arista.