Resumen Técnico: EntroPath – Ensamblaje de Caminos de Máxima Entropía para el Aprendizaje de Variedades

1. Declaración del Problema

Los conjuntos de datos modernos de alta dimensión, como la transcriptómica de célula única y las trayectorias de dinámica molecular, a menudo se concentran cerca de variedades riemannianas de baja dimensión. Un objetivo central del aprendizaje de variedades es recuperar la geometría intrínseca de estas variedades, específicamente sus distancias geodésicas, en una representación de baja dimensión.

Los enfoques existentes enfrentan limitaciones significativas:

• Métodos de Camino Más Corto (p. ej., Isomap): Estiman las geodésicas mediante caminos únicos de trayectoria corta en un grafo de vecindad. Estos son frágiles; un solo borde de "atajo" entre regiones geodésicamente distantes puede corromper las distancias globales. Además, las garantías de recuperación teórica suelen fallar en variedades no convexas o con ramificaciones.
• Métodos de Vecindad Local (p. ej., t-SNE, UMAP): Se centran en preservar las relaciones locales mediante objetivos probabilísticos. Aunque son efectivos para la visualización, no codifican explícitamente las estructuras geodésicas globales.
• Métodos de Difusión Estándar (p. ej., Diffusion Maps, PHATE): Agregan información sobre ensamblajes de caminos, ofreciendo robustez ante errores de grafo. Sin embargo, típicamente dependen de Caminatas Aleatorias Estándar (SRW) normalizadas por el grado local del nodo. Esto causa que la difusión se desplace hacia regiones densamente muestreadas, comprimiendo ramas y cuellos de botella dispersos, y sesgando las representaciones hacia estados terminales de alta densidad en los datos de trayectoria.

2. Metodología: EntroPath

EntroPath aborda estos problemas construyendo disimilitudes basadas en la Caminata Aleatoria de Máxima Entropía (MERW) y una disimilitud de energía libre derivada de ensamblajes de caminos.

2.1 Caminata Aleatoria de Máxima Entropía (MERW)

A diferencia de la SRW, que normaliza las probabilidades de transición localmente por el grado del nodo ($T_{ij} = A_{ij}/d_i$), la MERW maximiza la entropía de las trayectorias globalmente. La matriz de transición se define como:
$$T_{ij} = \frac{A_{ij}}{\lambda_{\max}} \frac{\psi_j}{\psi_i}$$
donde $A$ es la matriz de afinidad, $\lambda_{\max}$ es el autovalor más grande, y $\psi$ es el correspondiente autovector de Perron-Frobenius.

• Reponderación Global: La MERW incorpora la estructura de grafo global mediante $\psi$. Distribuye la probabilidad uniformemente sobre el ensamblaje de caminos, dejando poca masa en cuellos de botella de bajo grado.
• Estructura de Operador de Schrödinger: El Laplaciano de la MERW ($I-T$) es similar a un operador de Schrödinger discreto $H = \lambda_{\max}I - A = -\Delta + V$, donde $V$ es un potencial inducido por la heterogeneidad del grado ($V_i = \lambda_{\max} - d_i$). Esta estructura es central para las garantías teóricas del método.

2.2 Disimilitud de Energía Libre

EntroPath define la disimilitud entre los nodos $i$ y $j$ no como un único camino más corto, sino como el logaritmo negativo de la suma de los pesos sobre todos los caminos de $k$ pasos (una función de partición).

• Costos de Camino: Los costos de las aristas se definen como logaritmos negativos de las afinidades, $E(u,v) = -\log A_{uv}$.
• Formulación Log-Sum-Exp: La disimilitud es:
  $$D_{ij} = -\log \left( \tilde{A}^k \right)_{ij}$$
  donde $\tilde{A} = A/\lambda_{\max}$. Esto representa una relajación soft-min de la distancia del camino más corto, agregando todo el ensamblaje de $k$ pasos.
• Término de Entropía: La disimilitud incluye un término de entropía ($-\sum p(\gamma) \log p(\gamma)$) que recompensa a los pares conectados por muchos caminos comparables, distinguiéndose de las métricas de camino más corto.
• Simetrización: Para afinidades generales, la disimilitud se simetriza mediante la media geométrica de las probabilidades de transición hacia adelante y hacia atrás: $D_{ij} = -\log \sqrt{T^k_{ij} T^k_{ji}}$. En el caso simétrico (estándar para afinidades gaussianas), esto se simplifica a $-\log (\tilde{A}^k)_{ij}$.

2.3 Regímenes Geométricos y Escalamiento

La profundidad de difusión $k$ interpola entre dos regímenes:

1. Régimen Geodésico (k pequeño): La disimilitud aproxima la geodésica del grafo (camino más corto) mediante la fórmula del núcleo de calor de tiempo corto de Varadhan.
2. Régimen de Mezcla (k grande): La disimilitud converge a una distribución estacionaria dependiente solo del vector de Perron, perdiendo detalles geométricos finos.
   El método selecciona $k$ automáticamente usando la "rodilla" de la entropía de von Neumann del operador MERW, asegurando que el tiempo de difusión sea suficiente para conectar puntos pero no tanto como para sobremezclar.

