Temporal Hyperbolic Graph Representation Learning for Scale-Free Internet Routing and Delay Prediction

Resumen Técnico: HERMIT – Aprendizaje de Representación de Grafos Hiperbólicos Temporales para Enrutamiento de Internet Libre de Escala y Predicción de Retardo

Enunciado del Problema
Predecir con precisión el Tiempo de Ida y Vuelta (RTT) de Internet es esencial para la optimización del enrutamiento, la Calidad de Servicio (QoS) y la ingeniería de tráfico. Sin embargo, la predicción de RTT enfrenta tres desafíos principales:

1. Distribuciones de Cola Pesada: Los datos de RTT exhiben una variabilidad extrema, que va desde fracciones de milisegundo hasta varios segundos, lo que hace que los modelos de regresión tradicionales basados en Error Cuadrático Medio (MSE) estén dominados por valores atípicos y degraden el rendimiento en los rangos de latencia comunes.
2. Topología Dinámica: El RTT está influenciado por rutas de enrutamiento en evolución, estados de congestión y cambios en la topología de la red, los cuales son difíciles de capturar con incrustaciones de distancia estáticas o modelos de regresión convencionales.
3. Incompatibilidad Estructural: La mayoría de las Redes Neuronales de Grafos Temporales (TGNN) existentes operan en espacio euclidiano. Esto es inadecuado para los grafos de enrutamiento de Internet, que poseen estructuras jerárquicas y libres de escala. Las incrustaciones euclidianas a menudo requieren dimensiones altas o incurrir en distorsión geométrica para representar estas topologías, mientras que la geometría hiperbólica acomoda naturalmente dichas estructuras con baja distorsión en dimensiones bajas.

Metodología: El Marco HERMIT
Los autores proponen HERMIT (Modelado de RTT consciente de bordes hiperbólico mediante Topología Integrada), un marco híbrido diseñado para realizar conjuntamente la predicción de enlaces y la predicción de RTT. La arquitectura integra una GNN temporal que preserva la variedad hiperbólica con un regresor de Bosque Aleatorio basado en árboles.

• Preprocesamiento de Datos: El modelo utiliza un conjunto de datos de 10 años (2015–2024) del proyecto CAIDA IPv4 Ark. Los registros crudos de traceroute se limpian (reteniendo solo las trazas "completadas"), se podan hasta el 5% superior de nodos por grado para centrarse en la columna vertebral de la red, y se muestrean mediante una estrategia semanal rodante (3 días/semana) para gestionar la carga computacional. Los datos resultantes se estructuran como una secuencia de grafos ponderados diarios con características de borde que incluyen la media de RTT transformada por logaritmo, la desviación estándar del RTT y el peso del enlace.
• Codificador Temporal Hiperbólico: Basándose en el backbone HMPTGN, HERMIT introduce dos mejoras clave:
  1. Características de Borde Conscientes de RTT: Se incorporan características de borde explícitas (media de log-RTT, desviación estándar y peso) para caracterizar estados de enlace de granularidad fina.
  2. Codificador de Borde Aprendible: Una transformación lineal seguida de una activación sigmoidea comprime las características de borde 3D en un peso escalar. Esto actúa como un mecanismo de atención, ponderando adaptativamente los bordes durante el paso de mensajes para enfatizar enlaces críticos y estables.
  3. Preservación de Variedad: El codificador realiza el paso de mensajes directamente sobre la variedad de la bola de Poincaré (curvatura $c=1.0$) utilizando la adición de Möbius y transformaciones lineales de Poincaré, evitando la distorsión geométrica asociada con las proyecciones de espacio tangente utilizadas en modelos como HTGN.
• Tareas de Predicción Conjunta:
  • Predicción de Enlaces: El modelo calcula la distancia cuadrada de Poincaré entre las incrustaciones de nodos y la mapea a probabilidades de existencia de enlaces utilizando una función de activación de Fermi-Dirac.
  • Predicción de RTT: Las incrustaciones de nodos hiperbólicos ($z_u, z_v$) se concatenan con estadísticas históricas de RTT ($f_u, f_v$) para los extremos del borde. Este vector de características combinado se alimenta a un regresor de Bosque Aleatorio para predecir el RTT. El modelo se entrena con valores de RTT transformados por logaritmo y normalizados min-max para manejar colas pesadas, con predicciones inversamente transformadas a la escala de milisegundos para la evaluación.
• Objetivo de Entrenamiento: El modelo se optimiza utilizando una función de pérdida combinada $L = L_{link} + \lambda L_{RTT}$, donde $L_{link}$ es la entropía cruzada binaria y $L_{RTT}$ es el MSE sobre valores normalizados. El hiperparámetro de ponderación $\lambda$ se establece en 10.

Contribuciones Clave

1. Pipeline Reproducible: Un pipeline de preprocesamiento de datos que transforma registros crudos de CAIDA Ark en una secuencia de grafos ponderados diarios con estadísticas de RTT a nivel de borde, abordando inconsistencias de datos comunes en las mediciones de traceroute.
2. Arquitectura Híbrida (HERMIT): Un marco novedoso que combina una GNN temporal hiperbólica con un regresor de Bosque Aleatorio. Se evalúa en un conjunto de datos masivo y del mundo real que abarca una década.
3. Mejoras de Rendimiento:
   • Predicción de RTT: HERMIT logra una mejora del 6% en RMSE en comparación con una línea base fuerte de Bosque Aleatorio que utiliza solo estadísticas históricas. Específicamente, mejora el RMSE en un 6.4% en enlaces existentes y en un 2.3% en nuevos enlaces que aparecen.
   • Predicción de Enlaces: Al incorporar características de borde explícitas y un codificador de borde aprendible, HERMIT supera a las líneas base anteriores de TGNN hiperbólicas (HMPTGN y HTGN), logrando puntuaciones AUC y AP superiores a 0.99 tanto en enlaces existentes como nuevos.
4. Escalabilidad: El enfoque demuestra que las incrustaciones hiperbólicas de 16 dimensiones pueden codificar eficientemente estructuras de enrutamiento jerárquicas, ofreciendo una solución escalable para redes a gran escala.

Resultados y Significado
El artículo afirma que HERMIT proporciona una solución robusta y escalable para la predicción de RTT bajo condiciones de latencia de red del mundo real con colas pesadas. Los resultados experimentales en el conjunto de datos de CAIDA demuestran que:

• Manejo de Colas Pesadas: El diseño híbrido mitiga eficazmente los errores grandes en muestras de cola pesada, superando a los modelos que dependen exclusivamente de estadísticas históricas o incrustaciones euclidianas.
• Generalización: El modelo muestra una fuerte generalización a conexiones previamente no vistas (nuevos enlaces), lo que sugiere que las representaciones temporales hiperbólicas aprendidas capturan estructuras jerárquicas latentes que ayudan a inferir conexiones de red emergentes.
• Sinergia: La combinación de la organización de red a nivel macro (capturada por el codificador hiperbólico) y las interacciones de características a nivel micro (explotadas por el Bosque Aleatorio) produce predicciones más precisas y robustas que cualquiera de los enfoques por separado.

Los autores concluyen que incorporar el modelado de bordes consciente de RTT en grafos temporales hiperbólicos mejora significativamente tanto la predicción de enlaces como la de latencia, ofreciendo una vía práctica para la ingeniería de tráfico consciente de la latencia y el monitoreo proactivo del rendimiento.