Resumo Técnico: Assinaturas de Motivos Temporais para Redes Neurais de Grafos Temporais

Declaração do Problema

Fluxos de interação temporal do mundo real (ex: comunicações sociais, transferências financeiras, avaliações online) contêm uma estrutura preditiva dentro de padrões de motivos de curto horizonte, tais como repetição, reciprocidade, diversidade de estrelas e fluxo triádico. Embora as modernas Redes Neurais de Grafos Temporais (TGNNs) sejam modelos de sequência expressivos capazes de extrair teoricamente qualquer função de um fluxo temporal, seus vieses indutivos e orçamentos de treinamento limitados muitas vezes as impedem de capturar regularidades estruturais específicas de curto horizonte. Essas regularidades são frequentemente simples de computar analiticamente, mas são críticas para tarefas de jusante (downstream). O artigo aborda a lacuna entre o que as TGNNs padrão aprendem e as estatísticas explícitas de curto horizonte que caracterizam os fluxos temporais, questionando se uma aumentação principista e agnóstica à arquitetura pode preencher essa lacuna residual.

Metodologia

1. Diagnósticos Empíricos e Identificação de Assinaturas

Os autores primeiro analisam as contagens de motivos por candidato, em janelas passadas, através de um conjunto diversificado de 13 conjuntos de dados temporais reais e sintéticos (incluindo MOOC, Bitcoin Alpha/OTC e benchmarks TGB). Eles identificam que a atividade de motivos se organiza consistentemente ao longo de três eixos estáveis de escala:

• A1 (Recência Diádica/Reciprocidade): Captura o tempo e a frequência de interações diretas entre um par candidato $(u, v)$.
• A2 (Diversidade de Estrelas): Mede a diversidade de vizinhos interagindo com $u$ ou $v$ dentro de uma janela de tempo (ex: o número de itens distintos com os quais um estudante interagiu).
• A3 (Fluxo Triádico): Captura o fluxo de interações através de terceiros que fazem a ponte entre $u$ e $v$ (ex: vizinhos comuns).

2. O Mapa de Características de Motivo $h(u, v, t)$

Com base nesses eixos, os autores projetam um mapa de características de motivo compacto, de 13 coordenadas, local ao candidato, $h(u, v, t) \in \mathbb{R}^{13}$. As principais restrições de projeto incluem:

• Segurança contra Vazamento (Leakage Safety): As características são computadas estritamente a partir da janela passada $W_{t}^{past}(\Delta) = \{i : t - \Delta \le t_i < t\}$, garantindo que nenhuma informação futura vaze para a representação do candidato.
• Dimensão Fixa: As 13 características são concatenadas via uma matriz de incorporação linear aprendível $M$ em qualquer codificador estático ou temporal sem mudanças arquiteturais.
• Subfamílias: As 13 coordenadas correspondem aos três eixos:
  • A1 (5 características): Contagens de eventos $u \to v$ e $v \to u$, eventos pareados, burstiness (explosividade) e tempo normalizado desde o último evento recíproco.
  • A2 (4 características): Tamanhos dos conjuntos de vizinhos distintos ($N_{u}^{out}, N_{u}^{in}, N_{v}^{out}, N_{v}^{in}$) dentro da janela, limitados (capped) para lidar com hubs.
  • A3 (4 características): Tamanhos das interseções direcionadas de cunha cruzada (cross-wedge) e bi-cunha (bi-wedge) entre os conjuntos de vizinhos de $u$ e $v$.
• Normalização: Coordenadas de contagem de cauda pesada passam por uma transformação $\log_{10}(1+x)$ para garantir comparabilidade.

3. Posicionamento Teórico (Weisfeiler-Leman Temporal)

O artigo estabelece um limite teórico para as MP-GNNs temporais padrão (redes neurais de grafos de passagem de mensagem). Sob uma abstração comum de pontuação de aresta, esses modelos são limitados pelo primeiro nível de uma hierarquia Weisfeiler-Leman temporal ancorada no candidato (temporal-1-WL).

• Os autores provam que existem fluxos ancorados (ex: um ciclo $C_6$ versus dois triângulos disjuntos $2K_3$) que a temporal-1-WL não consegue distinguir (colapsando-os para a mesma cor), mas o mapa de características de motivo $h$ os distingue perfeitamente.
• Isso coloca a aumentação de motivos estritamente acima do poder de expressão das MP-GNNs temporais padrão, atuando como uma "testemunha" que quebra o gargalo da WL.

Principais Contribuições

