🤖 machine learning

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

Het artikel introduceert EmbedOR, een bewijsbaar stochastisch neighbor embedding-algoritme dat discrete graafkromming incorporeert om onderliggende clusterstructuren te behouden en de schijnbare fragmentatie van continue gebieden met een hoge dichtheid te voorkomen die vaak wordt gezien bij methoden zoals UMAP en t-SNE.

Oorspronkelijke auteurs: Tristan Luca Saidi, Abigail Hickok, Bastian Rieck, Andrew J. Blumberg

Gepubliceerd 2026-07-14

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tristan Luca Saidi, Abigail Hickok, Bastian Rieck, Andrew J. Blumberg

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een gigantische, warrige bal wol hebt die een enorme dataset voorstelt. Sommige delen van de wol zijn in strakke, kleurrijke clusters aan elkaar geknoopt (zoals groepen vrienden), terwijl andere delen zich uitstrekken als lange, continue draden. Je doel is om deze 3D-bal plat te maken op een 2D-vel papier, zodat je de patronen kunt zien zonder dat de wol hopeloos in de knoop raakt of uit elkaar wordt gescheurd.

Jarenlang waren de populaire tools voor deze taak — genaamd tSNE en UMAP — als enthousiaste maar onhandige kinderen die proberen de wol plat te maken. Ze doen vaak een goed werk bij het scheiden van de kleurrijke clusters, maar ze hebben de nare gewoonte om de lange, continue draden door te snappen. Ze kunnen een enkel, vloeiend pad van data nemen en dit in drie of vier losse eilanden uiteenrijten, waardoor het lijkt alsof de data in stukken is gebroken terwijl het eigenlijk allemaal verbonden is. Ze missen soms ook de clusters in de eerste plaats als de data niet perfect rond en netjes is.

Maak kennis met EmbedOR, een nieuwe tool ontworpen door onderzoekers Tristan Luca Saidi, Abigail Hickok, Bastian Rieck en Andrew J. Blumberg. Zie EmbedOR als een "krommings-voelende" schaar. Voordat het de wol knipt of platdrukt, meet het de "buigzaamheid" van elke verbinding.

De magie van "buigzaamheid" (Kromming)

Het geheime ingrediënt in EmbedOR is iets dat Ollivier-Ricci-kromming wordt genoemd. Stel je voor dat je door een drukke feestzaal loopt.

Als je in een hechte groep vrienden bent waar iedereen iedereen kent, is de "kromming" positief. Het voelt als een gezellige, verbonden gemeenschap.
Als je op een smalle brug staat die twee verschillende kamers verbindt, is de "kromming" negatief. Het voelt als een flessenhals; als je van de brug stapt, val je in een andere wereld.

Oude tools (tSNE en UMAP) keken vooral naar hoe dicht mensen bij elkaar stonden in de kamer. EmbedOR kijkt echter naar de vorm van de menigte. Het weet dat een "negatieve buiging" (een flessenhals) een gevaarlijke plek is om te snijden. Het behandelt deze flessenhalzen als hoogenergetische barrières, wat effectief zegt: "Sla deze draad niet door!"

Wat EmbedOR wel (en niet) doet

De onderzoekers hebben wiskundig bewezen dat EmbedOR, door gebruik te maken van deze krommingskaart, rommelige, ruisgevoelige data kan afhandelen waar de oude tools over struikelen. Ze toonden aan dat:

Het verbonden dingen bij elkaar houdt: Als twee punten deel uitmaken van dezelfde continue draad in de oorspronkelijke data, is de kans groot dat EmbedOR ze in de platte visualisatie verbonden houdt.
Het verschillende groepen scheidt: Als twee punten bij verschillende, gescheiden clusters horen, zorgt de tool ervoor dat ze ver van elkaar blijven.

