📊 statistics

Cluster and then Embed: A Modular Approach for Visualization

This paper proposes a transparent, modular visualization framework that improves upon methods like t-SNE and UMAP by sequentially clustering data, embedding each cluster individually, and then aligning them to preserve both local structure and global geometry.

Original authors: Elizabeth Coda, Ery Arias-Castro, Gal Mishne

Published 2026-07-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Elizabeth Coda, Ery Arias-Castro, Gal Mishne

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, messy box of 3D LEGO sculptures. Some are tiny, intricate castles; others are sprawling, flat cities. Your goal is to take photos of all of them and lay them out on a flat 2D table so you can see how they relate to each other.

The problem? If you just squish the whole box onto the table at once, the flat cities get crushed, and the castles overlap into a giant, confusing blob. This is the "crowding problem" that plagues popular tools like t-SNE and UMAP. They are great at keeping the tiny details of each castle together, but they often distort the map, making distant castles look like they are right next to each other.

Enter the Cluster+Embed (C+E) approach, a new method proposed by Elizabeth Coda, Ery Arias-Castro, and Gal Mishne. Think of this method not as a single magic camera, but as a three-step assembly line that treats your data like a collection of distinct neighborhoods.

Step 1: The Neighborhood Sort

First, the method doesn't try to photograph the whole box at once. Instead, it acts like a super-organized librarian who sorts the LEGO sculptures into separate piles based on their shape. If you have a pile of castles and a pile of cities, they get separated into different bins. The authors note that you can use any sorting method you like (like the popular Leiden or DBSCAN algorithms), but the key is that you define the groups before you take the picture.

Step 2: The Individual Photos

Next, the method takes a photo of each pile individually. Because the librarian is only looking at one pile of castles at a time, they can arrange the castles perfectly to show their intricate details without worrying about the cities getting in the way. This step uses standard tools (like PCA or TriMap) to flatten just that one group. The result? A crystal-clear, high-quality photo of the castles, and a separate, equally clear photo of the cities.

Step 3: The Global Map

Here is the clever part. Now you have a stack of perfect, separate photos. The final step is to tape these photos onto a giant wall to make one big map. But instead of just gluing them randomly, the method uses a "rigid transformation"—imagine picking up a whole photo of the castle pile and sliding it, rotating it, or flipping it, but never stretching or squishing the photo itself.