1. Diagnósticos (Seção 4): O artigo articula que as contagens de motivos por candidato organizam os fluxos temporais ao longo de três eixos dominantes e estáveis de escala (A1, A2, A3). Essas assinaturas por conjunto de dados predizem onde a aumentação de motivos gerará os maiores ganhos de desempenho.
2. Expressividade Temporal (Seção 6): Os autores fornecem um posicionamento teórico das MP-GNNs temporais padrão dentro de uma hierarquia temporal-WL ancorada no candidato. Eles exibem um par específico de fluxos onde as características de motivos distinguem candidatos que a temporal-1-WL colapsa, demonstrando que a aumentação eleva o modelo além do primeiro nível desta hierarquia.
3. Desempenho Empírico (Seção 7): O artigo demonstra que a aumentação de motivos eleva consistentemente o desempenho em tarefas heterogêneas (predição de propriedade de ligação TGB, classificação de arestas e classificação de nível de grafo) quando comparado a fortes baselines de TGNN. O ganho é interpretável: é maior onde o baseline falha em capturar a estrutura de curto horizonte (ex: MOOC) e negligenciável onde o baseline já captura a estrutura relevante.

Resultados Experimentais

O framework foi avaliado em:

• Predição de Propriedade de Ligação TGB: Através de cinco baselines (TPNet, HyperEvent, DyGFormer, TNCN, TGN) e três conjuntos de dados (Wiki, Review, Coin).
  • Resultado: A aumentação de motivos elevou o desempenho em todos os pares baseline-conjunto de dados avaliados. O ganho mais significativo foi observado no DyGFormer para o conjunto de dados tgbl-review-v2, onde o Mean Reciprocal Rank (MRR) aumentou de 0.224 para 0.413.
  • Observação: Os ganhos ficaram dentro de um desvio padrão de zero para baselines como o TPNet no tgbl-coin-v2, consistente com o fato de que esses baselines já capturam a estrutura de curto horizonte relevante para esse conjunto de dados específico.
• Classificação de Arestas:
  • MOOC: Uma tarefa de classificação binária prevendo o abandono de estudantes. Um codificador GraphSAGE vanilla alcançou um PR-AUC de 0.0164. Adicionar o subconjunto de 4 características de contagem de estrelas (A2) elevou isso para 0.1430, e o mapa completo de 13 características alcançou 0.1659.
  • Bitcoin Alpha/OTC: Tarefas de classificação de confiança mostraram melhorias modestas, mas consistentes (ex: SAGE PR-AUC de 0.9282 para 0.9667 no Alpha).
• Classificação de Nível de Grafo: Em geradores temporais sintéticos, a aumentação de motivos melhorou a acurácia significativamente, elevando notavelmente o GAT de um colapso de 16.7% (predição da classe majoritária) para 94.0% sem mudanças arquiteturais.

Ablação e Controles:

• A análise de exclusão (leave-one-out) confirmou que nenhuma coordenada é uniformemente redundante; diferentes conjuntos de dados dependem de diferentes eixos (ex: MOOC depende fortemente da diversidade de estrelas A2, enquanto Bitcoin Alpha depende de A1 reciprocidade).
• Controles descartaram "capacidade extra" como fonte dos ganhos (características aleatórias não replicaram o aumento) e confirmaram que o ganho não é meramente um proxy para contagens simples de atividade de nós.

Significância e Alegações

O artigo afirma que as assinaturas de motivos temporais fornecem um método compacto, interpretável e agnóstico à arquitetura para injetar regularidades estruturais de curto horizonte em TGNNs.

• Poder Preditivo: A assinatura por conjunto de dados ao longo dos eixos A1/A2/A3 serve como uma ferramenta de diagnóstico para prever onde a aumentação será mais benéfica.
• Fundamentação Teórica: Ao posicionar a aumentação em relação à hierarquia temporal-WL, o artigo esclarece por que as TGNNs padrão falham em certas tarefas (elas são limitadas pela temporal-1-WL) e como a aumentação supera isso.
• Utilidade Prática: O método não requer mudanças na arquitetura do codificador subjacente, apenas a concatenação de um vetor de características pré-computado, tornando-o facilmente implantável em pipelines existentes.

Os autores mantêm uma postura modesta, observando que o raio da janela $\Delta$ é um hiperparâmetro sensível e que, em fluxos esparsos onde o fluxo triádico é negligenciável, a aumentação reduz-se a um subespaço de menor dimensão com ganhos correspondentemente menores. O framework é apresentado como uma forma principista de expor sinais estruturais específicos que as vanilla TGNNs frequentemente falham em expor aos seus pontuadores de aresta (edge scorers).