Résumé Technique : EntroPath – Ensembles de Chemins à Entropie Maximale pour l'Apprentissage de Variétés

1. Énoncé du Problème

Les ensembles de données de haute dimension modernes, tels que la transcriptomique en cellule unique et les trajectoires de dynamique moléculaire, se concentrent souvent près de variétés riemanniennes de faible dimension. Un objectif central de l'apprentissage de variétés est de récupérer la géométrie intrinsèque de ces variétés, spécifiquement leurs distances géodésiques, dans une représentation de faible dimension.

Les approches existantes font face à des limitations significatives :

• Méthodes de plus court chemin (ex. Isomap) : Estiment les géodésiques via un chemin unique de plus court trajet sur un graphe de voisinage. Celles-ci sont fragiles ; un seul bord "raccourci" entre des régions géodésiquement distantes peut corrompre les distances globales. De plus, les garanties de récupération théoriques échouent souvent sur des variétés non convexes ou ramifiées.
• Méthodes de voisinage local (ex. t-SNE, UMAP) : Se concentrent sur la préservation des relations locales via des objectifs probabilistes. Bien qu'efficaces pour la visualisation, elles n'encodent pas explicitement les structures géodésiques globales.
• Méthodes de diffusion standard (ex. Diffusion Maps, PHATE) : Agrègent l'information sur des ensembles de chemins, offrant une robustesse aux erreurs de graphe. Cependant, elles reposent généralement sur des Marches Aléatoires Standards (SRW) normalisées par le degré local des nœuds. Cela provoque une dérive de la diffusion vers les régions densément échantillonnées, compressant les branches et les goulots d'étranglement peu denses, et biaisant les représentations vers les états terminaux à haute densité dans les données de trajectoire.

2. Méthodologie : EntroPath

EntroPath traite ces problèmes en construisant des dissimilarités basées sur la Marche Aléatoire à Entropie Maximale (MERW) et une dissimilarité d'énergie libre dérivée d'ensembles de chemins.

2.1 Marche Aléatoire à Entropie Maximale (MERW)

Contra contrairement à la SRW, qui normalise les probabilités de transition localement par le degré du nœud ($T_{ij} = A_{ij}/d_i$), la MERW maximise l'entropie des trajectoires globalement. La matrice de transition est définie par :
$$T_{ij} = \frac{A_{ij}}{\lambda_{\max}} \frac{\psi_j}{\psi_i}$$
où $A$ est la matrice d'affinité, $\lambda_{\max}$ est la plus grande valeur propre, et $\psi$ est le vecteur propre de Perron-Frobenius correspondant.

• Repondération Globale : La MERW incorpore la structure globale du graphe via $\psi$. Elle distribue la probabilité uniformément sur l'ensemble des chemins, laissant peu de masse sur les goulots d'étranglement à faible degré.
• Structure d'Opérateur de Schrödinger : Le Laplacien de la MERW ($I-T$) est similaire à un opérateur de Schrödinger discret $H = \lambda_{\max}I - A = -\Delta + V$, où $V$ est un potentiel induit par l'hétérogénéité des degrés ($V_i = \lambda_{\max} - d_i$). Cette structure est centrale aux garanties théoriques de la méthode.

2.2 Dissimilarité d'Énergie Libre

EntroPath définit la dissimilarité entre les nœuds $i$ et $j$ non pas comme un seul chemin le plus court, mais comme le logarithme négatif de la somme des poids sur tous les chemins de $k$ étapes (une fonction de partition).

• Coûts de Chemin : Les coûts des arêtes sont définis comme les logarithmes négatifs des affinités, $E(u,v) = -\log A_{uv}$.
• Formulation Log-Sum-Exp : La dissimilarité est :
  $$D_{ij} = -\log \left( \tilde{A}^k \right)_{ij}$$
  où $\tilde{A} = A/\lambda_{\max}$. Cela représente une relaxation "soft-min" de la distance du plus court chemin, agrégeant l'ensemble complet des $k$ étapes.
• Terme d'Entropie : La dissimilarité inclut un terme d'entropie ($-\sum p(\gamma) \log p(\gamma)$) qui récompense les paires connectées par de nombreux chemins comparables, se distinguant ainsi des métriques de plus court chemin.
• Symétrisation : Pour les affinités générales, la dissimilarité est symétrisée via la moyenne géométrique des probabilités de transition vers l'avant et vers l'arrière : $D_{ij} = -\log \sqrt{T^k_{ij} T^k_{ji}}$. Dans le cas symétrique (standard pour les affinités gaussiennes), cela se simplifie en $-\log (\tilde{A}^k)_{ij}$.

2.3 Régimes Géométriques et Mise à l'Échelle

La profondeur de diffusion $k$ interpole entre deux régimes :

1. Régime Géodésique (Petit $k$) : La dissimilarité approxime la géodésique du graphe (plus court chemin) via la formule du noyau de chaleur de Varadhan à court terme.
2. Régime de Mélange (Grand $k$) : La dissimilarité converge vers une distribution stationnaire dépendant uniquement du vecteur de Perron, perdant les détails géométriques fins.
   La méthode sélectionne $k$ automatiquement en utilisant le "genou" de l'entropie de von Neumann de l'opérateur MERW, garantissant que le temps de diffusion est suffisant pour connecter les points mais pas trop long pour éviter un mélange excessif.

