🤖 machine learning

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

The paper introduces EmbedOR, a provable stochastic neighbor embedding algorithm that incorporates discrete graph curvature to preserve underlying cluster structures and prevent the spurious fragmentation of continuous high-density regions often seen in methods like UMAP and t-SNE.

Original authors: Tristan Luca Saidi, Abigail Hickok, Bastian Rieck, Andrew J. Blumberg

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tristan Luca Saidi, Abigail Hickok, Bastian Rieck, Andrew J. Blumberg

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, tangled ball of yarn representing a massive dataset. Some parts of the yarn are knotted together in tight, colorful clusters (like groups of friends), while other parts stretch out into long, continuous threads. Your goal is to flatten this 3D ball onto a 2D piece of paper so you can see the patterns without the yarn getting hopelessly knotted or ripped apart.

For years, the popular tools for this job—called tSNE and UMAP—have been like enthusiastic but clumsy kids trying to flatten the yarn. They often do a great job of separating the colorful clusters, but they have a nasty habit of snapping the long, continuous threads. They might take a single, smooth path of data and tear it into three or four disconnected islands, making it look like the data has broken into pieces when it's actually all connected. They also sometimes fail to spot the clusters in the first place if the data isn't perfectly round and tidy.

Enter EmbedOR, a new tool designed by researchers Tristan Luca Saidi, Abigail Hickok, Bastian Rieck, and Andrew J. Blumberg. Think of EmbedOR as a "curvature-sensing" pair of scissors. Before it cuts or flattens the yarn, it measures the "bendiness" of every connection.

The Magic of "Bendiness" (Curvature)

The secret sauce in EmbedOR is something called Ollivier-Ricci curvature. Imagine walking through a crowded party.

If you are in a tight group of friends where everyone knows everyone, the "curvature" is positive. It feels like a cozy, connected community.
If you are standing on a narrow bridge connecting two different rooms, the "curvature" is negative. It feels like a bottleneck; if you step off the bridge, you fall into a different world.

Old tools (tSNE and UMAP) mostly just looked at how close people were standing to each other in the room. EmbedOR, however, looks at the shape of the crowd. It knows that a "negative bend" (a bottleneck) is a dangerous place to cut. It treats these bottlenecks as high-energy barriers, effectively saying, "Do not snap this thread!"

