ScaleMAP: Preserving Local Density and Neighborhood Structure in Low-Dimensional Embeddings

Resumen Técnico: ScaleMAP

Planteamiento del Problema
Los métodos de reducción de dimensionalidad (DR) no lineales, particularmente UMAP, PaCMAP y t-SNE, son herramientas estándar para el análisis exploratorio de datos de alta dimensión. Estos métodos construyen grafos de $k$-vecinos más cercanos ($k$NN) aproximados y normalizan las distancias locales utilizando anchos de banda adaptativos para manejar las variaciones en la densidad local. Si bien esta normalización asegura la robustez ante las variaciones de densidad, inadvertidamente borra la escala absoluta de los vecindarios. En consecuencia, estos métodos no logran preservar los tamaños relativos de los cúmulos y suprimen estructuras dispersas, tales como puentes entre tipos celulares en transición, picos espectrales estrechos en imágenes hiperespectrales o variaciones de densidad que abarcan muchos órdenes de magnitud (por ejemplo, en la citometría de flujo).

Los intentos existentes para corregir esto, como DensMAP, introducen un término de penalización en la función de pérdida para maximizar la correlación entre las densidades del espacio original y del espacio de incrustación (embedding). Sin embargo, el artículo argumenta que este enfoque crea un objetivo contrapuesto: la penalización de densidad lucha contra las fuerzas de atracción-repulsión inherentes de UMAP. Este conflicto dispersa los puntos lejos de sus verdaderos vecindarios, lo que resulta en una alta fracción de "puntos desconectados" y hace que las regiones dispersas sean difíciles de interpretar.

Metodología
ScaleMAP propone un enfoque diferente: en lugar de añadir un término de pérdida contrapuesto, reintroduce la información de escala a través de un cambio de variables aplicado a la métrica de distancia dentro del objetivo de UMAP existente.

1. Definición del Radio Local: ScaleMAP utiliza el "radio local" ($r_i$), una distancia de raíz cuadrática media ponderada de un punto hacia sus vecinos en el espacio original, como una medida de la escala del vecindario.
2. Distancia Reescalada: En lugar de utilizar la distancia euclidiana al cuadrado $d_{ij}^2 = \|y_i - y_j\|^2$ en la función de pérdida, ScaleMAP define una distancia al cuadrado reescalada:
   $$\tilde{d}_{ij}^2 = \frac{d_{ij}^2}{r_i r_j}$$
   donde $r_i$ y $r_j$ son los radios locales de los dos extremos.
3. Modificación de la Fuerza: Esta sustitución modifica el gradiente de la pérdida de entropía cruzada. Las reglas de actualización tanto para las fuerzas atractivas (vecinos) como para las repulsivas (no vecinos) se escalan por un factor de $1/(r_i r_j)$.
   • Simetría: Crucialmente, el reescalado se aplica de manera simétrica tanto a las fuerzas atractivas como a las repulsivas. Esto preserva el equilibrio local que otorga a UMAP sus propiedades de preservación de vecindarios.
   • Efecto: Los puntos en regiones dispersas (grandes $r_i, r_j$) experimentan fuerzas más débiles por unidad de desplazamiento euclidiano, lo que provoca que la incrustación los disperse. Los puntos en regiones densas permanecen estrechamente agrupados.
4. Normalización: Para manejar las escalas de distancia independientes de los datos originales y de la incrustación, los radios locales se normalizan utilizando el percentil 95 ($P_{95}$) de la distribución de los radios antes de la sustitución.
5. Extensión a PaCMAP: El mismo principio se aplica a PaCMAP (denominado Scale-PaCMAP) mediante la sustitución de la media geométrica de los radios por el producto de las escalas de distancia por punto de PaCMAP ($\sigma_i \sigma_j$).

Contribuciones Clave

