Resumo Técnico: TIDFormer

Declaração do Problema

O artigo aborda duas limitações críticas nos métodos existentes de aprendizado de Grafos Dinâmicos de Tempo Contínuo (CTDG) baseados em Transformer:

1. Mecanismos de Auto-Atenção (SAMs) Não Interpretáveis: Trabalhos anteriores definem SAMs em grafos dinâmicos de formas que carecem de interpretabilidade em relação a tarefas de downstream por ligação (link-wise). Especificamente, as definições de Nível de Nó Único (SL) (ex: TGAT) falham em capturar dependências entre pares de nós necessárias para a predição de ligações, enquanto as definições de Nível Multi-Nó (ML) (ex: DyGFormer) misturam sequências de nós de origem e destino, o que pode interromper a ordem cronológica e comprometer o aprendizado dos pesos de atenção.
2. Modelagem de Dinâmica Ineficiente e Insuficiente: Métodos existentes lutam para codificar efetivamente as dinâmicas temporais e interativas sem introduzir complexidade excessiva.
   • Codificação Temporal: Mapeamentos comuns baseados em cosseno falham em capturar características de fase e periódicas (ex: padrões semanais, mensais) inerentes aos grafos dinâmicos.
   • Codificação Interativa: Módulos de interação de vizinhos frequentemente degradam quando aplicados a grafos bipartidos (ex: sistemas usuário-item) porque os nós de origem e destino não compartilham vizinhos comuns sob amostragem de primeira ordem, reduzindo o módulo a apenas registrar tempos de interação.

Metodologia

Os autores propõem o TIDFormer, um Transformer de grafo dinâmico projetado para explorar totalmente as Dinâmicas Temporais e Interativas (Dynamic) usando um SAM interpretável e uma série de módulos de codificação eficientes.

1. Mecanismo de Auto-Atenção Interpretável no Nível de Interação (IL)

A mudança arquitetônica central é definir o SAM no Nível de Interação.

• Conceito: Em vez de tokenizar nós individuais (SL) ou misturar sequências de origem/destino (ML), a sequência é construída com base nas interações históricas entre pares de nós.
• Estrutura: Cada token na sequência $H_{IL}$ consiste nas características originais de nó/aresta concatenadas com um embedding temporal-interativo ($I$).
• Benefício: Isso preserva a ordem cronológica original enquanto modela explicitamente as dependências entre pares de nós que interagem, alinhando o mecanismo de atenção com os requisitos de tarefas de downstream por ligação.

2. Módulos de Codificação

O TIDFormer introduz três módulos específicos para codificar dinâmicas de forma eficiente usando apenas vizinhos de primeira ordem:

• Codificação Temporal de Granularidade Mista (MTE):

  • Integra carimbos de tempo (timestamps) relativos de grão fino com partições de tempo baseadas em calendário de grão grosso (semanal, mensal, anual).
  • Utiliza uma função cosseno para intervalos de grão fino e uma projeção linear para segmentos de grão grosso.
  • Isso captura tanto dependências temporais imediatas quanto padrões periódicos globais sem transformações complexas de domínio de frequência.

• Codificação de Interação Bidirecional (BIE):

  • Aborda o problema de "ausência de vizinho comum" em grafos bipartidos.
  • Utiliza um mecanismo bidirecional onde, para um par origem-destino, o modelo recupera os vizinhos de segunda ordem do outro nó a partir dos dicionários de vizinhos do lote atual.
  • Isso reconstrói efetivamente informações de interação de ordem superior usando apenas amostragem de primeira ordem, expandindo significativamente o campo receptivo sem o custo computacional da amostragem de ordem superior explícita.

• Codificação de Sazonalidade e Tendência (STE):

  • Decompõe a sequência de interação em componentes de tendência e sazonalidade usando uma operação simples de pooling médio.
  • O componente de tendência ($Z_t$) representa o padrão de interação geral suavizado, enquanto o componente sazonal ($Z_s$) captura flutuações periódicas.
  • Isso permite que o modelo modele conjuntamente características temporais e interativas ao capturar potenciais mudanças nos padrões de interação histórica.

3. Arquitetura

Os embeddings codificados (Nó/Aresta Inicial + MTE + BIE + STE) são concatenados para formar a sequência de entrada para o backbone do Transformer. O modelo emprega Auto-Atenção de Múltiplas Cabeças (MSA) no Nível de Interação, seguido por Redes Feed-Forward (FFN) padrão com conexões residuais e Normalização de Camada (Layer Normalization).

Principais Contribuições

1. Modelo TIDFormer: Um modelo de grafo dinâmico baseado em Transformer que minera totalmente as dinâmicas temporais e interativas.
2. SAM Interpretável: A proposta e verificação experimental de um SAM de Nível de Interação, resolvendo os problemas de interpretabilidade das definições anteriores de SL e ML.
3. Novos Módulos de Codificação: A introdução dos módulos MTE, BIE e STE, que capturam efetivamente dinâmicas complexas usando apenas vizinhos de primeira ordem, evitando o overhead computacional de amostragem de ordem superior ou transformadas de frequência complexas.

Resultados Experimentais

Os autores avaliaram o TIDFormer em sete conjuntos de dados de CTDG do mundo real (Wikipedia, Reddit, MOOC, LastFM, Enron, Social Evo., UCI) em duas tarefas: Predição de Ligação Dinâmica e Classificação de Nó Dinâmica.

• Desempenho: O TIDFormer superou os modelos de estado da arte (SOTA) (incluindo JODIE, TGAT, TGN, DyGFormer, FreeDyG, etc.) na maioria dos conjuntos de dados e configurações experimentais (transdutivas e indutivas).
  • Na predição de ligação transdutiva com amostragem negativa aleatória, o TIDFormer alcançou um rank médio de 1.57.
  • Na classificação de nós, alcançou um rank médio de 2.00.
• Eficiência:
  • A complexidade de tempo do TIDFormer é $O(n) + O(n^2 \times dim)$, comparável aos Transformers de amostragem de primeira ordem.
  • É significativamente mais eficiente que os métodos de amostragem de segunda ordem (que possuem complexidade $O(n^2)$ na etapa de amostragem).
  • Resultados empíricos no conjunto de dados Wikipedia mostraram o TIDFormer alcançando maior precisão (AP) de predição de ligação com menor tempo de treinamento por época em comparação ao TGAT, TGN e DyGFormer.

Significância e Alegações

O artigo afirma que explorar dinâmicas temporais e interativas pode "facilmente criar um ótimo Transformer de grafo dinâmico" quando feito corretamente. A significância do trabalho reside em:

• Correção da Interpretabilidade: Fornecer uma definição de SAM para grafos dinâmicos teoricamente sólida e experimentalmente verificada que se alinha com a natureza cronológica dos dados e os requisitos de predição de ligação.
• Eficiência vs. Desempenho: Demonstrar que o alto desempenho não requer módulos complexos e computacionalmente caros (como transformadas de Fourier ou amostragem de ordem superior). Os módulos de decomposição simples e mecanismos bidirecionais propostos são suficientes para capturar dinâmicas complexas.
• Generalização: O modelo performa de forma robusta tanto em grafos bipartidos (ex: usuário-item) quanto não-bipartidos, superando uma limitação específica de abordagens anteriores de codificação de vizinhos.

Os autores concluem que o TIDFormer representa um passo à frente no equilíbrio entre a eficácia e a eficiência do aprendizado de grafos dinâmicos, embora reconheçam que trabalhos futuros poderiam focar em otimizar ainda mais a escalabilidade e comparar contra modelos baseados em memória.