Cruciaal is dat het artikel uitsluit dat je de oude tools simpelweg kunt gebruiken en er dan op kunt hopen dat ze beter werken met een beetje aanpassing. De auteurs beargumenteren dat het simpelweg wegknippen van "shortcut"-randen (een methode die ze in een eerder artikel genaamd ORC-ManL probeerden) niet voldoende is, omdat dit een rigide "aan/uit"-schakelaar gebruikt. Als een shortcut net op de grens van de drempelwaarde ligt, kan deze worden gemist. EmbedOR is anders omdat het een vloeiende, glijdende schaal van "energie" gebruikt op basis van kromming, waardoor het veel robuuster is.

Het bewijs zit in de pudding (en de data)

Het team heeft niet alleen geraden; ze hebben getest op zowel nepdata (ontworpen om lastig te zijn, zoals een "Swiss Roll"-vorm) als echte data, waaronder afbeeldingen van handgeschreven cijfers (MNIST) en single-cell RNA-sequencing data (die bijhoudt hoe cellen zich ontwikkelen).

Op de nepdata: EmbedOR slaagde erin de "Swiss Roll" uit te rollen zonder deze te scheuren, terwijl tSNE faalde om de Swiss Roll uit te rollen en UMAP deze in fragmenten hakte.
Op echte celdata: Wanneer men kijkt naar hoe cellen zich in de loop van de tijd ontwikkelen, creëren UMAP en tSNE vaak "gaten" in de tijdlijn, waardoor het lijkt alsof de cellen van de ene fase naar de andere springen. EmbedOR hield de tijdlijn vloeiend en continu.

In hun experimenten vonden de onderzoekers dat de kortste verbindingen volgens de nieuwe kaart van EmbedOR meer dan 10 keer minder waarschijnlijk waren om twee verschillende clusters te overbruggen vergeleken met een standaard kaart. In de single-cell data was deze daling bijna 7-voudig. Dit suggereert dat de kaart van EmbedOR veel beter is in het identificeren van welke punten echt bij elkaar horen.

Een nieuwe manier om naar oude kaarten te kijken

Hier komt het coolste gedeelte: je hoeft niet eens EmbedOR te gebruiken om de afbeelding te genereren om het voordeel te krijgen. De auteurs hebben aangetoond dat je elke visualisatie (zelfs een rommelige gemaakt door UMAP) kunt nemen en de "EmbedOR-afstand" daaroverheen kunt leggen. Als je een korte lijn ziet in de EmbedOR-kaart die er in de afbeelding uitgerekt of gebroken uitziet, weet je dat de afbeelding de data heeft "gefragmenteerd". Het is alsof je een waarheidsgetrouwe kompas hebt dat aanwijst waar de kaart je heeft voorgelogen.

Hoe zeker zijn we?

De auteurs zijn zeer zelfverzekerd over de wiskunde achter de schermen. Ze hebben theoretische bewijzen geleverd die aantonen dat voor een specifiek type ruisgevoelige data, de EmbedOR-afstandsmethode de perfecte omstandigheden creëert voor een "cluster-behoudende" visualisatie. Ze bewezen dat als je de juiste instellingen kiest (specifiek een parameter genaamd $p$ die bepaalt hoeveel de tool negatief-gekromde randen afstoot), het algoritme met hoge waarschijnlijkheid de juiste structuur zal vinden.

Ze zijn echter ook eerlijk over de beperkingen. Hun wiskundige bewijzen vertrouwen op een specifiek model van hoe ruis aan de data wordt toegevoegd. Hoewel ze dit op veel echte datasets hebben getest en zagen dat het prachtig werkt, geldt het "perfecte" wiskundige bewijs voor het theoretische model dat ze hebben gebouwd. In de echte wereld worden de resultaten empirisch gedemonstreerd als superieur, maar het artikel beweert niet dat het elk mogelijke dataprobleem in het bestaan oplost.

Kortom, EmbedOR is een slimmere manier om de wereld van data plat te maken. Het luistert naar de vorm van de verbindingen, vermijdt het doorsnijden van de draden die alles bij elkaar houden, en geeft ons een duidelijker en eerlijker beeld van de verborgen geometrie in onze data.

