EmbedOR: Provable Cluster-Preserving Visualizations with Curvature-Based Stochastic Neighbor Embeddings

Resumen Técnico de EmbedOR: Visualizaciones de Agrupamiento Probables con Incrustaciones de Vecinos Estocásticos Basadas en la Curvatura

Declaración del Problema

Los algoritmos de Incrustación de Vecinos Estocásticos (SNE), particularmente t-SNE y UMAP, se utilizan ampliamente para visualizar datos de alta dimensión. Sin embargo, sufren limitaciones teóricas y prácticas significativas con respecto a la preservación de la geometría. Específicamente, estos métodos suelen fallar al recuperar la geometría subyacente de datos de alta dimensión ruidosos mediante:

1. El fallo en la identificación de clústeres en datos que son bien agrupables.
2. La introducción de fragmentación, donde los componentes conectados de la variedad (manifold) subyacente de los datos son espuriosamente separados en la visualización.

Las garantías teóricas existentes para t-SNE están restringidas a supuestos muy estrictos sobre los datos (por ejemplo, clústeres esféricos y bien separados), y no existen resultados teóricos significativos para UMAP. Además, los estudios empíricos muestran que las implementaciones estándar a menudo violan estos supuestos, lo que conduce a visualizaciones subóptimas.

Metodología

Los autores proponen EmbedOR, un nuevo algoritmo SNE que integra la Curvatura de Ollivier-Ricci (ORC) para construir una métrica de distancia que potencia los clústeres. La metodología procede en dos etapas:

1. Aprendizaje de Métrica Basado en la Curvatura ($\Delta_E$):

   • El algoritmo construye un grafo de vecinos más cercanos a partir de los datos.
   • Calcula la ORC para cada arista en el grafo. La ORC cuantifica la conectividad local; la curvatura positiva indica aristas dentro de una comunidad altamente conectada, mientras que la curvatura negativa indica "cuellos de botella" o aristas que unen clústeres disjuntos.
   • Se define una función de energía $E(\kappa; p)$ basada en la curvatura $\kappa$. Esta función asigna una alta "energía" (penalización) a las aristas con curvatura negativa y una baja energía a las aristas con curvatura positiva.
   • Se calcula una nueva métrica de distancia de pares, $\Delta_E$, como la distancia de camino más corto en el grafo ponderado, donde los pesos de las aristas son el producto de la distancia euclidiana y la función de energía basada en la curvatura. Esta métrica fomenta que los caminos atraviesen aristas de curvatura positiva (dentro de los clústeres) y eviten las aristas de curvatura negativa (entre clústeres).

2. Incrustación de Vecinos Estocásticos Personalizada:

   • EmbedOR utiliza un marco SNE personalizado que combina elementos de t-SNE y UMAP.
   • Afinidades de alta dimensión ($p_{ij}$): A diferencia de t-SNE estándar que utiliza la distancia euclidiana, EmbedOR utiliza la métrica $\Delta_E$ para calcular las afinidades.
   • Optimización: El algoritmo minimiza una pérdida de "entropía cruzada difusa" entre las afinidades de alta dimensión y las afinidades de baja dimensión (modeladas por una distribución t de Student). La optimización utiliza el descenso de gradiente estocástico (SGD), aprovechando la eficiencia computacional de UMAP (evitando la renormalización de las afinidades de baja dimensión) mientras retiene el cálculo de similitud basado en la perplejidad de t-SNE.

Contribuciones Clave

1. Extensión Teórica: Los autores demuestran que la métrica de distancia de EmbedOR extiende los resultados de consistencia teórica de t-SNE (previamente limitados a datos esféricos y bien separados) a una clase mucho más amplia de conjuntos de datos. Específicamente, muestran que bajo un modelo de variedad ruidosa:
   • Las distancias intra-clúster bajo $\Delta_E$ convergen a la distancia geodésica de la variedad.
   • Las distancias inter-clúster están limitadas inferiormente por un valor que aumenta con el parámetro de repulsión $p$.
   • Consecuentemente, para un $p$ suficientemente grande, los datos satisfacen las condiciones requeridas para que t-SNE produzca una visualización que preserve los clústeres.
