🤖 machine learning

EmbedOR: Provable Cluster-Preserving Visualizations with Curvature-Based Stochastic Neighbor Embeddings

L'article présente EmbedOR, un algorithme de plongement stochastique de voisinage prouvable qui incorpore la courbure de graphe discrète pour préserver les structures de grappes sous-jacentes et prévenir la fragmentation spécieuse des régions continues à haute densité souvent observée avec des méthodes telles que UMAP et t-SNE.

Auteurs originaux : Tristan Luca Saidi, Abigail Hickok, Bastian Rieck, Andrew J. Blumberg

Publié 2026-07-14

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Tristan Luca Saidi, Abigail Hickok, Bastian Rieck, Andrew J. Blumberg

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous avez une énorme pelote de laine emmêlée représentant un ensemble de données massif. Certaines parties de la laine sont nouées ensemble en grappes colorées et serrées (comme des groupes d'amis), tandis que d'autres s'étirent en longs fils continus. Votre objectif est d'aplatir cette pelote 3D sur une feuille de papier 2D afin de pouvoir voir les motifs sans que la laine ne s'emmêle de façon inextricable ou ne se déchire.

Pendant des années, les outils populaires pour ce travail — appelés tSNE et UMAP — ont été comme des enfants enthousiastes mais maladroits essayant d'aplatir la laine. Ils font souvent du bon travail pour séparer les grappes colorées, mais ils ont la fâcheuse habine de briser les longs fils continus. Ils peuvent prendre un chemin unique et fluide de données et le déchirer en trois ou quatre îles déconnectées, donnant l'impression que les données se sont brisées en morceaux alors qu'elles sont en fait toutes connectées. Ils échouent également parfois à repérer les grappes dès le départ si les données ne sont pas parfaitement rondes et ordonnées.

Entrez en scène EmbedOR, un nouvel outil conçu par les chercheurs Tristan Luca Saidi, Abigail Hickok, Bastian Rieck et Andrew J. Blumberg. Considérez EmbedOR comme une paire de ciseaux sensible à la « courbure ». Avant de couper ou d'aplatir la laine, il mesure la « torsion » de chaque connexion.

La magie de la « torsion » (la courbure)

Le ingrédient secret d'EmbedOR est ce qu'on appelle la courbure d'Ollivier-Ricci. Imaginez que vous marchez dans une fête bondée.

Si vous êtes dans un groupe serré d'amis où tout le monde se connaît, la « courbure » est positive. Cela ressemble à une communauté chaleureuse et connectée.
Si vous vous tenez sur un pont étroit reliant deux pièces différentes, la « courbure » est négative. Cela ressemble à un goulot d'étranglement ; si vous faites un pas de côté, vous tombez dans un autre monde.

Les anciens outils (tSNE et UMAP) regardaient principalement à quelle distance les gens se tenaient les uns des autres dans la pièce. EmbedOR, cependant, regarde la forme de la foule. Il sait qu'un « virage négatif » (un goulot d'étranglement) est un endroit dangereux pour couper. Il traite ces goulots d'étranglement comme des barrières de haute énergie, disant de fait : « Ne cassez pas ce fil ! »

Ce que fait (et ne fait pas) EmbedOR

Les chercheurs ont prouvé mathématiquement qu'en utilisant cette carte de courbure, Embedment peut gérer des données désordonnées et bruitées qui font trébucher les anciens outils. Ils ont montré que :

Il maintient les éléments connectés ensemble : Si deux points font partie du même fil continu dans les données d'origine, EmbedOR est très susceptible de les garder connectés dans la visualisation plate.
Il sépare les différents groupes : Si deux points appartiennent à des grappes différentes et distinctes, l'outil s'assure qu'ils restent éloignés.

Crucialement, l'article exclut l'idée que l'on puisse simplement prendre les anciens outils et espérer qu'ils fonctionnent mieux avec un petit ajustement. Les auteurs soutiennent que le simple fait d'élaguer les arêtes de « raccourci » (une méthode qu'ils ont testée dans un article précédent appelé ORC-ManL) n'est pas suffisant car cela utilise un interrupteur rigide de type « marche/arrêt ». Si un raccourci est juste à la limite du seuil, il pourrait être manqué. EmbedOR est différent car il utilise une échelle de « l'énergie » fluide basée sur la courbure, ce qui le rend beaucoup plus robuste.

La preuve est dans le pudding (et les données)

L'équipe n'a pas seulement deviné ; elle a testé cela sur des données fictives (conçues pour être difficiles, comme une forme de « Swiss Roll ») et sur des données du monde réel, incluant des images de chiffres manuscrits (MNIST) et des données de séquençage d'ARN de cellule unique (qui suit le développement des cellules).

Sur les données fictives : EmbedOR a réussi à dérouler le « Swiss Roll » sans le déchirer, alors que tSNE a échoué à le dérouler et UMAP l'a fragmenté en morceaux.
Sur les données cellulaires réelles : Lorsqu'on observe comment les cellules se développent au fil du temps, UMAP et tSNE créent souvent des « écarts » dans la chronologie, donnant l'impression que les cellules sautent d'un stade à un autre. EmbedOR maintient la chronologie lisse et continue.

