Resumo Técnico: EntroPath – Imbedimento de Conjunto de Caminhos de Entropia Máxima para Aprendizado de Variedades

1. Declaração do Problema

Conjuntos de dados de alta dimensão modernos, como transcriptômica de célula única e trajetórias de dinâmica molecular, frequentemente se concentram próximas a variedades riemannianas de baixa dimensão. Um objetivo central do aprendizado de variedades é recuperar a geometria intrínseca dessas variedades, especificamente suas distâncias geodésicas, em uma representação de baixa dimensão.

Abordagens existentes enfrentam limitações significativas:

• Métodos de Caminho Mais Curto (ex: Isomap): Estimam geodésicas via caminhos únicos mais curtos em um grafo de vizinhança. Estes são frágeis; uma única aresta de "atalho" entre regiões geodesicamente distantes pode corromper as distâncias globais. Além disso, garantias teóricas de recuperação frequentemente falham em variedades não convexas ou com ramificações.
• Métodos de Vizinhança Local (ex: t-SNE, UMAP): Focam na preservação de relações locais via objetivos probabilísticos. Embora eficazes para visualização, eles não codificam explicitamente estruturas geodésicas globais.
• Métodos de Difusão Padrão (ex: Diffusion Maps, PHATE): Agregam informações sobre conjuntos de caminhos, oferecendo robustez a erros de grafo. No entanto, eles tipicamente dependem de Caminhadas Aleatórias Padrão (SRW) normalizadas pelo grau local do nó. Isso faz com que a difusão derive em direção a regiões densamente amostradas, comprimindo ramos esparsos e gargalos, e enviesando as representações para estados terminais de alta densidade em dados de trajetória.

2. Metodologia: EntroPath

O EntroPath aborda essas questões construindo dissimilaridades baseadas na Caminhada Aleatória de Entropia Máxima (MERW) e uma dissimilaridade de energia livre derivada de conjuntos de caminhos.

2.1 Caminhada Aleatória de Entropia Máxima (MERW)

Ao contrário da SRW, que normaliza probabilidades de transição localmente pelo grau do nó ($T_{ij} = A_{ij}/d_i$), a MERW maximiza a entropia das trajetórias globalmente. A matriz de transição é definida como:
$$T_{ij} = \frac{A_{ij}}{\lambda_{\max}} \frac{\psi_j}{\psi_i}$$
onde $A$ é a matriz de afinidade, $\lambda_{\max}$ é o maior autovalor e $\psi$ é o autovetor de Perron-Frobenius correspondente.

• Reponderação Global: A MERW incorpora a estrutura de grafo global via $\psi$. Ela distribui a probabilidade uniformemente sobre o conjunto de caminhos, deixando pouca massa em gargalos de baixo grau.
• Estrutura do Operador de Schrödinger: O Laplaciano MERW ($I-T$) é similar a um operador de Schrödinger discreto $H = \lambda_{\max}I - A = -\Delta + V$, onde $V$ é um potencial induzido pela heterogeneidade de grau ($V_i = \lambda_{\max} - d_i$). Esta estrutura é central para as garantias teóricas do método.

2.2 Dissimilaridade de Energia Livre

O EntroPath define a dissimilaridade entre os nós $i$ e $j$ não como um único caminho mais curto, mas como o logaritmo negativo da soma dos pesos sobre todos os caminhos de $k$ passos (uma função de partição).

• Custos de Caminho: Os custos das arestas são definidos como log-afinidades negativas, $E(u,v) = -\log A_{uv}$.
• Formulação Log-Sum-Exp: A dissimilaridade é:
  $$D_{ij} = -\log \left( \tilde{A}^k \right)_{ij}$$
  onde $\tilde{A} = A/\lambda_{\max}$. Isso representa uma relaxação soft-min da distância do caminho mais curto, agregando todo o conjunto de $k$ passos.
• Termo de Entropia: A dissimilaridade inclui um termo de entropia ($-\sum p(\gamma) \log p(\gamma)$) que recompensa pares conectados por muitos caminhos comparáveis, distinguindo-se de métricas de caminho mais curto.
• Simetrização: Para afinidades gerais, a dissimilaridade é simetrizada via a média geométrica das probabilidades de transição direta e reversa: $D_{ij} = -\log \sqrt{T^k_{ij} T^k_{ji}}$. No caso simétrico (padrão para afinidades gaussianas), isso simplifica para $-\log (\tilde{A}^k)_{ij}$.

2.3 Regimes Geométricos e Escalonamento

A profundidade de difusão $k$ interpola entre dois regimes:

1. Regime Geodésico (Pequeno $k$): A dissimilaridade aproxima a geodésica do grafo (caminho mais curto) via a fórmula do kernel de calor de tempo curto de Varadhan.
2. Regime de Mistura (Grande $k$): A dissimilaridade converge para uma distribuição estacionária dependente apenas do vetor de Perron, perdendo detalhes geométricos finos.
   O método seleciona $k$ automaticamente usando o "joelho" da entropia de von Neumann do operador MERW, garantindo que o tempo de difusão seja suficiente para conectar os pontos, mas não tão longo a ponto de promover uma mistura excessiva.