Technische Samenvatting van EmbedOR: Bewijsbaar Cluster-behoudende Visualisaties met op Kromming Gebaseerde Stochastic Neighbor Embeddings

Probleemstelling

Stochastische Neighbor Embedding (SNE) algoritmen, met name t-SNE en UMAP, worden veelvuldig gebruikt voor het visualiseren van hoogdimensionele data. Ze lijden echter aan significante theoretische en praktische beperkingen met betrekking tot het behoud van geometrie. Specifiek schieten deze methoden vaak tekort in het herstellen van de onderliggende geometrie van ruizige, hoogdimensionele data door:

Het niet identificeren van clusters in data die goed clusterbaar is.
Het introduceren van fragmentatie, waarbij verbonden componenten van de onderliggende datamanifold onterecht gescheiden worden in de visualisatie.

Bestaande theoretische garanties voor t-SNE zijn beperkt tot zeer strikte aannames over data (bijv. sferische en goed gescheiden clusters), en er bestaan geen significante theoretische resultaten voor UMAP. Bovendien laten empirische studies zien dat standaard implementaties deze aannames vaak schenden, wat leidt tot suboptimale visualisaties.

Methodologie

De auteurs stellen EmbedOR voor, een nieuw SNE-algoritme dat Ollivier-Ricci-kromming (ORC) integreert om een cluster-verbeterende afstandmetriek te construeren. De methodologie verloopt in twee fasen:

Op kromming gebaseerde metrieklering ( $\Delta_E$ ):
- Het algoritme construeert een nearest-neighbor graaf van de data.
- Het berekent de ORC voor elke rand in de graaf. ORC kwantificeert lokale connectiviteit; positieve kromming duidt op randen binnen een hoog verbonden gemeenschap, terwijl negatieve kromming "bottlenecks" of randen aangeeft die verschillende clusters overbruggen.
- Een energiefunctie $E(\kappa; p)$ wordt gedefinieerd op basis van de kromming $\kappa$ . Deze functie wijst een hoge "energie" (straf) toe aan randen met een negatieve kromming en een lage energie aan randen met een positieve kromming.
- Een nieuwe paargewijze afstandmetriek, $\Delta_E$ , wordt berekend als de kortste padafstand in de gewogen graaf, waarbij de randgewichten het product zijn van de Euclidische afstand en de op kromming gebaseerde energiefunctie. Deze metriek moedigt paden aan om positief gekromde randen te volgen (binnen clusters) en negatief gekromde randen te vermijden (tussen clusters).
Custom Stochastic Neighbor Embedding:
- EmbedOR maakt gebruik van een aangepast SNE-framework dat elementen van t-SNE en UMAP combineert.
- Hoogdimensionele affiniteiten ( $p_{ij}$ ): In tegenstelling tot standaard t-SNE die de Euclidische afstand gebruikt, gebruikt EmbedOR de $\Delta_E$ -metriek om affiniteiten te berekenen.
- Optimalisatie: Het algoritme minimaliseert een "fuzzy cross-entropy" verlies tussen de hoogdimensionele affiniteiten en de laagdimensionele affiniteiten (gemodelleerd door een Student t-distributie). De optimalisatie maakt gebruik van stochastic gradient descent (SGD), waarbij het profiteert van de computationele efficiëntie van UMAP (het vermijden van her-normalisatie van laagdimensionele affiniteiten) terwijl het de perplexity-gebaseerde gelijkenisberekening van t-SNE behoudt.

Belangrijkste Bijdragen