The goal is to position these piles so that the distance between the "castle pile" and the "city pile" on the wall matches the distance they had in the original box. To solve the crowding problem (where there isn't enough room on the wall for everything), the method introduces a "scaling knob" (called $\alpha$ ). If the piles are too close and might overlap, the authors suggest turning this knob to gently push the piles apart, creating just enough space for everyone to be seen clearly without distorting the internal details of the photos.

What This Method Says "No" To

The authors are very clear about what they are fighting against. They argue against the idea that a single, all-in-one tool (like t-SNE or UMAP) can perfectly do two contradictory things at once: keep the tiny local details perfect and keep the global distances accurate. They show that while t-SNE is great at separating clusters, it often distorts the "map" so much that you can't trust the distances between the groups. They also explicitly rule out the idea that you can just force a hierarchical tree onto a map without a structured process; their method is a deliberate, transparent three-step pipeline, not a black box.

How Sure Are They?

The authors don't claim this is a magic bullet that solves everything forever. Instead, they present strong evidence from simulations and real-world data.

On Synthetic Data: They tested their method on a 10-dimensional Gaussian mixture model with 5,000 points. In these simulations, they showed that with a scaling factor of $\alpha = 2$ , their method avoided the overlap that plagued other methods, creating a ring of clusters that looked very similar to t-SNE but was achieved through a transparent, controllable process.
On Real Data: They applied this to three real datasets:
1. MNIST (Handwritten Digits): A dataset of 60,000 images. Here, C+E successfully separated the digits into groups (like fours and nines being close) and preserved the global structure better than t-SNE, which tended to space everything out equally.
2. Human Brain Organoids: A dataset of 20,272 cells. The method revealed a clear "developmental trajectory" (a path of growth over time) that was visible in their map but was more "discrete" and less continuous in t-SNE and UMAP.
3. Mouse Cortex: A dataset of 23,822 cells. Here, C+E revealed a "coarse-to-fine" structure (big groups breaking down into smaller ones) that other methods missed.

The authors admit there is a trade-off. While C+E is excellent at preserving global distances and local shapes, it sometimes struggles to match t-SNE's ability to keep the very nearest neighbors (kNN recall) perfect for small values of $k$ . They suggest this is because t-SNE has a mysterious way of breaking data into tiny patches that C+E doesn't replicate. However, they argue that for a visualization that is both transparent and faithful to the overall shape of the data, C+E is a highly competitive and much more understandable alternative.

In short, the paper suggests that by breaking the problem into "sort, flatten, then align," we can get a map that doesn't lie about where things are, even if it takes a few more steps to get there.

Technical Summary: Cluster and then Embed: A Modular Approach for Visualization

Problem Statement

Dimensionality reduction methods, particularly t-SNE and UMAP, are widely used for visualizing high-dimensional data with latent clustered structures. While these methods effectively group data points and preserve local information, they are known to distort the global geometry of the underlying data. Specifically, they often fail to preserve the relative positions, distances, and sizes of different clusters. This limitation stems from the "crowding problem," where low-dimensional embedding spaces lack sufficient capacity to accommodate all points at their original high-dimensional distance scales, leading to the collapse of distant points and the overlap of distinct clusters. Existing methods often force a trade-off between preserving local structure (separating clusters) and preserving global distances.

Methodology: The Cluster+Embed (C+E) Framework

The authors propose a modular, three-step framework called Cluster+Embed (C+E) to address the trade-off between local and global fidelity. The approach decouples clustering, local embedding, and global alignment, allowing the analyst to select specific algorithms for each stage based on their visualization goals.

Step 1: Clustering

The data $\{x_i\}_{i=1}^n$ is first partitioned into $\kappa$ clusters ( $C_1, \dots, C_\kappa$ ) using any chosen clustering algorithm (e.g., Leiden, DBSCAN, k-means). This step explicitly reveals the cluster structure present in the data. Points identified as noise can be discarded at this stage.

Step 2: Individual Cluster Embedding

Each cluster $C_l$ is embedded separately into a low-dimensional space (typically $\mathbb{R}^2$ ) using a chosen embedding method (e.g., PCA, Isomap, TriMap).

Rationale: Embedding clusters individually reduces distortion compared to embedding the entire dataset at once, as the "crowding problem" is mitigated within smaller, localized subsets.
Scaling: If the embedding method relies on ordinal information, a scaling factor $\gamma_l$ is applied to each cluster to minimize the quadratic loss between embedded distances and original dissimilarities.

Step 3: Global Alignment

The embedded clusters are aligned into a single global embedding using only rigid transformations (translations, rotations, and reflections). The goal is to position the clusters relative to one another such that the pairwise dissimilarities between points in different clusters are preserved as faithfully as possible.

Optimization: The alignment minimizes a stress function (Kruskal's stress) defined as:
$\min_{T_1, \dots, T_\kappa} \sum_{1 \le i < j \le \kappa} \sum_{l \in C_i} \sum_{m \in C_j} (\delta_{lm} - \|T_i(y_l) - T_j(y_m)\|)^2$
where $\delta_{lm}$ is the original dissimilarity and $T$ represents rigid transformations.
Crowding Mitigation via Scaling ( $\alpha$ ): To prevent overlap in the final visualization, the authors introduce a tuning parameter $\alpha \ge 1$ $α \geq 1$ . The target distance between clusters is scaled to $\alpha \delta_{lm}$ $α δ_{l m}$ . This effectively inflates the space between clusters in the low-dimensional map, avoiding the crowding problem.
- $\alpha$ can be tuned manually or automatically. An automatic heuristic is proposed: $\alpha = \max(1, \frac{\kappa \tau}{2\pi \Delta})$ , where $\tau$ is the average cluster diameter and $\Delta$ is the average inter-cluster distance.

Key Contributions

Modular Framework: The paper introduces a transparent, modular approach where clustering, embedding, and alignment are distinct steps. This allows users to choose specific algorithms for each stage to target specific visualization properties (e.g., using TriMap for kNN recall or PCA for distance preservation).
Explicit Control over Global Geometry: Unlike t-SNE and UMAP, which implicitly and often opaquely handle global structure through force-directed dynamics, C+E explicitly optimizes for the preservation of inter-cluster distances via rigid alignment.
Solution to the Crowding Problem: The method addresses the crowding problem not by altering the kernel (as t-SNE does with the Cauchy kernel) but by explicitly scaling inter-cluster distances via the parameter $\alpha$ , ensuring distinct clusters do not overlap while maintaining their relative organization.
Transparency: The approach is more interpretable than end-to-end methods because the preservation of local structure (within clusters) and global structure (between clusters) are handled by separate, controllable mechanisms.

Experimental Results

The authors evaluated C+E on synthetic and real-world datasets (MNIST, human brain organoid data, mouse cortex data) against baselines including t-SNE, UMAP, PCA, Isomap, PHATE, and TriMap.

Synthetic Shapes Dataset: C+E achieved perfect local metrics (recovering exact cluster configurations) and maintained global orientation, whereas t-SNE and UMAP introduced significant local distortion.
MNIST: C+E successfully separated clusters and organized them into meaningful groupings (e.g., grouping similar digits). While t-SNE showed superior kNN recall for small $k$ , C+E outperformed t-SNE and UMAP on global metrics (class preservation and inter-cluster distance preservation).
Human Brain Organoid Data: C+E embeddings revealed a clear temporal developmental trajectory and distinct cell-type groupings. It preserved global metrics comparable to or better than PCA and L-Isomap while offering improved local structure and less collapse than t-SNE or UMAP.
Mouse Cortex Data: C+E revealed a coarse-to-fine structure (separating inhibitory/excitatory neurons and non-neurons) that was not present in other methods. While the scale of the embedding was inflated (leading to higher normalized stress), scale-invariant global metrics favored C+E over UMAP and t-SNE.

Significance and Claims

The paper claims that C+E offers a competitive alternative to existing visualization methods by striking a balance between faithful local embeddings and a faithful global organization.

Trade-off Management: The method acknowledges the inherent trade-off between local and global preservation but provides a mechanism (the parameter $\alpha$ ) to explicitly manage this trade-off.
Flexibility: The framework allows users to prioritize specific metrics (e.g., kNN recall via TriMap or distance preservation via PCA) without sacrificing the global arrangement of clusters.
Limitations: The authors modestly note that t-SNE remains the state-of-the-art for maximizing kNN recall for small $k$ . They suggest that C+E's kNN recall can be improved by increasing $\alpha$ or creating more clusters, though this risks introducing false clusters. The computational complexity of the alignment step scales quadratically with the number of points, though subsampling strategies are employed to mitigate this.

In conclusion, the authors argue that C+E provides a more transparent and controllable approach to visualizing clustered data, preserving both the internal geometry of clusters and the relative positioning of the clusters themselves, which is often lost in popular nonlinear dimensionality reduction techniques.