Sintesi Tecnica: EntroPath – Embedding di Ensemble di Percorsi a Massima Entropia per il Manifold Learning

1. Definizione del Problema

I moderni dataset ad alta dimensionalità, come la trascrittomica a singola cellula e le traiettorie di dinamica molecolare, si concentrano spesso vicino a varietà (manifold) Riemanniane a bassa dimensionalità. Un obiettivo centrale del manifold learning è il recupero della geometria intrinseca di queste varietà, specificamente delle loro distanze geodetiche, in una rappresentazione a bassa dimensionalità.

Gli approcci esistenti presentano limitazioni significative:

• Metodi a Percorso Minimo (es. Isomap): Stimano le geodetiche tramite singoli percorsi minimi su un grafo di vicinato. Questi sono fragili; un singolo arco di "scorciatoia" tra regioni geodesicamente distanti può corrompere le distanze globali. Inoltre, le garanzie teoriche di recupero spesso falliscono su varietà non convesse o ramificate.
• Metodi di Vicinato Locale (es. t-SNE, UMAP): Si concentrano sulla preservazione delle relazioni locali tramite obiettivi probabilistici. Sebbene efficaci per la visualizzazione, non codificano esplicitamente le strutture geodetiche globali.
• Metodi di Diffusione Standard (es. Diffusion Maps, PHATE): Aggregano informazioni su ensemble di percorsi, offrendo robustezza agli errori del grafo. Tuttavia, tipicamente si affidano a Passeggiate Aleatorie Standard (SRW) normalizzate per grado locale del nodo. Ciò causa una deriva della diffusione verso regioni densamente campionate, comprimendo rami e colli di bottiglia sparsi e influenzando negativamente le rappresentazioni verso stati terminali ad alta densità nei dati di traiettoria.

2. Metodologia: EntroPath

EntroPath affronta questi problemi costruendo dissimilarità basate sulla Massima Entropia della Passeggiata Aleatoria (MERW) e su una dissimilarità di energia libera derivata da ensemble di percorsi.

2.1 Massima Entropia della Passeggiata Aleatoria (MERW)

A differenza della SRW, la MERW massimizza l'entropia delle traiettorie globalmente. La matrice di transizione è definita come:
$$T_{ij} = \frac{A_{ij}}{\lambda_{\max}} \frac{\psi_j}{\psi_i}$$
dove $A$ è la matrice di affinità, $\lambda_{\max}$ è il più grande autovalore e $\psi$ è il corrispondente autovettore di Perron-Frobenius.

• Ripesatura Globale: La MERW incorpora la struttura globale del grafo tramite $\psi$. Distribuisce la probabilità uniformemente sull'ensemble di percorsi, lasciando poca massa sui colli di bottiglia a basso grado.
• Struttura dell'Operatore di Schrödinger: Il Laplaciano MERW ($I-T$) è simile a un operatore di Schrödinger discreto $H = \lambda_{\max}I - A = -\Delta + V$, dove $V$ è un potenziale indotto dall'eterogeneità del grado ($V_i = \lambda_{\max} - d_i$). Questa struttura è centrale per le garanzie teoriche del metodo.

2.2 Dissimilarità di Energia Libera

EntroPath definisce la dissimilarità tra i nodi $i$ e $j$ non come un singolo percorso minimo, ma come il logaritmo negativo della somma dei pesi su tutti i percorsi a $k$-passaggi (una funzione di partizione).

• Costi di Percorso: I costi degli archi sono definiti come log-affinità negativi, $E(u,v) = -\log A_{uv}$.
• Formulazione Log-Sum-Exp: La dissimilarità è:
  $$D_{ij} = -\log \left( \tilde{A}^k \right)_{ij}$$
  dove $\tilde{A} = A/\lambda_{\max}$. Questo rappresenta una rilassazione soft-min della distanza del percorso minimo, aggregando l'intero ensemble a $k$-passaggi.
• Termine di Entropia: La dissimilarità include un termine di entropia ($-\sum p(\gamma) \log p(\gamma)$) che premia le coppie connesse da molti percorsi comparabili, distinguendosi dalle metriche di percorso minimo.
• Simmetrizzazione: Per affinità generiche, la dissimilarità è simmetrizzata tramite la media geometrica delle probabilità di transizione in avanti e all'indietro: $D_{ij} = -\log \sqrt{T^k_{ij} T^k_{ji}}$. Nel caso simmetrico (standard per affinità gaussiane), questo si semplifica in $-\log (\tilde{A}^k)_{ij}$.

2.3 Regimi Geometrici e Scaling

La profondità di diffusione $k$ interpola tra due regimi:

1. Regime Geodesico (Piccolo $k$): La dissimilarità approssima la geodetica del grafo (percorso minimo) tramite la formula del kernel di calore a breve tempo di Varadhan.
2. Regime di Mixing (Grande $k$): La dissimilarità converge a una distribuzione stazionaria dipendente solo dal vettore di Perron, perdendo i dettagli geometrici fini.
   Il metodo seleziona $k$ automaticamente usando il "ginocchio" dell'entropia di von Neumann dell'operatore MERW, garantendo che il tempo di diffusione sia sufficiente per connettere i punti ma non così lungo da causare un eccessivo mixing.

