Resumen Técnico: Modelado Generativo en Grafos Métricos mediante Transporte Óptimo Neuronal

Planteamiento del Problema

Muchos conjuntos de datos científicos y geométricos, como las redes de carreteras, las estructuras vasculares y los sistemas fluviales, están naturalmente soportados en grafos métricos. Un grafo métrico es un espacio geodésico unidimensional donde las aristas portan longitudes y son tratadas como intervalos continuos. Los enfoques de modelado generativo existentes enfrentan una limitación fundamental: los métodos estándar generan puntos en un espacio euclidiano ambiente, fallando al no asegurar que las muestras permanezcan soportadas en el grafo o respeten su geometría métrica intrínseca.

Por el contrario, los enfoques tradicionales de Transporte Óptimo (OT) para grafos suelen depender de la discretización, aproximando distribuciones continuas con medidas basadas en nodos finitos. Aunque es computacionalmente accesible, este enfoque introduce aproximaciones dependientes de la malla y escala pobremente a medida que se refina la discretización, perdiendo la naturaleza continua del dominio original.

El artículo aborda la necesidad de un marco generativo continuo soportado en grafos que pueda aprovechar estructuras ambientes suaves sin sacrificar la fidelidad geométrica del grafo métrico.

Metodología

Los autores proponen un marco de modelado generativo profundo que incrusta el grafo métrico en un espacio ambiente suave, resuelve un problema de OT entrópico allí y proyecta las muestras de vuelta al grafo. El proceso consta de tres etapas principales:

1. Incrustación (Embedding): El grafo métrico $\Gamma$ se incrusta en una variedad ambiente suave $M_\Psi$ mediante una aplicación $\Psi$. El artículo investiga dos incrustaciones específicas:

   • Realización Euclídea Extrínseca ($\iota$): Mapea el grafo a $\mathbb{R}^m$ (por ejemplo, coordenadas planas de una red de carreteras).
   • Incrustación Intrínseca de Abel–Jacobi Tropical ($\Phi_p$): Mapea el grafo en su toro de Jacobiano Tropical $J(\Gamma)$. Esta incrustación depende únicamente de las longitudes de las aristas y la estructura de ciclos, proporcionando una geometría intrínseca independiente de un dibujo euclidiano específico.

2. Transporte Óptimo Entrópico Neuronal:

   • Las medidas de origen ($P_\Gamma$) y destino ($Q_\Gamma$) son empujadas hacia adelante al espacio ambiente ($P_\Psi, Q_\Psi$).
   • Se resuelve un problema de Kantorovich entrópico entre estas medidas incrustadas utilizando una parametrización semidual neuronal.
   • A diferencia de las formulaciones de Monge basadas en mapas, este enfoque aprende un acoplamiento (plan). El potencial del lado del destino está parametrizado por una red neuronal $g_\theta$.
   • Para generar salidas continuas en lugar de muestras restringidas a átomos del destino, la ley condicional aprendida se suaviza utilizando el núcleo de calor ambiente (ambient heat kernel). Esto produce muestras en el espacio ambiente que pueden no caer exactamente sobre el grafo incrustado.

3. Recuperación (Proyección–Retroceso):

   • Dado que las muestras suavizadas por el núcleo de calor pueden caer fuera del grafo incrustado, se realiza una proyección al punto más cercano sobre el grafo incrustado $\Psi(\Gamma)$.
   • Posteriormente, se aplica la incrustación inversa $\Psi^{-1}$ para mapear el punto proyectado de vuelta al grafo métrico original $\Gamma$.
   • El generador final se construye como $\rho_\Gamma^\Psi = \Psi^{-1} \circ \text{proj}_{\Psi(\Gamma)}$, asegurando que todas las muestras generadas estén estrictamente soportadas en el grafo original.

Contribuciones Clave

