A discrete Benamou-Brenier formulation of Optimal Transport on graphs

A continuación presento un resumen técnico detallado del artículo "A discrete Benamou-Brenier formulation of Optimal Transport on graphs" (Una formulación discreta de Benamou-Brenier de Transporte Óptimo en grafos) de Kieran Morris y Oliver Johnson.

1. Planteamiento del Problema

El Transporte Óptimo (OT) busca encontrar la forma más eficiente de transportar una medida de probabilidad $\mu$ a otra $\nu$ minimizando el costo esperado definido por una métrica $d(x,y)$. La formulación clásica de Kantorovich define la distancia de Wasserstein $W_p$ como el infimo sobre acoplamientos.

Sin embargo, la formulación de Benamou-Brenier ofrece una perspectiva dinámica: reparametriza el problema como una minimización de energía cinética a lo largo de un flujo continuo en el tiempo, sujeto a una ecuación de transporte (ecuación de continuidad). En el caso continuo ($\mathbb{R}^d$), esto permite caracterizar las geodésicas de velocidad constante.

El problema central abordado en este trabajo es la extensión de la formulación de Benamou-Brenier al dominio discreto de grafos para la distancia $W_1$.

• En grafos, calcular $W_1$ mediante la formulación de Kantorovich es un programa lineal de dimensión $|V|^2$.
• La formulación de Beckmann (estática) reduce esto a $|E|$, pero carece de la estructura temporal dinámica.
• Trabajos previos (Erbar y Maas) propusieron una versión discreta para $W_2$ que induce una estructura Riemanniana, pero no es la distancia $W_2$ real.
• Hillion y Johnson proporcionaron condiciones para una formulación discreta de Benamou-Brenier para $W_1$ en $\mathbb{Z}$, pero faltaba una generalización a grafos arbitrarios y la clasificación completa de las geodésicas.

2. Metodología y Marco Teórico

Los autores proponen una ecuación de transporte discreta que generaliza la ecuación de continuidad a grafos dirigidos.

A. Ecuación de Transporte Discreta

En lugar de una sola distribución $f_t$ y un campo de velocidad $v_t$, introducen una tríada $(f, v, g)$:

• $f(t)$: Distribución de probabilidad en los nodos (vértices) $V$.
• $v(t)$: Función de "velocidad" definida en las aristas $E$.
• $g(t)$: Distribución de probabilidad definida en las aristas $E$ (que actúa como el peso sobre el cual se promedia la velocidad).

La ecuación de transporte se define utilizando la matriz de incidencia $\Omega$ del grafo:
$$\partial_t f = \Omega \cdot (v \cdot g)$$
Donde $(v \cdot g)$ es el producto componente a componente en las aristas. Esto generaliza la ecuación $\partial_t f + \nabla \cdot (fv) = 0$ del caso continuo, donde el término de flujo se distribuye entre la velocidad y la medida en las aristas.

B. Funcional de Energía

Definen un funcional de costo $I_q(v, g)$ para $q \geq 1$:
$$I_q(v, g) = \left( \int_0^1 \sum_{k \in E} g_k(t) |v_k(t)|^q dt \right)^{1/q}$$
El objetivo es minimizar este funcional sujeto a la restricción de la ecuación de transporte y a los estados inicial y final $f(0)$ y $f(1)$.

C. Estrategia de Prueba

1. Caso de Árboles: Utilizan la estructura de árbol para definir "colas" (tails) de las distribuciones. Demuestran que en un árbol, la distancia $W_1$ tiene una forma cerrada basada en la suma de las diferencias de las distribuciones de cola. Invierten la ecuación de transporte para encontrar soluciones explícitas de velocidad constante.
2. Caso de Grafos Generales: Dado que la matriz de incidencia $\Omega$ no es invertible en grafos con ciclos (su núcleo es el espacio de ciclos), no existe una solución única para $(v, g)$ dada $f$.
   • Introducen una formulación reducida donde se busca minimizar sobre pares $(v, g)$ tales que la integral del flujo $\int_0^1 \Omega(vg) dt$ iguale a $f(1) - f(0)$.
   • Demuestran que cualquier solución puede transformarse en una solución de velocidad constante (donde $|v_k|$ es constante en el tiempo y en las aristas) que no aumenta el costo.

3. Contribuciones Clave