2.4 Scalabilità

Per dataset di grandi dimensioni, EntroPath impiega:

• Proiezione su Landmark: Un'estensione di tipo Nyström in cui i nuovi punti vengono proiettati nell'embedding di un sottoinsieme di landmark tramite interpolazione kernel, evitando la ricalcolazione dell'operatore globale.
• Kernel Adattivi: Utilizza larghezze di banda adattive (basate sulle distanze $k$-NN locali) per gestire efficacemente le densità di campionamento non uniformi.

3. Contributi Chiave

1. Innovazione Algoritmica: Introduzione di EntroPath, un metodo di manifold learning basato su MERW e una dissimilarità di energia libera derivata da ensemble di percorsi.
2. Formulazione Teorica: Una dimostrazione che la dissimilarità di energia libera simmetrizzata converge alla distanza geodesica al quadrato sulla varietà sottostante nel limite a breve tempo (Teorema 5.3). Ciò si basa sulla struttura dell'operatore di Schrödinger discreto del Laplaciano MERW e sulla formula di Varadhan.
3. Connessione con i Kernel: Dimostrazione che il kernel MERW simmetrizzato ammette una fattorizzazione di Gram esatta (Proposizione 4.1), collegando direttamente EntroPath ai metodi kernel e alle diffusion maps, diversamente da molti metodi di diffusione basati su profili.
4. Estensioni Scalabili: Sviluppo dell'embedding out-of-sample basato su landmark e di un metodo di pseudotempo basato sul potenziale di diffusione.
5. Protocollo di Valutazione: Una valutazione in due fasi che separa la qualità del kernel (livello di distanza) dalle prestazioni del layout (livello di embedding), evidenziando un bias nella valutazione standard delle geodetiche che favorisce i metodi legati allo specifico grafo $k$-NN usato per la ground truth.

4. Risultati Sperimentali

EntroPath è stato valutato su manifold sintetici (Swiss roll, alberi sparsi) e sei dataset biologici a singola cellula (es. Paul15, Nestorowa, Root Atlas).

• Manifold Sintetici:

  • Su manifold campionati in modo non uniforme e alberi ramificati sparsi, EntroPath ha superato costantemente i baseline basati sulla diffusione (PHATE, HeatGeo, DTNE) e i metodi a percorso minimo (Isomap) nel recupero della geometria geodesica.
  • Ha raggiunto le più alte correlazioni di Spearman e Pearson con le geodetiche della ground-truth nelle valutazioni a livello di distanza.
  • Nelle valutazioni a livello di embedding, EntroPath ha preservato meglio la struttura globale rispetto ai metodi locali (UMAP, t-SNE) e ha mostrato una superiorità in termini di affidabilità (trustworthiness) e continuità rispetto ad altri metodi di diffusione, particolarmente nelle regioni sparse dove i metodi basati su SRW "perdono" attraverso i colli di bottiglia.

• Dati Single-Cell:

  • EntroPath ha eguagliato o superato le prestazioni di PHATE, HeatGeo e DTNE su metriche come DEMaP (preservazione del manifold) e trustworthiness.
  • Ha dimostrato particolare robustezza su dataset con campionamento non uniforme e traiettorie ramificate ben separate, mantenendo una chiara separazione tra gli stati cellulari senza fonderli in cluster densi.
  • Sul grande atlas della radice di Arabidopsis ($1.1 \times 10^5$ cellule), EntroPath ha raggiunto una fedeltà geometrica comparabile a DTNE in circa 15 secondi, sfruttando le strategie di landmark e i kernel adattivi per evitare il costo computazionale dei grafi densi richiesti dai metodi hard-$k$NN.

5. Significato e Rivendicazioni

L'articolo sostiene che EntroPath offra una soluzione rigorosa alla tensione tra normalizzazione del grado locale (che influenza la diffusione in SRW) e recupero della geodetica globale (che è fragile nei metodi a percorso minimo).

• Robustezza alla Densità di Campionamento: Utilizzando la MERW, EntroPath tratta i colli di bottiglia a basso grado come barriere ad alta energia piuttosto che passaggi facili. Ciò preserva la separazione dei rami campionati raramente e previene il "collasso" della geometria globale spesso visto negli embedding basati su SRW.
• Garanzia Teorica: La convergenza alla distanza geodesica al quadrato fornisce una base geometrica rigorosa, distinguendo il metodo dagli approoli euristici di distanza di diffusione.
• Utilità Pratica: Il metodo fornisce un approccio scalabile e con pochi parametri (usando la selezione automatica della profondità) che compete efficacemente in diversi regimi di dati, dai benchmark sintetici alle complesse traiettorie biologiche.

Gli autori segnalano alcune limitazioni, specificamente che la selezione della profondità basata sull'entropia può diventare rumorosa su rami molto brevi, e suggeriscono lavori futuri in formulazioni a tempo continuo e nella gestione di affinità dirette (es. per la RNA velocity).