1. Formulación Novedosa: La introducción de ScaleMAP, una modificación de UMAP que inyecta información de escala local mediante un cambio de variables en lugar de un término de pérdida adicional.
2. Equilibrio de Rendimiento: Demostración de que ScaleMAP logra una preservación de vecindarios de nivel UMAP y iguala o supera a DensMAP en la preservación de la densidad, con una fracción significativamente menor de puntos dispersos (desconectados).
3. Recuperación de Estructura: Recuperación exitosa de estructuras dispersas que UMAP colapsa (por ejemplo, puentes transcriptómicos) y preservación de estructuras de densidad multiescala (por ejemplo, datos de citometría de flujo que abarcan 17 órdenes de magnitud).
4. Generalizabilidad: Evidencia de que el principio de cambio de variables se generaliza a otros métodos, específicamente a PaCMAP.

Resultados
Los autores evaluaron ScaleMAP en bancos de pruebas estándar (MNIST, Fashion-MNIST, COIL-20, Mammoth) y tres conjuntos de datos científicos (transcriptómica de Tabula Sapiens, imágenes hiperespectrales BCARS y citometría de flujo de médula ósea humana).

• Métricas Cuantitativas:

  • Preservación de la Densidad: ScaleMAP logra una preservación de densidad (ajuste log-log $R^2$) comparable a la de DensMAP en la mayoría de los conjuntos de datos (por ejemplo, $R^2 \approx 0.51$ en Fashion-MNIST frente al $0.58$ de DensMAP). En conjuntos de datos con rangos dinámicos extremos, ScaleMAP supera a DensMAP (por ejemplo, Citometría de Flujo: $R^2 = 0.80$ frente al $0.68$ de DensMAP; Imágenes Hiperespectrales: $R^2 = 0.81$ frente al $0.59$ de DensMAP).
  • Preservación de Vecindarios: ScaleMAP mantiene una recuperación de kNN comparable a la de UMAP (por ejemplo, 14.3% frente al 13.3% de UMAP en Fashion-MNIST) y significativamente mejor que la de DensMAP (7.1%).
  • Puntos Desconectados: ScaleMAP mantiene baja la fracción de puntos desconectados, siendo comparable a la de UMAP (por ejemplo, 0.19% frente al 0.11% de UMAP), mientras que DensMAP exhibe un orden de magnitud más de puntos desconectados (3.48%).
  • Mezcla de Clases: ScaleMAP reduce la mezcla de clases en comparación con ambos modelos de referencia.

• Observaciones Cualitativas:

  • Transcriptómica: ScaleMAP recupera puentes dispersos entre poblaciones celulares (por ejemplo, monocitos-neutrófilos, células B-T) que están colapsados o son invisibles en UMAP.
  • Imágenes Hiperespectrales: Revela picos espectrales dispersos y pequeños cúmulos que UMAP comprime o absorbe en el fondo.
  • Citometría de Flujo: Representa fielmente la estructura multiescala a través de 17 órdenes de magnitud, preservando un "bulbo" denso de células con marcadores negativos que aparece como una característica diminuta en la incrustación, a diferencia de UMAP/DensMAP que carecen de esta fidelidad multiescala.
  • Diagnósticos Sintéticos: En los conjuntos de datos "XOI" y "Bridge", ScaleMAP preserva correctamente los tamaños relativos y las conexiones dispersas, mientras que DensMAP distorsiona las formas y dispersa los puntos.

Significancia y Reivindicaciones
El artículo afirma que ScaleMAP representa una mejora fundamental en la forma en que las incrustaciones que preservan vecindarios manejan la escala. Al tratar el reescalado como un cambio de variables en lugar de un objetivo contrapuesto, ScaleMAP evita el compromiso entre la fidelidad de la densidad y la integridad del vecindario que afecta a DensMAP.

Los autores sostienen que ScaleMAP es el único método probado que no sacrifica un eje de calidad de la incrustación por otro: mantiene la preservación de vecindarios de UMAP, iguala la fidelidad de densidad de DensMAP y mejora la preservación del orden de distancia global (superando a PaCMAP en conjuntos de datos con amplios rangos dinámicos). El artículo concluye que restaurar la escala local es un ingrediente faltante general en las incrustaciones que preservan vecindarios y sugiere ScaleMAP como un método por defecto cuando la representación fiel de la escala es crítica para la visualización. Se señala que el enfoque es computacionalmente eficiente, añadiendo solo un costo de $O(n)$ para el precálculo de los radios, con un tiempo de ejecución total aproximadamente el doble que el de UMAP.