Dans leurs expériences, les chercheurs ont constaté que les connexions les plus courtes selon la nouvelle carte d'EmbedOR étaient plus de 10 fois moins susceptibles de relier deux grappes différentes par rapport à une carte standard. Dans les données de cellules uniques, cette baisse était de près de 7 fois. Cela suggère que la carte d'EmbedOR est bien meilleure pour identifier quels points appartiennent réellement ensemble.

Une nouvelle façon de regarder les vieilles cartes

Voici la partie la plus cool : vous n'avez même pas besoin d'utiliser EmbedOR pour générer l'image afin d'en tirer profit. Les auteurs ont montré que vous pouvez prendre n'importe quelle visualisation (même une version désordonnée faite par UMAP) et superposer la « distance EmbedOR » par-dessus. Si vous voyez une ligne courte dans la carte EmbedOR qui semble étirée ou brisée dans l'image, vous savez que l'image a « fragmenté » les données. C'est comme avoir une boussole qui dit la vérité et qui vous indique là où la carte vous a menti.

À quel point sommes-nous sûrs ?

Les auteurs sont très confiants dans les mathématiques qui se cachent derrière les coulisses. Ils ont fourni des preuves théoriques montrant que pour un type spécifique de données bruitées, la métrique de distance d'EmbedOR crée les conditions parfaites pour une visualisation « préservant les grappes ». Ils ont prouvé que si vous choisissez les bons paramètres (spécifiquement un paramètre appelé $p$ qui contrôle la façon dont l'outil repousse les arêtes à courbure négative), l'algorithme est garanti de trouver la bonne structure avec une haute probabilité.

Cependant, ils sont aussi honnêtes quant aux limites. Leurs preuves mathématiques reposent sur un modèle spécifique de la manière dont le bruit est ajouté aux données. Bien qu'ils aient testé cela sur de nombreux ensembles de données réels et qu'ils aient constaté que cela fonctionne magnifiquement, la garantie mathématique « parfaite » s'applique au modèle théorique qu'ils ont construit. Dans le monde réel, les résultats sont démontrés empiriquement comme étant supérieurs, mais l'article ne prétend pas résoudre tous les problèmes de données existants.

En bref, EmbedOR est une façon plus intelligente d'aplatir les données du monde. Il écoute la forme des connexions, évite de briser les fils qui les maintiennent ensemble, et nous donne une image plus claire et plus honnête de la géométrie cachée dans nos données.

Résumé technique d'EmbedOR : Visualisations préservant les clusters de manière prouvable via des plongements de voisins stochastiques basés sur la courbure

Énoncé du problème

Les algorithmes de plongement de voisins stochastiques (SNE), particulièrement t-SNE et UMAP, sont largement utilisés pour la visualisation de données de haute dimension. Cependant, ils souffrent de limitations théoriques et pratiques significatives concernant la préservation de la géométrie. Plus précisément, ces méthodes échouent souvent à récupérer la géométrie sous-jacente de données de haute dimension bruitées en :

Échouant à identifier les clusters dans des données qui sont bien regroupables.
Introduisant une fragmentation, où des composantes connexes de la sous-variété de données sous-jacente sont séparées de manière spécieuse dans la visualisation.

Les garanties théoriques existantes pour t-SNE sont restreintes à des hypothèses très strictes sur les données (par exemple, des clusters sphériques et bien séparés), et aucun résultat théorique significatif n'existe pour UMAP. De plus, des études empiriques montrent que les implémentations standards violent souvent ces hypothèses, menant à des visualisations sous-optimales.

Méthodologie

Les auteurs proposent EmbedOR, un nouvel algorithme SNE qui intègre la courbure de Ricci d'Ollivier (ORC) pour construire une métrique de distance renforçant les clusters. La méthodologie se déroule en deux étapes :

Apprentissage de métrique basé sur la courbure ( $\Delta_E$ ) :
- L'algorithme construit un graphe de plus proches voisins à partir des données.
- Il calcule l'ORC pour chaque arête du graphe. L'ORC quantifie la connectivité locale ; une courbure positive indique des arêtes au sein d'une communauté hautement connectée, tandis qu'une courbure négative indique des « goulots d'étranglement » ou des arêtes reliant des clusters disjoints.
- Une fonction d'énergie $E(\kappa; p)$ est définie basée sur la courbure $\kappa$ . Cette fonction assigne une énergie élevée (pénalité) aux arêtes avec une courbure négative et une énergie faible aux arêtes avec une courbure positive.
- Une nouvelle métrique de distance par paire, $\Delta_E$ , est calculée comme la distance du plus court chemin dans le graphe pondéré, où les poids des arêtes sont le produit de la distance euclidienne et de la fonction d'énergie basée sur la courbure. Cette métrique encourage les chemins à traverser des arêtes à courbure positive (au sein des clusters) et à éviter les arêtes à courbure négative (entre les clusters).
Plongement de voisins stochastique personnalisé :
- EmbedOR utilise un cadre SNE personnalisé qui mélange des éléments de t-SNE et d'UMAP.
- Affinités de haute dimension ( $p_{ij}$ ) : Contrairement au t-SNE standard qui utilise la distance euclidienne, EmbedOR utilise la métrique $\Delta_E$ pour calculer les affinités.
- Optimisation : L'algorithme minimise une perte d'« entropie croisée floue » entre les affinités de haute dimension et les affinités de basse dimension (modélisées par une distribution t de Student). L'optimisation utilise la descente de gradient stochastique (SGD), s'appuyant sur l'efficacité computationnelle d'UMAP (en évitant la renormalisation des affinités de basse dimension) tout en conservant le calcul de similitude basé sur la perplexité de t-SNE.