2.4 Escalabilidade

Para grandes conjuntos de dados, o EntroPath emprega:

• Projeção de Marcos (Landmark Projection): Uma extensão do tipo Nyström onde novos pontos são projetados no imbedimento de um subconjunto de marcos via interpolação de kernel, evitando a recomputação do operador global.
• Kernels Adaptativos: Utiliza larguras de banda adaptativas (baseadas em distâncias $k$-NN locais) para lidar efetivamente com densidades de amostragem não uniformes.

3. Principais Contribuições

1. Inovação Algorítmica: Introdução do EntroPath, um método de aprendizado de variedades baseado em MERW e uma dissimilaridade de energia livre derivada de conjuntos de caminhos.
2. Formulação Teórica: Uma prova de que a dissimilaridade de energia livre simetrizada converge para a distância geodésica ao quadrado na variedade subjacente no limite de tempo curto (Teorema 5.3). Isso se baseia na estrutura de operador de Schrödinger discreto do Laplaciano MERW e na fórmula de Varadhan.
3. Conexão com Kernel: Demonstração de que o kernel MERW simetrizado admite uma fatoração de Gram exata (Proposição 4.1), conectando o EntroPath diretamente a métodos de kernel e mapas de difusão, diferentemente de muitos métodos de difusão baseados em perfis.
4. Extensões Escaláveis: Desenvolvimento de imbedimento fora da amostra (out-of-sample) baseado em marcos e um método de pseudotempo de potencial de difusão para inferência de trajetória.
5. Protocolo de Avaliação: Avaliação em duas etapas separando o nível de distância (qualidade do kernel) do nível de imbedimento (qualidade do layout), destacando um viés na avaliação geodésica padrão que favorece métodos atrelados ao grafo $k$-NN específico usado para o ground truth.

4. Resultados Experimentais

O EntroPath foi avaliado em variedades sintéticas (Swiss roll, árvores esparsas) e seis conjuntos de dados biológicos de célula única (ex: Paul15, Nestorowa, Root Atlas).

• Variedades Sintéticas:

  • Em variedades amostradas de forma não uniforme e árvores de ramificação esparsas, o EntroPath superou consistentemente as bases de difusão (PHATE, HeatGeo, DTNE) e os métodos de caminho mais curto (Isomap) na recuperação da geometria geodésica.
  • Alcançou as maiores correlações de Spearman e Pearson com as geodésicas de ground-truth em avaliações de nível de distância.
  • Nas avaliações de nível de imbedimento, o EntroPath preservou melhor a estrutura global do que métodos locais (UMAP, t-SNE) e mostrou confiança (trustworthiness) e continuidade superiores em comparação com outros métodos de difusão, particularmente em regiões esparsas onde métodos baseados em SRW "vazam" através de gargalos.

• Dados de Célula Única:

  • O EntroPath igualou ou excedeu o desempenho do PHATE, HeatGeo e DTNE em métricas como DEMaP (preservação de variedade) e confiança.
  • Demonstrou robustez particular em conjuntos de dados com amostragem não uniforme e trajetórias de ramificação bem separadas, onde manteve a separação clara entre estados celulares sem suavizá-los em clusters densos.
  • No grande atlas de raiz de Arabidopsis ($1.1 \times 10^5$ células), o EntroPath alcançou fidelidade geométrica comparável ao DTNE em aproximadamente 15 segundos, aproveitando suas estratégias de marcos e kernel adaptativo para evitar o custo computacional de potências de grafos densos exigidas por métodos de hard-$k$NN.

5. Significância e Alegações

O artigo afirma que o EntroPath oferece uma solução principiada para a tensão entre normalização de grau local (que enviesa a difusão em SRW) e recuperação geodésica global (que é frágil em métodos de caminho mais curto).

• Robustez à Densidade de Amostragem: Ao utilizar MERW, o EntroPath trata gargalos de baixo grau como barreiras de alta energia em vez de passagens fáceis. Isso preserva a separação de ramos amostrados esparsamente e evita o "colapso" da geometria global frequentemente visto em imbedimentos baseados em SRW.
• Garantia Teórica: A convergência para a distância geodésica ao quadrado fornece uma base geométrica rigorosa, distinguindo-o de distâncias de difusão heurísticas.
• Utilidade Prática: O método fornece uma abordagem escalável e de poucos parâmetros (usando seleção de profundidade automática) que performa competitivamente através de diversos regimes de dados, desde benchmarks sintéticos até complexas trajetórias biológicas.

Os autores observam limitações, especificamente que a seleção de profundidade baseada em entropia pode tornar-se ruidosa em ramos muito curtos, e sugerem trabalhos futuros em formulações de tempo contínuo e no tratamento de afinidades direcionadas (ex: velocidade de RNA).