2.4 Scalabilité

Pour les grands ensembles de données, EntroPath emploie :

• Projection par Points Repères (Landmark Projection) : Une extension de type Nyström où les nouveaux points sont projetés dans l'incorporation d'un sous-ensemble de points repères via l'interpolation par noyau, évitant le recalcul de l'opérateur global.
• Noyaux Adaptatifs : Utilise des largeurs de bande adaptatives (basées sur les distances $k$-NN locales) pour gérer efficacement les densités d'échantillonnage non uniformes.

3. Contributions Clés

1. Innovation Algorithmique : Introduction d'EntroPath, une méthode d'apprentissage de variétés basée sur la MERW et une dissimilarité d'énergie libre dérivée d'ensembles de chemins.
2. Formulation Théorique : Une preuve que la dissimilarité d'énergie libre symétrisée converge vers la distance géodésique au carré sur la variété sous-jacente dans la limite de temps court (Théorème 5.3). Cela repose sur la structure d'opérateur de Schrödinger discret de la MERW et la formule de Varadhan.
3. Connexion aux Noyaux : Démonstration que le noyau MERW symétrisé admet une factorisation de Gram exacte (Proposition 4.1), connectant directement EntroPath aux méthodes de noyau et aux cartes de diffusion, contrairement à de nombreuses méthodes de diffusion basées sur des profils.
4. Extensions Scalables : Développement de l'incorporation hors échantillon basée sur des points repères et d'une méthode de pseudotemps par potentiel de diffusion pour l'inférence de trajectoire.
5. Protocole d'Évaluation : Évaluation en deux étapes séparant la qualité des distances (qualité du noyau) de la qualité de l'incorporation (qualité de la disposition), soulignant un biais dans l'évaluation standard des géodésiques qui favorise les méthodes liées au graphe $k$-NN spécifique utilisé pour la vérité de terrain.

4. Résultats Expérimentaux

EntroPath a été évalué sur des variétés synthétiques (rouleau suisse, arbres clairsemés) et six ensembles de données biologiques de cellule unique (ex. Paul15, Nestorowa, Root Atlas).

• Variétés Synthétiques :

  • Sur des variétés échantillonnées de manière non uniforme et des arbres ramifiés clairsemés, EntroPath a systématiquement surpassé les bases de diffusion (PHATE, HeatGeo, DTNE) et les méthodes de plus court chemin (Isomap) dans la récupération de la géométrie géodésique.
  • Il a obtenu les corrélations de Spearman et de Pearson les plus élevées avec les géodésiques de vérité de terrain dans les évaluations de niveau distance.
  • Dans les évaluations de niveau incorporation, EntroPath préserve mieux la structure globale que les méthodes locales (UMAP, t-SNE) et montre une fiabilité et une continuité supérieures par rapport aux autres méthodes de diffusion, particulièrement dans les régions clairsemées où les méthodes basées sur la SRW "fuient" à travers les goulots d'étranglement.

• Données de Cellule Unique :

  • EntroPath égale ou dépasse les performances de PHATE, HeatGeo et DTNE sur des métriques telles que DEMaP (préservation de la variété) et la fiabilité (trustworthiness).
  • Il a démontré une robustesse particulière sur les ensembles de données avec un échantillonnage non uniforme et des trajectoires ramifiées bien séparées, où il maintient une séparation claire entre les états cellulaires sans les lisser en clusters denses.
  • Sur le grand atlas de l'atlas de racines d'Arabidopsis ($1,1 \times 10^5$ cellules), EntroPath a atteint une fidélité géométrique comparable à DTNE en environ 15 secondes, en exploitant ses stratégies de points repères et de noyaux adaptatifs pour éviter le coût computationnel des puissances de graphes denses requis par les méthodes hard-$k$NN.

5. Signification et Revendications

L'article affirme qu'EntroPath offre une solution fondée sur des principes au conflit entre la normalisation du degré local (qui biaise la diffusion dans la SRW) et la récupération géodésique globale (qui est fragile pour les méthodes de plus court chemin).

• Robustesse à la Densité d'Échantillonnage : En utilisant la MERW, EntroPath traite les goulots d'étranglement à faible degré comme des barrières de haute énergie plutôt que comme des passages faciles. Cela préserve la séparation des branches échantillonnées de manière clairsemée et empêe l'effondrement de la géométrie globale souvent observé dans les incorporations basées sur la SRW.
• Garantie Théorique : La convergence vers la distance géodésique au carré fournit un fondement géométrique rigoureux, la distinguant des distances de diffusion heuristiques.
• Utilité Pratique : La méthode fournit une approche scalable et légère en paramètres (utilisant la sélection automatique de la profondeur) qui est compétitive à travers divers régimes de données, des benchmarks synthétiques aux trajectoires biologiques complexes.

Les auteurs notent des limitations, spécifiquement que la sélection de la profondeur basée sur l'entropie peut devenir bruitée sur des branches très courtes, et suggèrent des travaux futurs dans les formulations en temps continu et la gestion des affinités dirigées (ex. vélocité de l'ARN).