Resumen Técnico: Transporte de Operadores de Distancia Convexos (CDOT)

Planteamiento del Problema

El Transporte Óptimo (OT) proporciona un marco fundamental para comparar medidas de probabilidad cuantificando el coste mínimo para transportar masa; sin embargo, el OT clásico basado en la distancia de Wasserstein requiere que las distribuciones de datos residan en el mismo espacio, una restricción que limita su aplicación a dominios heterogéneos. Los marcos de Gromov–Wasserstein (GW) y Fused Gromov–Wasserstein (FGW) abordan esto comparando distribuciones a través de sus espacios métricos-medida (mm) intrínsecos, alineando la información estructural sin requerir un coste entre dominios.

A pesar de su versatilidad, las formulaciones de (F)GW sufren de una limitación fundamental: la no convexidad. Esto surge porque el coste de GW implica un producto tensorial del acoplamiento ($\pi \otimes \pi$), lo que conduce a comparaciones de distancias por pares que crean un paisaje de optimización no convexo. En consecuencia, los algoritmos de optimización estándar suelen converger solo a puntos estacionarios locales, y las soluciones resultantes pueden carecer de garantías de optimalidad global. Además, las relaxaciones convexas existentes a menudo no logran preservar la propiedad de pseudométrica en el espacio de espacios mm con atributos o requieren parámetros de suavizado adicionales (por ejemplo, regularización entrópica) que alteran la geometría del problema.

Metodología: Transporte de Operadores de Distancia Convexos (CDOT)

Los autores proponen el Transporte de Operadores de Distancia Convexos (CDOT), el primer marco de transporte óptimo convexo diseñado para alinear espacios mm heterogéneos preservando tanto la correspondencia de características como la estructura geométrica intrínseca.

Formulación Central

CDOT eleva la estructura geométrica de cada espacio y el plan de transporte a operadores lineales que actúan sobre espacios $L^2$. En lugar de comparar distancias por pares directamente, CDOT alinea estructuras de distancia agregadas mediante la composición de operadores.

Dados dos espacios mm compactos con atributos $\mathcal{X} = (X, d_X, P_X, f_X)$ y $\mathcal{Y} = (Y, d_Y, P_Y, f_Y)$, y un plan de transporte $\pi \in \Pi(P_X, P_Y)$, el objetivo de CDOT equilibra dos componentes:

1. Alineación de Características: $F(\pi) = \mathbb{E}_\pi[\|f_X(X) - f_Y(Y)\|_2^2]$, que fomenta la similitud elemento a elemento entre las características.
2. Regularización Estructural: $R(\pi) = \|D_{P_X} T_\pi - T_\pi D_{P_Y}\|_{HS}^2$, que penaliza la discrepancia estructural.

Aquí:

• $D_{P_X}$ y $D_{P_Y}$ son operadores de distancia definidos como operadores integrales en $L^2(X, P_X)$ y $L^2(Y, P_Y)$, que representan el análogo continuo de las matrices de distancia por pares.
• $T_\pi$ es el operador de esperanza condicional asociado con el acoplamiento $\pi$, que mapea funciones de $L^2(Y, P_Y)$ a $L^2(X, P_X)$.
• $\|\cdot\|_{HS}$ denota la norma de Hilbert–Schmidt.

El problema CDOT se formula como:
$$\inf_{\pi \in \Pi(P_X, P_Y)} \left[ (1-\alpha)F(\pi) + \frac{\alpha}{2}R(\pi) \right]$$

Fundamentos Teóricos

• Convexidad: Los autores demuestran que el objetivo de CDOT es convexo. Esto se logra porque el término estructural $R(\pi)$ depende linealmente del operador de esperanza condicional $T_\pi$ (que es afín en $\pi$) y la norma de Hilbert–Schmidt al cuadrado es convexa. Esto contrasta con GW, donde la dependencia cuadrática de $\pi$ crea no convexidad.
• Pseudométrica: Se demuestra que la discrepancia CDOT resultante, definida como la raíz cuadrada del valor mínimo del objetivo, es una pseudométrica válida en el espacio de espacios mm compactos con atributos.
• Brecha de Dispersión (Dispersion Gap): El artículo introduce un análisis de la "brecha de dispersión" para elucidar formalmente la relación entre CDOT y GW. Se muestra que el objetivo de GW puede descomponerse en el objetivo de CDOT más una penalización de dispersión $V(\pi)$, que cuantifica la incertidumbre espacial del acoplamiento. La no convexidad de GW surge de este término de dispersión, que favorece acoplamientos deterministas (concentrados). CDOT logra la convexidad aislando el componente estructural y descartando esta penalización.

Optimización