1. Formulación de Benamou-Brenier Discreta para $W_1$:
   Establecen que para cualquier grafo conexo $G$ y $q \geq 1$, la distancia de Wasserstein-1 se puede expresar exactamente como:
   $$W_1(f(0), f(1)) = \inf_{f, v, g} \left\{ I_q(v, g) : \partial_t f = \Omega \cdot (vg) \right\}$$
   Esto resuelve el problema abierto de dar una interpretación dinámica de Benamou-Brenier para $W_1$ en grafos.

2. Caracterización de Geodésicas de Velocidad Constante:
   Demuestran que el ínfimo se alcanza mediante geodésicas de velocidad constante. Proporcionan una caracterización completa: una trayectoria $f(t)$ es una geodésica de velocidad constante si y solo si existe un par $(v, g)$ que minimiza el funcional y satisface $|v_k| = c$ (constante) para todo $k$ y $t$.

3. Interpolación Convexa vs. Geodésicas Exóticas:
   Muestran que la interpolación lineal simple $f(t) = (1-t)f(0) + tf(1)$ es siempre una geodésica de velocidad constante (Corolario 1). Sin embargo, no es la única.

   • Presentan ejemplos (como distribuciones Binomiales y Poisson) donde existen múltiples geodésicas de velocidad constante distintas a la interpolación lineal convexa.
   • Esto revela una riqueza estructural en el espacio de Wasserstein discreto que no existe en el continuo euclidiano para ciertas métricas.

4. Generalización de Resultados Previos:
   Extienden el trabajo de Hillion y Johnson (limitado a $\mathbb{Z}$) a árboles y grafos generales, unificando la visión de Beckmann (estática) con la dinámica de Benamou-Brenier.

4. Resultados Principales

• Teorema 1 (Árboles): En un árbol, $W_1$ se puede calcular exactamente mediante el funcional de Benamou-Brenier, y las soluciones minimizadoras se pueden construir explícitamente usando distribuciones de cola.
• Teorema 2 (Grafos Generales): La igualdad $W_1 = V_q$ (donde $V_q$ es el valor del problema de minimización dinámica) se mantiene para cualquier grafo conexo. La prueba utiliza la conexión con la formulación de Beckmann y la existencia de un árbol generador que preserva la distancia $W_1$.
• Proposición 4: Establece la equivalencia entre las soluciones minimizadoras del funcional dinámico y las geodésicas de velocidad constante.
• Ejemplos Numéricos/Analíticos:
  • Para distribuciones Binomiales $Bin(n, p(t))$, la interpolación lineal de $p(t)$ genera una geodésica de velocidad constante.
  • Para distribuciones Poisson, ocurre lo mismo con el parámetro $\lambda(t)$.
  • En un ciclo de 4 nodos, se demuestra cómo la libertad en el núcleo de la matriz de incidencia (el ciclo) permite múltiples configuraciones de flujo $(v, g)$ que alcanzan el mismo costo mínimo.

5. Significado e Impacto

Este trabajo es fundamental para el campo del Transporte Óptimo en redes y grafos:

1. Puente Teórico: Cierra la brecha entre las formulaciones estáticas (Beckmann) y dinámicas (Benamou-Brenier) en dominios discretos, proporcionando una base teórica sólida para definir flujos óptimos en tiempo continuo sobre estructuras discretas.
2. Aplicaciones en Aprendizaje Automático: La distancia de Wasserstein es una función de pérdida popular en ML. Una formulación dinámica permite el uso de Flujos de Gradiente de Wasserstein en grafos, lo cual es crucial para problemas de difusión, propagación de información y aprendizaje en redes neuronales gráficas.
3. Comprensión de la Geometría Discreta: La demostración de que existen múltiples geodésicas de velocidad constante (incluyendo la interpolación convexa y otras "exóticas") desafía la intuición basada en el espacio continuo y sugiere que el espacio de medidas sobre grafos tiene una geometría más compleja y rica de lo que se pensaba.
4. Herramientas Computacionales: Al reducir el problema a una optimización sobre aristas (dimensión $|E|$) en lugar de pares de nodos ($|V|^2$), y al proporcionar soluciones de velocidad constante, se abren vías para algoritmos más eficientes para calcular distancias de transporte y trayectorias óptimas en redes grandes.

En resumen, el artículo establece que la dinámica de Benamou-Brenier es válida y útil para $W_1$ en grafos, caracterizando completamente las trayectorias óptimas y revelando la existencia de múltiples caminos de velocidad constante entre distribuciones discretas.