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

Resumo Técnico: ScaleMAP

Definição do Problema
Métodos de redução de dimensionalidade (DR) não lineares, particularmente UMAP, PaCMAP e t-SNE, são ferramentas padrão para análise exploratória de dados de alta dimensão. Esses métodos constroem grafos de $k$-vizinhos mais próximos ($k$NN) aproximados e normalizam distâncias locais usando larguras de banda adaptativas para lidar com variações de densidade local. Embora essa normalização garanta robustez a variações de densidade, ela inadvertidamente apaga a escala absoluta dos vizinhanços. Consequentemente, esses métodos falham em preservar os tamanhos relativos de clusters e suprimem estruturas esparsas, como pontes entre tipos celulares em transição, picos espectrais estreitos em imagens hiperespectrais ou variações de densidade que abrangem muitas ordens de magnitude (por exemplo, em citometria de fluxo).

Tentativas existentes para corrigir isso, como o DensMAP, introduzem um termo de penalidade à função de perda para maximizar a correlação entre as densidades de espaço original e de espaço de incorporação (embedding). No entanto, o artigo argumenta que essa abordagem cria um objetivo conflitante: a penalidade de densidade luta contra as forças inerentes de atração-repulsão do UMAP. Esse conflito dispersa os pontos para longe de seus vizinhanços reais, levando a uma alta fração de "pontos desconectados" e tornando as regiões esparsas difíceis de interpretar.

Metodologia
O ScaleMAP propõe uma abordagem diferente: em vez de adicionar um termo de perda conflitante, ele reintroduz a informação de escala através de uma mudança de variáveis aplicada à métrica de distância dentro do objetivo existente do UMAP.

1. Definição do Raio Local: O ScaleMAP utiliza o "raio local" ($r_i$), uma distância de raiz quadrada média ponderada de um ponto para seus vizinhos no espaço original, como uma medida de escala de vizinhança.
2. Distância Reescalonada: Em vez de usar a distância euclidiana ao quadrado $d_{ij}^2 = \|y_i - y_j\|^2$ na função de perda, o ScaleMAP define uma distância ao quadrado reescalonada:
   $$\tilde{d}_{ij}^2 = \frac{d_{ij}^2}{r_i r_j}$$
   onde $r_i$ e $r_j$ são os raios locais dos dois pontos terminais.
3. Modificação de Força: Essa substituição modifica o gradiente da perda de entropia cruzada. As regras de atualização para as forças de atração (vizinho) e repulsão (não-vizinho) são escalonadas por um fator de $1/(r_i r_j)$.
   • Simetria: Crucialmente, o reescalonamento aplica-se simetricamente tanto às forças de atração quanto às de repulsão. Isso preserva o equilíbrio local que confere ao UMAP suas propriedades de preservação de vizinhança.
   • Efeito: Pontos em regiões esparsas (grandes $r_i, r_j$) experimentam forças mais fracas por unidade de deslocamento euclidiano, fazendo com que a incorporação os espalhe. Pontos em regiões densas permanecem compactados.
4. Normalização: Para lidar com as escalas de distância independentes dos dados originais e da incorporação, os raios locais são normalizados usando o percentil 95 ($P_{95}$) da distribuição de raios antes da substituição.
5. Extensão ao PaCMAP: O mesmo princípio é aplicado ao PaCMAP (denominado Scale-PaCMAP) substituindo a média geométrica dos raios pelo produto das escalas de distância por ponto do PaCMAP ($\sigma_i \sigma_j$).

Principais Contribuições

1. Formulação Inovadora: A introdução do ScaleMAP, uma modificação do UMAP que injeta informação de escala local via uma mudança de variáveis, em vez de um termo de perda adicional.
2. Equilíbrio de Desempenho: Demonstração de que o ScaleMAP alcança a preservação de vizinhança do nível do UMAP enquanto iguala ou excede o DensMAP na preservação de densidade, com significativamente menos pontos dispersos (desconectados).
3. Recuperação de Estrutura: Recuperação bem-sucedida de estruturas esparsas que o UMAP colapsa (ex: pontes transcriptômicas) e preservação de estruturas de densidade multiescala (ex: dados de citometria de fluxo).
4. Generalização: Evidência de que o princípio de mudança de variáveis se generaliza para outros métodos, especificamente o PaCM%AP.

