Resumen Técnico: Firmas de Motivos Temporales para Redes Neuronales de Grafos Temporales

Declaración del Problema

Los flujos de interacción temporal del mundo real (por ejemplo, comunicaciones sociales, transferencias financieras, reseñas en línea) contienen una estructura predictiva dentro de patrones de motivos de corto horizonte, tales como la repetición, la reciprocidad, la diversidad de estrellas y el flujo triádico. Si bien las modernas Redes Neuronales de Grafos Temporales (TGNN) son modelos de secuencia expresivos capaces de extraer teóricamente cualquier función de un flujo temporal, sus sesgos inductivos y presupuestos de entrenamiento limitados a menudo les impiden capturar regularidades estructurales específicas de corto horizonte. Estas regularidades son frecuentemente sencillas de computar analíticamente, pero son críticas para las tareas de seguimiento. El artículo aborda la brecha entre lo que las TGNN estándar aprenden y las estadísticas explícitas de corto horizonte que caracterizan los flujos temporales, preguntando si un aumento basado en principios, agnóstico a la arquitectura, puede cerrar esta brecha residual.

Metodología

1. Diagnósticos Empíricos e Identificación de Firmas

Los autores analizan primero los recuentos de motivos por candidato en ventanas pasadas a través de un conjunto diverso de 13 conjuntos de datos temporales reales y sintéticos (incluyendo MOOC, Bitcoin Alpha/OTC y benchmarks de TGB). Identifican que la actividad de los motivos se organiza consistentemente a lo largo de tres ejes estables de escala:

• A1 (Recencia Diádica/Reciprocidad): Captura el tiempo y la frecuencia de las interacciones directas entre un par candidato $(u, v)$.
• A2 (Diversidad de Estrellas): Mide la diversidad de los vecinos que interactúan con $u$ o $v$ dentro de una ventana de tiempo (por ejemplo, el número de elementos distintos con los que un estudiante ha interactuado).
• A3 (Flujo Triádico): Captura el flujo de interacciones a través de terceros que conectan a $u$ y $v$ (por ejemplo, vecinos comunes).

2. El Mapa de Características de Motivos $h(u, v, t)$

Basándose en estos ejes, los autores diseñan un mapa de características de motivos compacto, de 13 coordenadas y local al candidato, $h(u, v, t) \in \mathbb{R}^{13}$. Las restricciones clave de diseño incluyen:

• Seguridad contra Filtraciones (Leakage Safety): Las características se computan estrictamente desde la ventana pasada $W_{t}^{past}(\Delta) = \{i : t - \Delta \le t_i < t\}$, asegurando que no haya filtración de información futura en la representación del candidato.
• Dimensión Fija: Las 13 características se concatenan mediante una matriz de incrustación lineal aprendible $M$ en cualquier codificador estático o temporal sin cambios arquitectónicos.
• Subfamilias: Las 13 coordenadas corresponden a los tres ejes:
  • A1 (5 características): Recuentos de eventos $u \to v$ y $v \to u$, eventos emparejados, estallidos (burstiness) y el tiempo normalizado desde el último evento recíproco.
  • A2 (4 características): Tamaños de los conjuntos de vecinos distintos ($N_{u}^{out}, N_{u}^{in}, N_{v}^{out}, N_{v}^{in}$) dentro de la ventana, limitados para manejar nodos centrales (hubs).
  • A3 (4 características): Tamaños de las intersecciones de cuñas cruzadas dirigidas y cuñas dobles entre los conjuntos de vecinos de $u$ y $v$.
• Normalización: Las coordenadas de recuento de cola pesada se someten a una transformación $\log_{10}(1+x)$ para asegurar la comparabilidad.

3. Ubicación Teórica (Weisfeiler-Leman Temporal)

El artículo establece un límite teórico para las GNN de paso de mensajes temporales (MP-GNN) estándar. Bajo una abstracción común de puntuación de aristas, estos modelos están limitados por el primer nivel de una jerarquía Weisfeiler-Leman temporal anclada al candidato (temporal-1-WL).

• Los autores demuestran que existen flujos temporales anclados (por ejemplo, un ciclo $C_6$ frente a dos triángulos disjuntos $2K_3$) que el temporal-1-WL no puede distinguir (colapsándolos al mismo color), pero que el mapa de características de motivos $h$ distingue perfectamente.
• Esto sitúa el aumento de motivos estrictamente por encima del poder de expresión de las MP-GNN temporales estándar, actuando como un "testigo" que rompe el cuello de botella de WL.

Contribuciones Clave

