ScaleMAP: Preserving Local Density and Neighborhood Structure in Low-Dimensional Embeddings

Technical Summary: ScaleMAP

Problem Statement
Nonlinear dimensionality reduction (DR) methods, particularly UMAP, PaCMAP, and t-SNE, are standard tools for exploratory analysis of high-dimensional data. These methods construct approximate $k$-nearest-neighbor (kNN) graphs and normalize local distances using adaptive bandwidths to handle varying local densities. While this normalization ensures robustness to density variations, it inadvertently erases the absolute scale of neighborhoods. Consequently, these methods fail to preserve the relative sizes of clusters and suppress sparse structures, such as bridges between transitioning cell types, narrow spectral spikes in hyperspectral images, or density variations spanning many orders of magnitude (e.g., in flow cytometry).

Existing attempts to correct this, such as DensMAP, introduce a penalty term to the loss function to maximize the correlation between original-space and embedding-space local densities. However, the paper argues that this approach creates a competing objective: the density penalty fights against UMAP's inherent attraction–repulsion forces. This conflict scatters points away from their true neighborhoods, leading to a high fraction of "disconnected points" and making sparse regions difficult to interpret.

Methodology
ScaleMAP proposes a different approach: rather than adding a competing loss term, it reintroduces scale information through a change of variables applied to the distance metric within the existing UMAP objective.

1. Local Radius Definition: ScaleMAP utilizes the "local radius" ($r_i$), a weighted root-mean-square distance from a point to its neighbors in the original space, as a measure of neighborhood scale.
2. Rescaled Distance: Instead of using the Euclidean squared distance $d_{ij}^2 = \|y_i - y_j\|^2$ in the loss function, ScaleMAP defines a rescaled squared distance:
   $$\tilde{d}_{ij}^2 = \frac{d_{ij}^2}{r_i r_j}$$
   where $r_i$ and $r_j$ are the local radii of the two endpoints.
3. Force Modification: This substitution modifies the gradient of the cross-entropy loss. The update rules for both attractive (neighbor) and repulsive (non-neighbor) forces are scaled by a factor of $1/(r_i r_j)$.
   • Symmetry: Crucially, the rescaling applies symmetrically to both attractive and repulsive forces. This preserves the local equilibrium that gives UMAP its neighborhood preservation properties.
   • Effect: Points in sparse regions (large $r_i, r_j$) experience weaker forces per unit Euclidean displacement, causing the embedding to spread them out. Points in dense regions remain tightly packed.
4. Normalization: To handle the independent distance scales of the original data and the embedding, local radii are normalized using the 95th percentile ($P_{95}$) of the radii distribution before substitution.
5. Extension to PaCMAP: The same principle is applied to PaCMAP (dubbed Scale-PaCMAP) by replacing the geometric mean of radii with the product of PaCMAP's per-point distance scales ($\sigma_i \sigma_j$).

Key Contributions

1. Novel Formulation: The introduction of ScaleMAP, a modification of UMAP that injects local-scale information via a change of variables rather than an additional loss term.
2. Performance Balance: Demonstration that ScaleMAP achieves UMAP-level neighborhood preservation while matching or exceeding DensMAP on density preservation, with significantly fewer scattered (disconnected) points.
3. Structure Recovery: Successful recovery of sparse structures that UMAP collapses (e.g., transcriptomic bridges) and preservation of multiscale density structures (e.g., flow cytometry data spanning 17 orders of magnitude).
4. Generalizability: Evidence that the change-of-variables principle generalizes to other methods, specifically PaCMAP.

Results
The authors evaluated ScaleMAP on standard benchmarks (MNIST, Fashion-MNIST, COIL-20, Mammoth) and three scientific datasets (Tabula Sapiens transcriptomics, BCARS hyperspectral imaging, and human bone-marrow flow cytometry).

• Quantitative Metrics:

  • Density Preservation: ScaleMAP achieves density preservation ($R^2$ of log-log fit) comparable to DensMAP across most datasets (e.g., $R^2 \approx 0.51$ on Fashion-MNIST vs. DensMAP's $0.58$). On datasets with extreme dynamic ranges, ScaleMAP outperforms DensMAP (e.g., Flow Cytometry: $R^2 = 0.80$ vs. $0.68$; Hyperspectral Imaging: $R^2 = 0.81$ vs. $0.59$).
  • Neighborhood Preservation: ScaleMAP maintains kNN recall comparable to UMAP (e.g., 14.3% vs. UMAP's 13.3% on Fashion-MNIST) and significantly better than DensMAP (7.1%).
  • Disconnected Points: ScaleMAP keeps the fraction of disconnected points low and comparable to UMAP (e.g., 0.19% vs. UMAP's 0.11%), whereas DensMAP exhibits an order of magnitude more disconnected points (3.48%).
  • Class Mixing: ScaleMAP reduces class mixing compared to both baselines.

• Qualitative Observations:

  • Transcriptomics: ScaleMAP recovers sparse bridges between cell populations (e.g., monocytes-neutrophils, B-T cells) that are collapsed or invisible in UMAP.
  • Hyperspectral Imaging: It reveals sparse spectral spikes and small clusters that UMAP compresses or absorbs into the background.
  • Flow Cytometry: It faithfully represents multiscale structure across 17 orders of magnitude, preserving a dense "bulb" of marker-negative cells that appears as a tiny feature in the embedding, unlike UMAP/DensMAP which lack this multiscale fidelity.
  • Synthetic Diagnostics: On "XOI" and "Bridge" datasets, ScaleMAP correctly preserves relative sizes and sparse connections, whereas DensMAP distorts shapes and scatters points.

Significance and Claims
The paper claims that ScaleMAP represents a fundamental improvement in how neighborhood-preserving embeddings handle scale. By treating the rescaling as a change of variables rather than a competing objective, ScaleMAP avoids the trade-off between density fidelity and neighborhood integrity that plagues DensMAP.

The authors assert that ScaleMAP is the only tested method that does not sacrifice one axis of embedding quality for another: it retains UMAP's neighborhood preservation, matches DensMAP's density fidelity, and improves global distance-order preservation (surpassing PaCMAP on datasets with wide dynamic ranges). The paper concludes that restoring local scale is a general missing ingredient in neighborhood-preserving embeddings and suggests ScaleMAP as a default method when faithfully representing scale is critical for visualization. The approach is noted to be computationally efficient, adding only $O(n)$ overhead for precomputing radii, with total runtime roughly double that of UMAP.