1. Primer Marco Generativo Profundo para Grafos Métricos: El artículo introduce, según los autores, el primer modelo generativo profundo para distribuciones de probabilidad continuamente soportadas en grafos métricos compactos.
2. Geometrías de Incrustación Duales: El marco se desarrolla para dos geometrías de transporte distintas:
   • Una realización euclídea extrínseca.
   • La incrustación intrínseca de Abel–Jacobi tropical en el toro de Jacobiano.
3. Convergencia Teórica: Los autores demuestran que, en el límite conjunto de un aumento de la expresividad neuronal y un núcleo de calor evanescente, el generador de proyección–retroceso suavizado por calor aprendido converge débilmente a un acoplamiento de transporte válido entre las medidas del grafo original. Esto garantiza que, a pesar de aprender en un espacio ambiente, el objeto límite es un acoplamiento legítimo en el grafo.
4. Gestión de Puentes (Bridges): El método incluye una aumentación canónica (añadir aristas paralelas virtuales) para manejar los puentes en el grafo, asegurando que el mapa de Abel–Jacobi tropical sea inyectivo y que el grafo pueda recuperarse de su imagen.

Resultados Experimentales

El método fue evaluado a través de benchmarks sintéticos y datos del mundo real:

• Benchmarks Sintéticos: Probado en grafos tipo theta, rueda (wheel), rejilla (grid) y pequeñas redes de carreteras. Las variantes de OT neuronal (tanto Tropical como Euclídea) redujeron consistentemente el error (en términos de distancia de Wasserstein intrínseca del grafo $W_1^\Gamma, W_2^\Gamma$ y errores de densidad/CDF $L_1$) en comparación con líneas base heurísticas basadas en OT de grafos discretos (interpolación de nodos y empuje hacia adelante ambiente). Las dos geometrías de incrustación funcionaron de manera comparable, lo que sugiere que la principal ganancia proviene de la regla de transporte entrópico amortizada más que de una ventaja específica de la incrustación.
• Escalabilidad: El enfoque neuronal escala favorablemente con el tamaño del soporte. A diferencia de los métodos de OT de grafos explícitos por pares que requieren evaluar distancias de camino corto intrínsecas en grandes pares de soporte, el método neuronal entrena sobre minibatches y aplica la regla aprendida mediante inferencia por lotes (batches).
• Aplicación en el Mundo Real: El marco se aplicó a un millón de ubicaciones de recogida de Uber en Manhattan, Nueva York.
  • La tarea consistió en la generación de densidad espacial soportada en grafos (aprender a generar recogidas desde una fuente de carretera uniforme).
  • Las líneas base de OT de grafos densos eran inviables a esta escala debido a restricciones de memoria ($10^{12}$ costos por pares).
  • El modelo Euclídeo Neuronal (Gromov) logró generar muestras que recuperaron la estructura dominante de las recogidas en el grafo de carreteras de Manhattan, superando a las líneas base heurísticas entrenadas en un subconjunto subsampado (16,384 puntos).

Significado y Reivindicaciones

El artículo afirma proporcionar una solución fundamentada para el modelado generativo en grafos métricos que evita los problemas de la discretización. Al resolver el problema de transporte en un espacio ambiente suave y recuperar muestras soportadas en el grafo mediante proyección, el método retiene la geometría continua del dominio.

Los autores enfatizan que su enfoque se basa en planes (acoplamientos) en lugar de mapas, lo que permite el manejo de medidas singulares en el grafo sin suavizarlas en densidades ambientes. La garantía teórica de convergencia débil a un acoplamiento válido asegura que el método no es meramente una heurística, sino que posee un fundamento riguroso en la teoría del transporte óptimo.

El trabajo demuestra que el OT neuronal puede adaptarse a dominios geométricos no euclídeos y unidimensionales, ofreciendo una alternativa escalable al OT de grafos discretos para aplicaciones que van desde la movilidad urbana hasta las redes biológicas. Los autores señalan limitaciones, incluyendo la naturaleza asintótica de la prueba de convergencia (sin tasas de muestra finita) y el enfoque actual en la generación no condicionada en lugar de la previsión temporal o condicionada por covariables.