Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph

Resumen Técnico: La Reducción de Dimensionalidad se Encuentra con la Ciencia de Redes

Planteamiento del Problema

Si bien UMAP es una herramienta dominante para la visualización de datos de alta dimensionalidad, los flujos de trabajo analíticos estándar suelen tratar el gráfico de dispersión 2D resultante como el único artefacto de interés. Este enfoque descarta el rico grafo de k-vecinos más cercanos (kNN) intermedio que UMAP construye internamente antes de la proyección. Los autores argumentan que este grafo codifica la geometría local y la conectividad del manifold de los datos en el espacio de alta dimensionalidad original de manera más fiel que la disposición 2D, la cual introduce inevitablemente distorsión. Al ignorar este grafo, los analistas pierden oportunidades para realizar tareas de comprensión (sensemaking)—como identificar puntos representativos, analizar jerarquías de densidad y detectar cohesión local—que quedan oscurecidas en la proyección 2D.

Metodología

El artículo propone elevar el grafo kNN interno de UMAP a un "recurso analítico de primer orden" aplicando algoritmos estándar de ciencia de redes directamente a él, en lugar de hacerlo sobre el embedding 2D. La metodología aprovecha las propiedades estructurales específicas del grafo: grado de salida $k$ fijo, grado de entrada variable y pesos de arista adaptativos a la densidad. Se aplican tres algoritmos específicos:

1. PageRank para la Selección de Representantes:

   • Mecanismo: En lugar de seleccionar ejemplares basados en centroides geométricos en el espacio 2D distorsionado (que pueden caer en regiones no representativas), los autores aplican PageRank al grafo kNN.
   • Lógica: La puntuación de un nodo se amplifica de forma transitiva; un punto obtiene un ranking alto no solo porque muchos nodos apunten a él (alto grado de entrada), sino porque esos nodos que apuntan son, a su vez, altamente posicionados. Esto identifica puntos globalmente representativos que actúan como "autoridades" en el manifold.
   • Implementación: Los pesos de las aristas se derivan de las fuerzas de membresía adaptativas a la densidad de UMAP.

2. Descomposición k-Core para la Jerarquía de Densidad:

   • Mecanismo: Los autores aplican la descomposición k-core al grafo para distinguir regiones de núcleos densos de periferias dispersas.
   • Lógica: A diferencia de la descomposición basada en el grado estándar, que está limitada por el grado de salida fijo $k$, este método se descompone basándose únicamente en el grado de entrada. Esto produce una puntuación de "núcleo" (0, 1, 2...) que indica qué tan profundamente embebido está un nodo dentro de subgrafos progresivamente más densos e interconectados.
   • Objetivo: Revelar jerarquías de subgrafos graduadas y subcategorías dentro de los clusters que las etiquetas de clustering discretas (por ejemplo, de HDBSCAN) no pueden capturar.

3. Coeficiente de Agrupamiento para la Cohesión Local:

   • Mecanismo: Se calcula el coeficiente de agrupamiento (CC, por sus siglas en inglés) para cada nodo para medir la fracción de sus vecinos que también están conectados entre sí.
   • Lógica: Un CC alto indica micro-vecindarios "estrechamente vinculados" donde los puntos se consideran mutuamente como vecinos más cercanos.
   • Objetivo: Detectar micro-clusters semánticamente coherentes (por ejemplo, estilos de escritura manual específicos) que pueden aparecer como una masa monolítica en una proyección 2D.

Contribuciones Clave

El artículo realiza dos contribuciones primarias:

1. Cambio Conceptual: Une la reducción de dimensionalidad con la ciencia de redes al tratar el grafo kNN descartado de UMAP como un recurso primario. Esto permite una comprensión que es complementaria a los gráficos de dispersión 2D, abordando específicamente la representatividad, la estructura de densidad y la cohesión local.
2. Validación Empírica: A través de evaluaciones cuantitativas y cualitativas en MNIST y Fashion MNIST, los autores demuestran que estos métodos basados en grafos son competitivos o superiores a los métodos diseñados específicamente para tales fines:
   • PageRank vs. k-medoids: Los puntos seleccionados mediante PageRank logran un balance de clases superior (menor divergencia de Jensen-Shannon) en comparación con k-medoids, que tiende a sobre-seleccionar de clases de alta varianza. Aunque k-medoids supera ligeramente a PageRank en representatividad con presupuestos muy pequeños, PageRank alcanza su nivel rápidamente y se mantiene competitivo en la precisión de clasificación de SVM descendente. Crucialmente, PageRank requiere solo un único cálculo de ranking global, mientras que k-medoids debe ejecutarse de nuevo para cada tamaño de presupuesto.
   • k-Core vs. HDBSCAN: Mientras que HDBSCAN asigna etiquetas de cluster discretas, la descomposición k-core revela una jerarquía graduada de centralidad dentro de los clusters. La membresía de HDBSCAN mostró una correlación casi nula con la "coreness", confirmando que responden a preguntas diferentes (pertenencia al grupo vs. posición dentro del grupo).
   • Coeficiente de Agrupamiento: El CC identifica micro-vecindarios distintos (por ejemplo, estilos específicos del dígito "6") que son topológicamente cohesivos pero que pueden ser visualmente indistinguibles en 2D.

Resultados

• Estabilidad: Los rankings de PageRank son altamente estables a través de un rango de 20x en los tamaños de vecindad ($k=5$ a $100$), con correlaciones de rango de Spearman medias de ~0.95, lo que indica que los representantes seleccionados no son artefactos de un valor de $k$ específico.
• Rendimiento:
  • Representatividad: PageRank rivaliza con k-medoids en la distancia de coseno media a los representantes más cercanos, especialmente a medida que aumenta el presupuesto de selección.
  • Balance de Clases: PageRank supera significativamente a k-medoids en el mantenimiento de la distribución global de clases (menor JSD), particularmente en presupuestos $s \ge 200$.
  • Utilidad Descendente: Los clasificadores SVM entrenados con ejemplares seleccionados por PageRank alcanzan una precisión dentro de 2 a 3 puntos porcentuales de k-medoids en Fashion MNIST y son comparables en MNIST.
  • Perspectiva Estructural: La descomposición k-core logra aislar subcategorías (por ejemplo, bolsos de mensajero frente a riñoneras dentro de la clase "bolso") filtrando por umbrales específicos de coreness. Los valores altos de CC aíslan estilos de escritura manual consistentes dentro del cluster del dígito "6".

Significación y Reivindicaciones

Los autores afirman que su trabajo demuestra el potencial sin explotar de la representación interna de UMAP. Al retener y analizar el grafo kNN, los analistas pueden acceder a información estructural (centralidad, jerarquía de conectividad, cohesión local) que se pierde o se distorsiona en la proyección 2D.

El artículo posiciona estos algoritmos de grafos no como reemplazos de las herramientas existentes, sino como métodos complementarios que ofrecen ventajas distintas:

• Proporcionan una forma libre de parámetros (o estable) de seleccionar representantes sin optimizar un objetivo de distancia.
• Ofrecen una jerarquía continua de densidad (vía k-core) en lugar de asignaciones de cluster discretas.
• Son computacionalmente eficientes, ejecutándose en menos de 1 segundo sobre 60,000 puntos al reutilizar los arreglos de vecinos precomputados de UMAP.

Los autores concluyen que esta perspectiva alienta a la comunidad a "mirar más allá del gráfico de dispersión y hacia el grafo que lo construyó", sugiriendo que este enfoque se extiende naturalmente a otros métodos de reducción de dimensionalidad que construyen grafos kNN (como TriMap o PaCMAP).