Resumo Técnico: Perdido na Tokenização: Trade-offs Fundamentais em Tokenização de Grafos para Transformers

Declaração do Problema

Transformers emergiram como uma arquitetura poderosa para aprendizado em grafos, no entanto, sua aplicação a dados estruturados em grafos requer uma etapa preliminar: tokenização. Diferentemente de sequências ou grades, grafos carecem de um formato de entrada contínuo canônico. Consequentemente, deve-se escolher um mapeamento de grafo para token para determinar quais informações estruturais são expostas ao modelo na camada de entrada.

Embora existam várias estratégias de tokenização (por exemplo, espectral, passeio aleatório, adjacência), elas são frequentemente tratadas como escolhas de design empíricas ou detalhes de pré-processamento. Este artigo postula que a escolha da tokenização é um componente fundamental da expressividade do transformer. O problema central abordado é se diferentes tokenizações são intercambiáveis ou se induzem regimes computacionais distintos, especificamente regarding a profundidade necessária para resolver tarefas de grafos e a capacidade de recuperar informações estruturais.

Metodologia

Os autores formalizam a tokenização de grafos como parte integrante do modelo computacional, analisando a expressividade de Transformers com profundidade finita ($L$), largura ($m$) e precisão ($p$) sob três famílias principais de tokenização:

1. Tokenização por Adjacência: Codifica a conectividade local de cada nó através de sua linha de adjacência. É sem perdas, mas expõe apenas a estrutura local.
2. Tokenização Espectral (Laplaciana): Deriva tokens da decomposição espectral do Laplaciano do grafo ($L = D - A$). Captura propriedades topológicas globais, mas é equivariante a permutações.
3. Tokenização por Passeio Aleatório: Codifica probabilidades de retorno de passeios aleatórios de comprimento $1$a$t(n)$. Captura padrões de difusão, mas é inerentemente com perdas.

A metodologia combina análise de complexidade teórica com experimentos controlados.

• Análise Teórica: Os autores estabelecem limites inferiores e resultados de impossibilidade mapeando tarefas de grafos para classes de complexidade (por exemplo, $TC^0$, $NC^1$, $L$). Eles analisam como tarefas específicas (por exemplo, detecção de $k$-caminhos fechados, conectividade, contagem de triângulos, planaridade) se comportam sob diferentes tokenizações, considerando as restrições de profundidade finita e as propriedades matemáticas das representações de tokens (por exemplo, números de condição, perda de informação).
• Validação Empírica: Experimentos são conduzidos em tarefas sintéticas (validando separações de profundidade) e benchmarks do mundo real (GraphBench, Open Graph Benchmark, ZINC). O estudo avalia Transformers usando versões completas e truncadas de cada tokenização, bem como tokenizações combinadas, comparando o desempenho contra baselines de DeepSet e GIN.

Principais Contribuições

1. Formalização da Tokenização como Restrição Computacional

O artigo formaliza como a representação de entrada restringe a expressividade do transformer em profundidade finita. Demonstra-se que a tokenização não é meramente uma etapa de engenharia de características, mas um determinante de quais dependências estruturais são acessíveis ao modelo.

2. Separações de Profundidade entre Tokenizações

Os autores provam que a mesma computação em grafos pode exigir profundidades drasticamente diferentes dependendo da tokenização:

• Passeio Aleatório vs. Adjacência: Detectar um $k$-caminho fechado é solucionável em profundidade $O(1)$ com tokenização por Passeio Aleatório (pois as estatísticas são explícitas), mas requer profundidade $\Omega(\log k)$ com tokenização por Adjacência. Isso é provado via uma redução do problema da palavra no grupo de permutações $S_5$ (um problema completo em $NC^1$) para topologia de grafos, mostrando que Transformers de profundidade constante ($TC^0$) não podem simular a travessia sequencial de caminhos exigida pelos tokens de Adjacência.
• Adjacência vs. Espectral: Resolver a conectividade global do grafo requer profundidade $\Omega(\log n)$ com tokenização por Adjacência, enquanto a tokenização Espectral resolve em profundidade $O(1)$.

3. Limitações Inerentes e Perda de Informação

• Passeio Aleatório é Provavelmente com Perdas: Independentemente do comprimento do passeio, a tokenização por Passeio Aleatório não pode determinar a planaridade do grafo. Os autores constroem grafos planares e não planares com distribuições idênticas de Passeio Aleatório usando comutação Godsil-McKay (GM), provando que nenhuma profundidade ou largura de Transformer pode recuperar a distinção topológica.
• Truncamento Espectral é Frágil: Truncar o espectro Laplaciano (mesmo por um único autovalor) pode tornar a contagem de triângulos impossível. Os autores mostram que adicionar uma aresta entre nós simétricos altera apenas um autovalor; se esse autovalor for truncado, o transformer não consegue distinguir os grafos.
• Truncamento de Adjacência: Truncar a dimensão dos tokens de adjacência (via projeção aleatória) destrói a capacidade de resolver tarefas como contagem de triângulos, conforme provado por limites inferiores de complexidade de comunicação (Disjunção de Conjuntos).