2. Innovación Algorítmica: La propuesta de EmbedOR, que utiliza la curvatura de grafo discreta para crear una métrica de distancia que enfatiza la estructura de clúster subyacente sin introducir fragmentación.
3. Herramienta de Diagnóstico: La demostración de que la métrica de EmbedOR puede utilizarse como una herramienta post-hoc para anotar visualizaciones existentes. Al visualizar las aristas con distancias $\Delta_E$ cortas, los usuarios pueden identificar la fragmentación (donde los puntos cercanos en $\Delta_E$ están lejos en la incrustación), proporcionando información sobre la geometría subyacente.

Resultados Experimentales

Los autores evaluaron EmbedOR en conjuntos de datos sintéticos y del mundo real (incluyendo MNIST, Fashion-MNIST y varios conjuntos de datos de secuenciación de ARN de célula única) frente a líneas base como t-SNE, UMAP, PHATE, Isomap y Aprendizaje de Autovalores Laplaciano.

• Datos Sintéticos: EmbedOR demostró consistentemente un rendimiento superior o igual al mejor en la separación de componentes conectados subyacentes mientras evitaba la fragmentación de caminos continuos. Mientras que UMAP a menudo introducía fragmentación y t-SNE fallaba en desenrollar estructuras como el Swiss Roll, EmbedOR mantuvo la integridad topológica.
• Datos Reales (scRNA-seq): En conjuntos de datos de trayectoria de desarrollo y tipos celulares, EmbedOR preservó mejor la continuidad de las trayectorias y la separación de los tipos celulares en comparación con UMAP y t-SNE.
• Análisis de Fragmentación: El análisis cuantitativo utilizando correlaciones de Spearman y longitudes de arista estandarizadas (z-scored) confirmó que EmbedOR expande mínimamente las distancias entre puntos considerados cercanos por la métrica $\Delta_E$. En contraste, se demostró que UMAP y t-SNE expanden significativamente estas distancias, indicando fragmentación.
• Utilidad de la Métrica: Los experimentos confirmaron que las aristas de corta distancia $\Delta_E$ son significativamente más propensas a conectar puntos dentro del mismo clúster (o tipo celular) de la verdad fundamental que las aristas en un grafo k-NN estándar, validando la capacidad de la métrica para detectar la fragmentación en otras incrustaciones.

Significado y Reivindicaciones

El artículo afirma que EmbedOR logra un "equilibrio delicado" entre resaltar la estructura de los clústeres y preservar la continuidad de las variedades de los datos, una cualidad no observada en los métodos de línea base probados.

• Significado Teórico: El trabajo proporciona la primera justificación teórica para el uso de métricas basadas en la curvatura para relajar los estrictos supuestos requeridos para la convergencia de SNE, ampliando así la aplicabilidad de la preservación de clústeres demostrable.
• Significado Práctico: EmbedOR ofrece una alternativa robusta para visualizar datos de alta dimensión ruidosos donde mantener la integridad de los componentes conectados es crítico (por ejemplo, en genómica de célula única).
• Valor Diagnóstico: Los autores enfatizan que la métrica de EmbedOR sirve un doble propósito: actúa como la métrica de distancia central para el algoritmo y como una herramienta de diagnóstico para identificar e interpretar la fragmentación en las visualizaciones generadas por otros métodos.

Los autores se mantienen modestos respecto al alcance teórico, señalando que sus resultados de convergencia dependen de instancias específicas de t-SNE y que su algoritmo personalizado mezcla elementos de UMAP y t-SNE. Sin embargo, argumentan que los conocimientos teóricos respecto a la métrica $\Delta_E$ proporcionan una fuerte motivación para su efectividad en la práctica.