Principales contributions

Extension théorique : Les auteurs prouvent que la métrique de distance d'EmbedOR étend les résultats de cohérence théorique de t-SNE (précédemment limités aux données sphériques et bien séparées) à une classe beaucoup plus large de jeux de données. Spécifiquement, ils montrent que sous un modèle de variété bruyante :
- Les distances intra-cluster sous $\Delta_E$ convergent vers la distance géodésique de la variété.
- Les distances inter-cluster sont inférieures par une valeur qui augmente avec le paramètre de répulsion $p$ .
- Par conséquent, pour un $p$ suffisamment grand, les données satisfont les conditions requises pour que t-SNE produise une visualisation préservant les clusters.
Innovation algorithmique : La proposition d'EmbedOR, qui utilise la courbure de graphe discrète pour créer une métrique de distance qui met l'accent sur la structure de cluster sous-jacente sans introduire de fragmentation.
Outil de diagnostic : La démonstration que la métrique EmbedOR peut être utilisée comme un outil post-hoc pour annoter les visualisations existantes. En visualisant les arêtes avec des distances $\Delta_E$ courtes, les utilisateurs peuvent identifier la fragmentation (où des points proches en $\Delta_E$ sont éloignés dans le plongement), fournissant un aperçu de la géométrie sous-jacente.

Résultats expérimentaux

Les auteurs ont évalué EmbedOR sur des jeux de données synthétiques et réels (incluant MNIST, Fashion-MNIST et divers jeux de données de séquençage d'ARN unicellulaire) par rapport à des bases telles que t-SNE, UMAP, PHATE, Isomap et les cartes propres de Laplacien.

Données synthétiques : EmbedOR a systématiquement démontré des performances supérieures ou égales aux meilleures méthodes pour séparer les composantes connexes sous-jacentes tout en évitant la fragmentation des chemins continus. Alors que UMAP introduisait souvent de la fragmentation et que t-SNE échouait à dérouler des structures comme le "Swiss Roll", EmbedOR maintenait l'intégrité topologique.
Données réelles (scRNA-seq) : Dans les jeux de données de trajectoires de développement et de types cellulaires, EmbedOR préservait mieux la continuité des trajectoires et la séparation des types cellulaires par rapport à UMAP et t-SNE.
Analyse de la fragmentation : L'analyse quantitative utilisant les corrélations de Spearman et les longueurs d'arêtes z-score a confirmé qu'EmbedOR étendait de manière minimale les distances entre les points considérés comme proches par la métrique $\Delta_E$ . En revanche, il a été montré que UMAP et t-SNE augmentaient significativement ces distances, indiquant une fragmentation.
Utilité de la métrique : Les expériences ont confirmé que les arêtes à courte distance $\Delta_E$ sont significativement plus susceptibles de connecter des points au sein du même cluster de vérité terrain (ou type cellulaire) que les arêtes d'un graphe k-NN standard, validant la capacité de la métrique à détecter la fragmentation dans d'autres plongements.

Signification et affirmations

L'article affirme qu'EmbedOR atteint un « équilibre délicat » entre la mise en évidence de la structure des clusters et la préservation de la continuité des variétés de données, une qualité non observée dans les méthodes de base testées.

Signification théorique : Ce travail fournit la première justification théorique de l'utilisation de métriques basées sur la courbure pour assouplir les hypothèses strictes requises pour la convergence de SNE, élargissant ainsi l'applicabilité de la préservation prouvable des clusters.
Signification pratique : EmbedOR offre une alternative robuste pour la visualisation de données de haute dimension bruitées où le maintien de l'intégrité des composantes connexes est critique (par exemple, en génomique unicellulaire).
Valeur diagnostique : Les auteurs soulignent que la métrique EmbedOR sert un double usage : elle agit à la fois comme la métrique de distance centrale pour l'algorithme et comme un outil de diagnostic pour identifier et interpréter la fragmentation dans les visualisations générées par d'autres méthodes.

Les auteurs restent modestes quant à la portée théorique, notant que leurs résultats de convergence reposent sur des instanciations spécifiques de t-SNE et que leur algorithme personnalisé mélange des éléments d'UMAP et de t-SNE. Cependant, ils soutiennent que les intuitions théoriques concernant la métrique $\Delta_E$ fournissent une forte motivation pour son efficacité en pratique.