Resultados
Os autores avaliaram o ScaleMAP em benchmarks padrão (MNIST, Fashion-MNIST, COIL-20, Mammoth) e três conjuntos de dados científicos (transcriptômica Tabula Sapiens, imagem hiperespectral BCARS e citometria de fluxo de medula óssea humana).

• Métricas Quantitativas:

  • Preservação de Densidade: O ScaleMAP alcança preservação de densidade ($R^2$ de ajuste log-log) comparável ao DensMAP na maioria dos conjuntos de dados (ex: $R^2 \approx 0,51$ no Fashion-MNIST vs. $0,58$ do DensMAP). Em conjuntos de dados com amplitudes dinâmicas extremas, o ScaleMAP supera o DensMAP (ex: Citometria de Fluxo: $R^2 = 0,80$ vs. $0,68$; Imagem Hiperespectral: $R^2 = 0,81$ vs. $0,59$).
  • Preservação de Vizinhança: O ScaleMAP mantém o recall de kNN comparável ao UMAP (ex: 14,3% vs. 13,3% do UMAP no Fashion-MNIST) e significativamente melhor que o DensMAP (7,1%).
  • Pontos Desconectados: O ScaleMAP mantém a fração de pontos desconectados baixa e comparável ao UMAP (ex: 0,19% vs. 0,11% do UMAP), enquanto o DensMAP apresenta uma ordem de magnitude a mais de pontos desconectados (3,48%).
  • Mistura de Classes: O ScaleMAP reduz a mistura de classes em comparação com ambos os modelos de base.

• Observações Qualitativas:

  • Transcriptômica: O ScaleMAP recupera pontes esparsas entre populações celulares (ex: monócitos-neutrófilos, células B-T) que são colapsadas ou invisíveis no UMAP.
  • Imagem Hiperespectral: Revela picos espectrais esparsos e pequenos clusters que o UMAP comprime ou absorve no fundo.
  • Citometria de Fluxo: Representa fielmente a estrutura multiescala através de 17 ordens de magnitude, preservando um "bulbo" denso de células marcador-negativas que aparece como um pequeno recurso na incorporação, ao contrário do UMAP/DensMAP que carecem dessa fidelidade multiescala.
  • Diagnósticos Sintéticos: Nos conjuntos "XOI" e "Bridge", o ScaleMAP preserva corretamente tamanhos relativos e conexões esparsas, enquanto o DensMAP distorce formas e dispersa pontos.

Significância e Alegações
O artigo afirma que o ScaleMAP representa uma melhoria fundamental na forma como as incorporações que preservam vizinhanças lidam com a escala. Ao tratar o reescalonamento como uma mudança de variáveis em vez de um objetivo conflitante, o ScaleMAP evita o compromisso entre fidelidade de densidade e integridade de vizinhança que assola o DensMAP.

Os autores afirmam que o ScaleMAP é o único método testado que não sacrifica um eixo de qualidade da incorporação em favor de outro: ele retém a preservação de vizinhança do UMAP, iguala a fidelidade de densidade do DensMAP e melhora a preservação da ordem de distância global (superando o PaCMAP em conjuntos de dados com amplas amplitudes dinâmicas). O artigo conclui que restaurar a escala local é um ingrediente ausente geral nas incorporações que preservam vizinhança e sugere o ScaleMAP como um método padrão quando a representação fiel da escala é crítica. O método é notado por ser computacionalmente eficiente, adicionando apenas um overhead de $O(n)$ para pré-computar os raios, com tempo de execução total aproximadamente o dobro do UMAP.