Theoretische Uitbreiding: De auteurs bewijzen dat de EmbedOR afstandmetriek de theoretische consistentieresultaten van t-SNE (voorheen beperkt tot sferische, goed gescheiden data) uitbreidt naar een veel bredere klasse van datasets. Specifiek tonen zij aan dat onder een ruisig manifold-model:
- Intra-cluster afstanden onder $\Delta_E$ convergeren naar de manifold geodetische afstand.
- Inter-cluster afstanden ondergrenzen hebben die toenemen met de repulsieparameter $p$ .
- Consequentelijk voldoet de data voor een voldoende grote $p$ aan de voorwaarden die vereist zijn voor t-SNE om een cluster-behoudende visualisatie te produceren.
Algoritmische Innovatie: Het voorstel van EmbedOR, dat discrete graafkromming gebruikt om een afstandmetriek te creëren die de onderliggende clusterstructuur benadrukt zonder fragmentatie te introduceren.
Diagnostisch Instrument: De demonstratie dat de EmbedOR-metriek kan worden gebruikt als een post-hoc instrument om bestaande visualisaties te annoteren. Door randen met korte $\Delta_E$ -afstanden te visualiseren, kunnen gebruikers fragmentatie identificeren (waar punten dichtbij in $\Delta_E$ ver weg zijn in de embedding), wat inzicht biedt in de onderliggende geometrie.

Experimentele Resultaten

De auteurs evalueerden EmbedOR op zowel synthetische als real-world datasets (inclusief MNIST, Fashion-MNIST en diverse single-cell RNA sequencing datasets) tegen baselines zoals t-SNE, UMAP, PHATE, Isomap en Laplacian Eigenmaps.

Synthetische Data: EmbedOR demonstreerde consistent superieure of gelijkwaardige prestaties bij het scheiden van onderliggende verbonden componenten terwijl de fragmentatie van continue paden werd vermeden. Terwijl UMAP vaak fragmentatie introduceerde en t-SNE er niet in slaagde structuren zoals de Swiss Roll uit te rollen, behield EmbedOR de topologische integriteit.
Real Data (scRNA-seq): In datasets met ontwikkelings-trajecten en celtypen behield EmbedOR beter de continuïteit van trajecten en de scheiding van celtypen vergeleken met UMAP en t-SNE.
Fragmentatie-analyse: Kwantitatieve analyse met behulp van Spearman-correlaties en z-gescorede randlengtes bevestigde dat EmbedOR de afstanden tussen punten die als dichtbij worden beschouwd door de $\Delta_E$ -metriek minimaal vergroot. In contrast hiermee vertoonden UMAP en t-SNE significante expansie van deze afstanden, wat duidt op fragmentatie.
Nut van de Metriek: Experimenten bevestigden dat korte $\Delta_E$ -randen aanzienlijk vaker punten verbinden binnen hetzelfde grondwaarheid-cluster (of celtype) dan randen in een standaard k-NN graaf, wat de capaciteit van de metriek valideert om fragmentatie in andere embeddings te detecteren.

Betekenis en Claims

Het artikel claimt dat EmbedOR een "delicaat evenwicht" bereikt tussen het benadrukken van de clusterstructuur en het behouden van de continuïteit van datamanifolds, een kwaliteit die niet werd waargenomen bij de geteste baseline-methoden.

Theoretische Betekenis: Het werk biedt de eerste theoretische rechtvaardiging voor het gebruik van kromming-gebaseerde metrieken om de strikte aannames die vereist zijn voor SNE-convergentie te versoepelen, waardoor de toepasbaarheid van bewijsbaar cluster-behoud wordt vergroot.
Praktische Betekenis: EmbedOR biedt een robuust alternatief voor het visualiseren van ruisige, hoogdimensionele data waarbij het behoud van de integriteit van verbonden componenten cruciaal is (bijv. in single-cell genomics).
Diagnostische Waarde: De auteurs benadrukken dat de EmbedOR-metriek een tweeledig doel dient: het fungeert als de kern-afstandmetriek voor het algoritme en als een diagnostisch instrument om fragmentatie in visualisaties gegenereerd door andere methoden te identificeren en te interpreteren.

De auteurs blijven bescheiden over de theoretische reikwijdte, waarbij zij opmerken dat hun convergentieresultaten steunen op specifieke instantiaties van t-SNE en dat hun aangepaste algoritme elementen van UMAP en t-SNE combineert. Zij argumenteren echter dat de theoretische inzichten met betrekking tot de $\Delta_E$ -metriek een sterke motivatie bieden voor de effectiviteit ervan in de praktijk.