2.4 Escalabilidad

Para conjuntos de datos grandes, EntroPath emplea:

• Proyección de Hitos (Landmark Projection): Una extensión de tipo Nyström donde los nuevos puntos se proyectan en el embedding de un subconjunto de hitos mediante interpolación de kernel, evitando la recomputación del operador global.
• Kernels Adaptativos: Utiliza anchos de banda adaptativos (basados en distancias de $k$-NN locales) para manejar eficazmente las densidades de muestreo no uniformes.

3. Contribuciones Clave

1. Innovación Algorítmica: Introducción de EntroPath, un método de aprendizaje de variedades basado en MERW y una disimilitud de energía libre derivada de ensamblajes de caminos.
2. Formulación Teórica: Una prueba de que la disimilitud de energía libre simetrizada converge a la distancia geodésica al cuadrado en la variedad subyacente en el límite de tiempo corto (Teorema 5.3). Esto se basa en la estructura de operador de Schrödinger discreto del Laplaciano de la MERW y la fórmula de Varadhan.
3. Conexión con Kernels: Demostración de que el kernel de MERW simetrizado admite una factorización de Gram exacta (Proposición 4.1), conectando EntroPath directamente con los métodos de kernel y los mapas de difusión, a diferencia de muchos métodos de difusión basados en perfiles.
4. Extensiones Escalables: Desarrollo de embedding fuera de muestra basado en hitos y un método de pseudotiempo de potencial de difusión para la inferencia de trayectorias.
5. Protocolo de Evaluación: Una evaluación de dos etapas que separa el nivel de distancia (calidad del kernel) del nivel de embedding (calidad del layout), resaltando un sesgo en la evaluación estándar de geodésicas que favorece a los métodos ligados al grafo $k$-NN específico utilizado para la verdad de campo.

4. Resultados Experimentales

EntroPath fue evaluado en variedades sintéticas (Swiss roll, árboles dispersos) y seis conjuntos de datos biológicos de célula única (p. ej., Paul15, Nestorowa, Root Atlas).

• Variedades Sintéticas:

  • En variedades muestreadas de forma no uniforme y árboles de ramificación dispersos, EntroPath superó consistentemente a los baselines basados en difusión (PHATE, HeatGeo, DTNE) y a los métodos de camino más corto (Isomap) en la recuperación de la geometría geodésica.
  • Logró las correlaciones de Spearman y Pearson más altas con las geodésicas de verdad de campo en las evaluaciones de nivel de distancia.
  • En las evaluaciones de nivel de embedding, EntroPath preservó mejor la estructura global que los métodos locales (UMAP, t-SNE) y mostró una confianza y continuidad superiores en comparación con otros métodos de difusión, particularmente en regiones dispersas donde los métodos basados en SRW "se filtran" a través de cuellos de botella.

• Datos de Célula Única:

  • EntroPath igualó o superó el rendimiento de PHATE, HeatGeo y DTNE en métricas como DEMaP (preservación de la variedad) y confiabilidad (trustworthiness).
  • Demostró una robustez particular en conjuntos de datos con muestreo no uniforme y trayectorias de ramificación bien separadas, donde mantuvo una separación clara entre estados celulares sin suavizarlos en cúmulos densos.
  • En el atlas de raíz de Arabidopsis a gran escala ($1.1 \times 10^5$ células), EntroPath logró una fidelidad geométrica comparable a DTNE en aproximadamente 15 segundos, aprovechando sus estrategias de hitos y kernels adaptativos para evitar el costo computacional de las potencias de grafos densos requeridas por los métodos de $k$-NN estrictos.

5. Significado y Reivindicaciones

El artículo afirma que EntroPath ofrece una solución fundamentada a la tensión entre la normalización de grado local (que sesga la difusión en SRW) y la recuperación de la geodésica global (que es frágil en los métodos de camino más corto).

• Robustez a la Densidad de Muestreo: Al utilizar MERW, EntroPath trata los cuellos de botella de bajo grado como barreras de alta energía en lugar de pasajes fáciles. Esto preserva la separación de las ramas muestreadas de forma dispersa y evita el "colapso" de la geometría global que se observa a menudo en los embeddings de SRW.
• Garantía Teórica: La convergencia a la distancia geodésica al cuadrado proporciona una base geométrica rigurosa, distinguiéndolo de las distancias de difusión heurísticas.
• Utilidad Práctica: El método proporciona un enfoque escalable y de pocos parámetros (usando la selección automática de profundidad) que rinde competitivamente a través de diversos regímenes de datos, desde benchmarks sintéticos hasta complejas trayectorias biológicas.

Los autores señalan limitaciones, específicamente que la selección de profundidad basada en la entropía puede volverse ruidosa en ramas muy cortas, y sugieren trabajos futuros en formulaciones de tiempo continuo y el manejo de afinidades dirigidas (p. ej., para la velocidad de ARN).