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

Resumo Técnico: Redução de Dimensionalidade Encontra a Ciência de Redes

Declaração do Problema

Embora o UMAP seja uma ferramenta dominante para a visualização de dados de alta dimensão, os fluxos de trabalho analíticos padrão tipicamente tratam o gráfico de dispersão 2D resultante como o único artefato de interesse. Essa abordagem descarta o rico grafo de k-vizinhos mais próximos (kNN) intermediário que o UMAP constrói internamente antes da projeção. Os autores argumentam que esse grafo codifica a geometria local e a conectividade do manifold de dados no espaço original de alta dimensão de forma mais fiel do que o layout 2D, que inevitavelmente introduz distorções. Ao ignorar esse grafo, os analistas perdem oportunidades de realizar tarefas de compreensão (sensemaking) — como identificar pontos representativos, analisar hierarquias de densidade e detectar coesão local — que são obscurecidas na projeção 2D.

Metodologia

O artigo propõe elevar o grafo kNN interno do UMAP a um "recurso analítico de primeira classe", aplicando algoritmos padrão de ciência de redes diretamente a ele, em vez de aplicá-los ao embedding 2D. A metodologia aproveita as propriedades estruturais específicas do grafo: grau de saída fixo $k$, grau de entrada variável e pesos de aresta adaptáveis à densidade. Três algoritmos específicos são aplicados:

1. PageRank para Seleção de Representantes:

   • Mecanismo: Em vez de selecionar exemplares baseando-se em centroides geométricos no espaço 2D distorcido (que podem cair em regiões não representativas), os autores aplicam o PageRank ao grafo kNN.
   • Lógica: A pontuação de um nó é amplificada transitoriamente; um ponto possui uma classificação alta não apenas porque muitos nós apontam para ele (alto grau de entrada), mas porque os nós que apontam para ele são, eles próprios, altamente classificados. Isso identifica pontos globalmente representativos que servem como "autoridades" no manifold.
   • Implementação: Os pesos das arestas são derivados das forças de pertinência adaptáveis à densidade do UMAP.

2. Decomposição k-Core para Hierarquia de Densidade:

   • Mecanismo: Os autores aplicam a decomposição k-core ao grafo para distinguir regiões de núcleo denso de periferias esparsas.
   • Lógica: Diferente da decomposição baseada em grau padrão, que é limitada pelo grau de saída fixo $k$, este método realiza a decomposição baseando-se apenas no grau de entrada. Isso produz uma pontuação de "coreness" (núcleo) (0, 1, 2...) indicando o quão profundamente um nó está inserido em subgrafos progressivamente mais densos e interconectados.
   • Objetivo: Revelar hierarquias de subgrafos graduadas e subcategorias dentro de clusters que rótulos de agrupamento discretos (ex: de HDBSCAN) não conseguem capturar.

3. Coeficiente de Agrupamento para Coesão Local:

   • Mecanismo: O coeficiente de agrupamento (CC) é calculado para cada nó para medir a fração de seus vizinhos que também estão conectados entre si.
   • Lógica: Um CC alto indica micro-vizinhanças "bem conectadas" onde os pontos consideram mutuamente uns aos outros como vizinhos mais próximos.
   • Objetivo: Detectar micro-clusters semanticamente coerentes (ex: estilos específicos de caligrafia) que podem aparecer como uma massa monolítica em uma projeção 2D.

Principais Contribuições

O artigo apresenta duas contribuições primárias:

1. Mudança Conceitual: Ele une a redução de dimensionalidade e a ciência de redes ao tratar o grafo kNN descartado do UMAP como um recurso primário. Isso permite uma compreensão que é complementar aos gráficos de dispersão 2D, abordando especificamente representatividade, estrutura de densidade e coesão local.
2. Validação Empírica: Através de avaliações quantitativas e qualitativas no MNIST e Fashion MNIST, os autores demonstram que esses métodos baseados em grafos são competitivos ou superiores a métodos criados para fins específicos:
   • PageRank vs. k-medoids: Pontos selecionados via PageRank alcançam um equilíbrio de classes superior (menor divergência de Jensen-Shannon) em comparação ao k-medoids, que tende a selecionar excessivamente classes de alta variância. Embora o k-medoids supere ligeiramente o PageRank em representatividade para orçamentos muito pequenos, o PageRank alcança o nível rapidamente e permanece competitivo na precisão de classificação SVM subsequente. Crucialmente, o PageRank requer apenas um único cálculo de classificação global, enquanto o k-medoids deve ser executado novamente para cada tamanho de orçamento.
   • k-Core vs. HDBSCAN: Enquanto o HDBSCAN atribui rótulos de cluster discretos, a decomposição k-core revela uma hierarquia graduada de centralidade dentro dos clusters. A probabilidade de pertinência do HDBSCAN mostrou correlação quase nula com a "coreness", confirmando que respondem a perguntas diferentes (pertencimento ao grupo vs. posição dentro do grupo).
   • Coeficiente de Agrupamento: O CC identifica micro-vizinhanças distintas (ex: estilos específicos do dígito "6") que são topologicamente coesas, mas podem ser visualmente indistinguíveis em 2D.

Resultados

• Estabilidade: As classificações do PageRank são altamente estáveis através de uma faixa de 20x no tamanho de vizinhança ($k=5$ a $100$), com correlações médias de ranking de Spearman de ~0,95, indicando que os representantes selecionados não são artefatos de um valor específico de $k$.
• Desempenho:
  • Representatividade: O PageRank rivaliza com o k-medoids em distância de cosseno média para os representantes mais próximos, especialmente conforme o orçamento de seleção aumenta.
  • Equilíbrio de Classes: O PageRank supera significativamente o k-medoids na manutenção da distribuição de classes global (menor JSD), particularmente para orçamentos $s \ge 200$.
  • Utilidade Subsequente: Classificadores SVM treinados com exemplares selecionados por PageRank alcançam uma precisão dentro de 2 a 3 pontos percentuais do k-medoids no Fashion MNIST e são comparáveis no MNIST.
  • Insight Estrutural: A decomposição k-core isola com sucesso subcategorias (ex: bolsas de mensageiro vs. bolsas de cintura dentro da classe "bag") ao filtrar por limiares específicos de coreness. Valores altos de CC isolam estilos de caligrafia consistentes dentro do cluster do dígito "6".

Significância e Alegações

Os autores alegam que seu trabalho demonstra o potencial inexplorado da representação interna do UMAP. Ao reter e analisar o grafo kNN, os analistas podem acessar informações estruturais (centralidade, hierarquia de conectividade, coesão local) que são perdidas ou distorcidas na projeção 2D.

O artigo posiciona esses algoritmos de grafo não como substitutos para ferramentas existentes, mas como métodos complementares que oferecem vantagens distintas:

• Eles fornecem uma maneira livre de parâmetros (ou estável) de selecionar representantes sem otimizar um objetivo de distância.
• Oferecem uma hierarquia contínua de densidade (via k-core) em vez de atribuições de cluster discretas.
• São computacionalmente eficientes, rodando em menos de 1 segundo para 60.000 pontos ao reutilizar os arrays de vizinhos pré-computados do UMAP.

Os autores concluem que essa perspectiva encoraja a comunidade a "olhar além do gráfico de dispersão e para dentro do grafo que o criou", sugerindo que esta abordagem se estende naturalmente a outros métodos de redução de dimensionalidade que constroem grafos kNN (ex: TriMap, PaCMAP).