What EmbedOR Does (and Doesn't Do)

The researchers proved mathematically that by using this curvature map, EmbedOR can handle messy, noisy data that trips up the old tools. They showed that:

It keeps connected things together: If two points are part of the same continuous thread in the original data, EmbedOR is highly likely to keep them connected in the flat visualization.
It separates different groups: If two points belong to different, separate clusters, the tool makes sure they stay far apart.

Crucially, the paper rules out the idea that you can just take the old tools and hope they work better with a little tweaking. The authors argue that simply pruning "shortcut" edges (a method they tried in a previous paper called ORC-ManL) isn't enough because it uses a rigid "on/off" switch. If a shortcut is just barely on the edge of the threshold, it might get missed. EmbedOR is different because it uses a smooth, sliding scale of "energy" based on curvature, making it much more robust.

The Proof is in the Pudding (and the Data)

The team didn't just guess; they tested this on both fake data (designed to be tricky, like a "Swiss Roll" shape) and real-world data, including images of handwritten digits (MNIST) and single-cell RNA sequencing data (which tracks how cells develop).

On the fake data: EmbedOR successfully unrolled the "Swiss Roll" without tearing it, whereas tSNE failed to unroll it and UMAP chopped it into fragments.
On real cell data: When looking at how cells develop over time, UMAP and tSNE often created "gaps" in the timeline, making it look like the cells jumped from one stage to another. EmbedOR kept the timeline smooth and continuous.

In their experiments, the researchers found that the shortest connections according to EmbedOR's new map were more than 10 times less likely to bridge two different clusters compared to a standard map. In the single-cell data, this drop was nearly 7-fold. This suggests that EmbedOR's map is much better at identifying which points truly belong together.

A New Way to Look at Old Maps

Here is the coolest part: You don't even have to use EmbedOR to generate the picture to get the benefit. The authors showed that you can take any visualization (even a messy one made by UMAP) and overlay the "EmbedOR distance" on top of it. If you see a short line in the EmbedOR map that looks stretched out or broken in the picture, you know that the picture has "fragmented" the data. It's like having a truth-telling compass that points out where the map has lied to you.

How Sure Are We?

The authors are very confident in the math behind the scenes. They provided theoretical proofs showing that for a specific type of noisy data, EmbedOR's distance metric creates the perfect conditions for a "cluster-preserving" visualization. They proved that if you choose the right settings (specifically a parameter called $p$ that controls how much the tool repels negative-curvature edges), the algorithm is guaranteed to find the right structure with high probability.

However, they are also honest about the limits. Their mathematical proofs rely on a specific model of how noise is added to the data. While they tested this on many real-world datasets and found it works beautifully, the "perfect" mathematical guarantee applies to the theoretical model they built. In the real world, the results are empirically demonstrated to be superior, but the paper doesn't claim it solves every possible data problem in existence.

In short, EmbedOR is a smarter way to flatten the world's data. It listens to the shape of the connections, avoids snapping the threads that hold things together, and gives us a clearer, more honest picture of the hidden geometry in our data.

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

Problem Statement

Stochastic Neighbor Embedding (SNE) algorithms, particularly t-SNE and UMAP, are widely used for visualizing high-dimensional data. However, they suffer from significant theoretical and practical limitations regarding geometry preservation. Specifically, these methods often fail to recover the underlying geometry of noisy, high-dimensional data by either:

Failing to identify clusters in data that is well-clusterable.
Introducing fragmentation, where connected components of the underlying data submanifold are spuriously separated in the visualization.

Existing theoretical guarantees for t-SNE are restricted to very stringent assumptions about data (e.g., spherical and well-separated clusters), and no significant theoretical results exist for UMAP. Furthermore, empirical studies show that standard implementations often violate these assumptions, leading to suboptimal visualizations.

Methodology

The authors propose EmbedOR, a novel SNE algorithm that integrates Ollivier-Ricci Curvature (ORC) to construct a cluster-enhancing distance metric. The methodology proceeds in two stages:

Curvature-Based Metric Learning ( $\Delta_E$ ):
- The algorithm constructs a nearest-neighbor graph from the data.
- It computes the ORC for each edge in the graph. ORC quantifies local connectivity; positive curvature indicates edges within a highly connected community, while negative curvature indicates "bottlenecks" or edges bridging disjoint clusters.
- An energy function $E(\kappa; p)$ is defined based on the curvature $\kappa$ . This function assigns high "energy" (penalty) to edges with negative curvature and low energy to positive curvature edges.
- A new pairwise distance metric, $\Delta_E$ , is calculated as the shortest path distance in the weighted graph, where edge weights are the product of the Euclidean distance and the curvature-based energy function. This metric encourages paths to traverse positive-curvature edges (within clusters) and avoid negative-curvature edges (between clusters).
Custom Stochastic Neighbor Embedding:
- EmbedOR utilizes a custom SNE framework that blends elements of t-SNE and UMAP.
- High-dimensional affinities ( $p_{ij}$ ): Unlike standard t-SNE which uses Euclidean distance, EmbedOR uses the $\Delta_E$ metric to compute affinities.
- Optimization: The algorithm minimizes a "fuzzy cross-entropy" loss between the high-dimensional affinities and low-dimensional affinities (modeled by a Student t-distribution). The optimization uses stochastic gradient descent (SGD), drawing on UMAP's computational efficiency (avoiding re-normalization of low-dimensional affinities) while retaining t-SNE's perplexity-based similarity calculation.

Key Contributions

Theoretical Extension: The authors prove that the EmbedOR distance metric extends the theoretical consistency results of t-SNE (previously limited to spherical, well-separated data) to a much broader class of datasets. Specifically, they show that under a noisy manifold model:
- Intra-cluster distances under $\Delta_E$ converge to the manifold geodesic distance.
- Inter-cluster distances are lower-bounded by a value that increases with the repulsion parameter $p$ .
- Consequently, for sufficiently large $p$ , the data satisfies the conditions required for t-SNE to produce a cluster-preserving visualization.
Algorithmic Innovation: The proposal of EmbedOR, which uses discrete graph curvature to create a distance metric that emphasizes underlying cluster structure without introducing fragmentation.
Diagnostic Tool: The demonstration that the EmbedOR metric can be used as a post-hoc tool to annotate existing visualizations. By visualizing edges with short $\Delta_E$ distances, users can identify fragmentation (where points close in $\Delta_E$ are far in the embedding), providing insight into the underlying geometry.

Experimental Results

The authors evaluated EmbedOR on both synthetic and real-world datasets (including MNIST, Fashion-MNIST, and various single-cell RNA sequencing datasets) against baselines such as t-SNE, UMAP, PHATE, Isomap, and Laplacian Eigenmaps.

Synthetic Data: EmbedOR consistently demonstrated superior or tied-for-best performance in separating underlying connected components while avoiding the fragmentation of continuous paths. While UMAP often introduced fragmentation and t-SNE failed to unroll structures like the Swiss Roll, EmbedOR maintained topological integrity.
Real Data (scRNA-seq): In developmental trajectory and cell-type datasets, EmbedOR better preserved the continuity of trajectories and the separation of cell types compared to UMAP and t-SNE.
Fragmentation Analysis: Quantitative analysis using Spearman correlations and z-scored edge lengths confirmed that EmbedOR minimally expands distances between points deemed close by the $\Delta_E$ metric. In contrast, UMAP and t-SNE were shown to significantly expand these distances, indicating fragmentation.
Metric Utility: Experiments confirmed that short $\Delta_E$ edges are significantly more likely to connect points within the same ground-truth cluster (or cell type) than edges in a standard k-NN graph, validating the metric's ability to detect fragmentation in other embeddings.

Significance and Claims

The paper claims that EmbedOR achieves a "delicate balance" between highlighting cluster structure and preserving the continuity of data manifolds, a quality not observed in the tested baseline methods.

Theoretical Significance: The work provides the first theoretical justification for using curvature-based metrics to relax the strict assumptions required for SNE convergence, thereby broadening the applicability of provable cluster preservation.
Practical Significance: EmbedOR offers a robust alternative for visualizing noisy, high-dimensional data where maintaining the integrity of connected components is critical (e.g., in single-cell genomics).
Diagnostic Value: The authors emphasize that the EmbedOR metric serves a dual purpose: it acts as the core distance metric for the algorithm and as a diagnostic tool to identify and interpret fragmentation in visualizations generated by other methods.

The authors remain modest regarding the theoretical scope, noting that their convergence results rely on specific instantiations of t-SNE and that their custom algorithm blends UMAP and t-SNE elements. However, they argue that the theoretical insights regarding the metric $\Delta_E$ provide a strong motivation for its effectiveness in practice.