4. Mau Condicionamento da Tokenização Espectral para Tarefas Locais

Embora a tokenização Espectral capture a topologia global, ela é matematicamente mal condicionada para tarefas locais como previsão de arestas. O artigo deriva um limite inferior mostrando que as normas de parâmetros necessárias para decodificar uma aresta local a partir de um espectro global escalam com o grau máximo ($d_{max}$). Isso força um trade-off: ou o modelo sofre de saturação de Softmax (gradientes que desaparecem) ou requer pesos explosivos, tornando a otimização difícil.

5. Impossibilidade de Conversão em Profundidade Limitada

O artigo estabelece que converter entre famílias de tokenização é geralmente impossível em profundidade limitada.

• Um Transformer não pode converter eficientemente tokens de Adjacência em estatísticas de Passeio Aleatório (requer profundidade $\Omega(\log k)$).
• Um Transformer não pode recuperar representações completas de Adjacência ou Laplaciana a partir de tokens de Passeio Aleatório (devido à perda de informação).
• A conversão entre visões globais (Espectral) e locais (Adjacência) incorre em gargalos computacionais severos ou instabilidade de otimização.

Resultados

Descobertas Teóricas:

• Separações de Profundidade: A validação empírica confirma que a tokenização Espectral resolve tarefas de conectividade com $L=1$ em todos os tamanhos de grafo, enquanto a tokenização por Adjacência colapsa para desempenho ao acaso em grafos maiores ($n \ge 128$).
• Limites de Recuperação: Ao treinar um Transformer para prever probabilidades de retorno de Passeio Aleatório a partir de tokens de Adjacência, o erro cresce com o comprimento do passeio $k$, consistente com o requisito de profundidade $\Omega(\log k)$.
• Planaridade: Modelos usando tokens de Passeio Aleatório falham em distinguir grafos planares de não planares, mesmo com profundidade aumentada, confirmando o resultado teórico de impossibilidade.

Descobertas Empíricas:

• Dependência da Tarefa: Nenhuma tokenização única domina.
  • Tarefas Locais: A tokenização por Adjacência desempenha melhor em tarefas governadas por restrições locais explícitas (por exemplo, Máximo Clique, Ordenação Topológica).
  • Tarefas Globais: A tokenização Espectral (Laplaciana) desempenha melhor em tarefas dependentes da geometria global (por exemplo, previsão de propriedades moleculares Tox21).
  • Abordagem Combinada: Combinar tokenizações complementares (Adjacência + Espectral + Passeio Aleatório) frequentemente produz o melhor desempenho, permitindo que o modelo aproveite sinais estruturais distintos.
• Efeitos do Truncamento: Tokenizações truncadas geralmente degradam o desempenho, particularmente para tarefas que exigem recuperação estrutural exata (por exemplo, contagem de triângulos), validando a "fragilidade" teórica do truncamento.

Significado e Afirmações

O artigo afirma que a tokenização de grafos é um trade-off fundamental e não um detalhe de pré-processamento. A escolha da tokenização dita a "visão" do grafo que o transformer recebe, restringindo assim a classe de dependências estruturais que o modelo pode expressar em profundidade finita.

As principais conclusões enfatizadas pelos autores incluem:

1. Não Intercambiabilidade: Tokenizações por Adjacência, Espectral e Passeio Aleatório não são intercambiáveis; elas induzem regimes de profundidade distintos e limites de expressividade.
2. Limitações Inerentes: Tokenizações específicas têm pontos cegos prováveis (por exemplo, Passeio Aleatório não pode ver planaridade; Espectral é mal condicionado para arestas locais).
3. Barreiras de Conversão: Transformers não podem simplesmente "aprender" a converter eficientemente entre essas representações se a tokenização inicial for desfavorável; a profundidade necessária para preencher essas lacunas pode ser proibitiva.
4. Implicação Prática: A tokenização ótima depende da natureza estrutural da tarefa downstream. Combinar visões complementares é uma estratégia robusta para superar as limitações de qualquer representação única.

Os autores concluem que, embora sua análise foque em tokenizações em nível de nó, as descobertas sugerem um princípio mais amplo: a representação de entrada é um eixo crítico de complexidade no aprendizado de grafos, e trabalhos futuros devem explorar desafios de otimização e tokenizações em nível de aresta.