1. Diagnósticos (Sección 4): El artículo articula que los recuentos de motivos por candidato organizan los flujos temporales a lo largo de tres ejes dominantes y estables de escala (A1, A2, A3). Estas firmas por conjunto de datos predicen dónde el aumento de motivos producirá las mayores ganancias de rendimiento.
2. Expresividad Temporal (Sección 6): Los autores proporcionan una ubicación teórica de las MP-GNN temporales estándar dentro de una jerarquía temporal-WL anclada al candidato. Demuestran un par específico de flujos donde las características de los motivos distinguen candidatos que el temporal-1-WL colapsa, demostando que el aumento eleva al modelo más allá del primer nivel de esta jerarquía.
3. Rendimiento Empírico (Sección 7): El artículo demuestra que el aumento de motivos eleva consistentemente el rendimiento en tareas heterogéneas (predicción de propiedades de enlaces TGB, clasificación de aristas y clasificación a nivel de grafo) en comparación con fuertes baselines de TGNN. La ganancia es interpretable: es mayor donde el baseline falla al capturar la estructura de corto horizonte (por ejemplo, MOOC) y es insignificante donde el baseline ya captura la estructura relevante.

Resultados Experimentales

El marco fue evaluado en:

• Predicción de Propiedades de Enlaces TGB: A través de cinco baselines (TPNet, HyperEvent, DyGFormer, TNCN, TGN) y tres conjuntos de datos (Wiki, Review, Coin).
  • Resultado: El aumento de motivos elevó el rendimiento en todos los pares baseline-conjunto de datos evaluados. La ganancia más significativa se observó en DyGFormer para el conjunto de datos tgbl-review-v2, donde el Rango Recíproco Medio (MRR) aumentó de 0.224 a 0.413.
  • Observación: Las ganancias estuvieron dentro de una desviación estándar de cero para baselines como TPNet en tgbl-coin-v2, consistente con esos baselines que ya capturan la estructura de corto horizonte relevante para ese conjunto de datos específico.
• Clasificación de Aristas:
  • MOOC: Una tarea de clasificación binaria para predecir la deserción estudiantil. Un codificador GraphSAGE vanilla logró un PR-AUC de 0.0164. Añadir el subconjunto de 4 características de conteo de estrellas (A2) elevó esto a 0.1430, y el mapa completo de 13 características alcanzó 0.1659.
  • Bitcoin Alpha/OTC: Las tareas de clasificación de confianza mostraron mejoras modestas pero consistentes (por ejemplo, SAGE PR-AUC de 0.9282 a 0.9667 en Alpha).
• Clasificación a Nivel de Grafo: En generadores temporales sintéticos, el aumento de motivos mejoró la precisión significativamente, elevando notablemente a GAT de un colapso del 16.7% (predicción de clase mayoritaria) al 94.0% sin cambios arquitectónicos.

Ablación y Controles:

• El análisis de exclusión mutua confirmó que ninguna coordenada es uniformemente redundante; diferentes conjuntos de datos dependen de diferentes ejes (por ejemplo, MOOC depende fuertemente de la diversidad de estrellas A2, mientras que Bitcoin Alpha depende de la reciprocidad A1).
• Los controles descartaron que la "capacidad extra" fuera la fuente de las ganancias (las características aleatorias no replicaron la mejora) y confirmaron que la ganancia no es simplemente un proxy de los simples recuentos de actividad de los nodos.

Significancia y Reivindicaciones

El artículo afirma que las firmas de motivos temporales proporcionan un método compacto, interpretable y agnóstico a la arquitectura para inyectar regularidades estructurales de corto horizonte en las TGNN.

• Poder Predictivo: La firma por conjunto de datos a lo largo de los ejes A1/A2/A3 sirve como una herramienta de diagnóstico para predecir dónde será más beneficioso el aumento.
• Fundamentación Teórica: Al situar el aumento en relación con la jerarquía temporal-WL, el artículo aclara por qué las TGNN estándar fallan en ciertas tareas (están limitadas por el temporal-1-WL) y cómo el aumento supera este problema.
• Utilidad Práctica: El método no requiere cambios en la arquitectura del codificador subyacente, solo la concatenación de un vector de características precomputado, lo que lo hace fácilmente desplegable en procesos existentes.

Los autores mantienen una postura modesta, señalando que el radio de la ventana $\Delta$ es un hiperparámetro sensible y que en flujos dispersos donde el flujo triádico es insignificante, el aumento se reduce a un subespacio de menor dimensión con ganancias correspondientemente menores. El marco se presenta como una forma fundamentada de exponer señales estructurales específicas que las vanilla TGNN a menudo no logran exponer a sus evaluadores de aristas.