En el régimen de muestras finitas, el problema CDOT se reduce a un programa cuadrático convexo sobre un politopo de transporte. Los autores lo resuelven utilizando el algoritmo de Frank–Wolfe (FW), elegido por su naturaleza libre de proyecciones. Proponen una variante de "gradiente perezoso" (lazy gradient) que aprovecha la estructura cuadrática para actualizar gradientes de manera eficiente, reduciendo la sobrecarga computacional por iteración de tiempo cúbico a cuadrático respecto a las operaciones matriciales, aunque la complejidad general sigue dominada por el oráculo de minimización lineal ($O(n^3)$).

Contribuciones Clave

1. Primer Marco de OT con Conciencia Geométrica Convexo: CDOT es el primer marco que proporciona una formulación convexa para alinear espacios mm heterogéneos que recupera explícitamente un plan de transporte óptimo, a diferencia de los métodos basados en segmentación (slicing) que solo estiman la discrepancia.
2. Garantías Teóricas:
   • Existencia y Convexidad: Se demuestra la existencia de un acoplamiento óptimo y la convexidad del objetivo sin requerir regularización entrópica.
   • Propiedad de Pseudométrica: Se establece que la discrepancia CDOT es una pseudométrica válida.
   • Consistencia de Riesgo: Se derivan límites de riesgo no asintóticos descompuestos en errores de optimización y estadísticos, demostando que el estimador es consistente en riesgo bajo un algoritmo de Frank–Wolfe de convergencia global.
3. Perspectiva Geométrica: El análisis de la "brecha de dispersión" explica formalmente la fuente de no convexidad en GW y demuestra cómo CDOT filtra el término de dispersión para lograr un paisaje convexo.
4. Rendimiento Empírico: Demostró un rendimiento superior a los métodos existentes (FGW, Entropic FGW, IsoRank, Spectral Matching, COPT) en nubes de puntos sintéticas, conectomas cerebrales (OASIS-3) y benchmarks de clasificación de grafos (TUDataset).

Resultados Experimentales

• Datos Sintéticos: En nubes de puntos agrupadas en 2D, CDOT alcanzó consistentemente el error cuadrático medio (MSE) más bajo en diversas variaciones de tamaño de muestra, mostrando una convergencia estable. En contraste, el EFGW (Entropic FGW) exhibió una alta sensibilidad al parámetro de regularización $\epsilon$, fallando a menudo en igualar la precisión de CDOT o quedando atrapado en óptimos locales cuando $\epsilon$ era pequeño.
• Conectomas Cerebrales (OASIS-3): En redes cerebrales estructurales, CDOT superó significativamente a FGW cuando se utilizó la distancia de difusión (una métrica global robusta), logrando un 61.36% de precisión de emparejamiento frente al 18.53% de FGW. Los autores atribuyen esto a la capacidad de CDOT para alinear perfiles geométricos agregados incluso cuando los contrastes por pares se suavizan por la difusión, mientras que el objetivo no convexo de GW pierde poder discriminativo en tales paisajes planos. Bajo la distancia geodésica, FGW funcionó ligeramente mejor, resaltando el compromiso entre el alineamiento por pares rígido y el alineamiento global robusto.
• Clasificación de Grafos: En los benchmarks de TUDataset, CDOT superó consistentemente a los métodos de referencia (FGW, GW, COPT) en precisión de clasificación, particularmente en conjuntos de datos ricos en información de características (ej. MUTAG, ENZYMES). Notablemente, CDOT mantuvo el mejor rendimiento incluso en el conjunto de datos IMDB-BINARY (sin características de nodos), sugiriendo que la geometría basada en operadores de CDOT captura las distinciones topológicas de manera más efectiva que los enfoques estándar de GW.

Significado y Reivindicaciones

El artículo afirma que CDOT ofrece una alternativa robusta y fiable a los métodos de OT no convexos existentes para datos estructurados. Al asegurar un paisaje de optimización convexo, CDOT garantiza la convergencia a un óptimo global sin la necesidad de un ajuste de hiperparámetros (como la regularización entrópica) que puede desestabilizar las soluciones. El marco es particularmente significativo para aplicaciones que involucran dominios heterogéneos donde las estructuras geométricas intrínsecas deben preservarse, como el análisis de redes cerebrales y la clasificación de grafos.

Los autores señalan modestamente dos limitaciones:

1. CDOT está diseñado para el alineamiento a nivel de operador en lugar de un emparejamiento estricto uno a uno; una discrepancia cero no implica necesariamente una isometría exacta que preserve la medida.
2. Aunque es convexo, la implementación actual depende de iteraciones de Frank–Wolfe dominadas por subproblemas de OT, lo que lo hace más adecuado para tamaños de problema moderados en lugar de entornos de escala muy grande.

Las direcciones futuras sugeridas por los autores incluyen el desarrollo de marcos de inferencia estadística (por ejemplo, pruebas de hipótesis para el isomorfismo) basados en la discrepancia CDOT y la integración del objetivo de CDOT como una capa diferenciable en redes neuronales profundas para aprender conjuntamente las métricas de tierra óptimas.