ScaleMAP：在低维嵌入中保持局部密度和邻域结构

# ScaleMAP：在低维嵌入中保留局部密度和邻域结构
来源：https://arxiv.org/html/2605.30597
Rajas Poorna 化学与生物分子工程学院 佐治亚理工学院 rajasp@gatech\.edu  
Marcus T\. Cicerone 化学与生物化学学院 佐治亚理工学院 cicerone@gatech\.edu

###### 摘要

非线性降维方法（如 UMAP 和 PaCMAP）在图构建过程中自适应地归一化局部距离，从而抹去了数据中的邻域尺度。这不仅扭曲了相对聚类大小：稀疏结构（如过渡细胞类型之间的桥梁、高光谱图像中的窄光谱峰）可能被抑制或完全丢失。DensMAP 通过添加密度惩罚项来修正这一问题，但该惩罚项与 UMAP 的吸引-排斥力相互竞争，导致点远离其邻域而分散。ScaleMAP 采取了不同的方法：每个成对的嵌入位移除以两个端点在原始空间中局部半径的几何平均值，通过变量替换而非竞争性目标来重新注入尺度信息。在标准基准测试以及来自转录组学、高光谱成像和流式细胞术的科学数据集上，ScaleMAP 在密度保留方面与 DensMAP 相当，同时保持了 UMAP 级别的邻域保留。在转录组数据中，它恢复了 UMAP 压缩的细胞群之间的稀疏桥梁；在流式细胞术中，它忠实地表示了跨越 17 个数量级的密度结构。同样的原理应用于 PaCMAP 也能持续改善密度保留，表明该方法可推广至 UMAP 之外。

## 1 引言

低维嵌入通常是探索性分析大型高维数据集的第一步。非线性降维方法——UMAP[1 (https://arxiv.org/html/2605.30597#bib.bib1)]、t-SNE[2 (https://arxiv.org/html/2605.30597#bib.bib2)]、PaCMAP[3 (https://arxiv.org/html/2605.30597#bib.bib3)]——在高维空间中构建一个近似的 k 近邻图，并将点放置在二维空间中以便表示该图。特别是 UMAP 已成为自然科学领域探索性分析的默认工具。这些方法通过自适应带宽对每个点到其邻居的距离进行归一化，使其对局部密度的变化具有鲁棒性。直观上，人们可能会认为保留邻域的方法会同时保留邻域邻接性和尺度，但尽管在图构建过程中估计了相关尺度，它们通常不将其纳入嵌入目标中。因此，两个密度差异很大的区域在嵌入目标中变得难以区分——其后果不仅限于相对聚类大小的变化。稀疏结构，如过渡细胞类型之间的桥梁、高光谱图像中的窄光谱峰，以及跨越多个数量级的局部密度（如流式细胞术中的数据），都可能被抑制或丢失。

DensMAP[4 (https://arxiv.org/html/2605.30597#bib.bib4)]通过向 UMAP 损失添加一个惩罚项来解决此问题，该惩罚项抑制原始空间和嵌入空间中局部密度之间的不匹配。然而，该惩罚项与 UMAP 的吸引-排斥力相互竞争，导致 DensMAP 将一部分点分散到远离其真实邻居的位置，使得嵌入的稀疏区域难以解释。

如果 UMAP 正确表示了形状但未表示尺度，那么解决此问题的一个直观方法是：局部地重新缩放空间以匹配原始空间中的尺度。我们可以通过将嵌入点之间的距离视为非均匀来实现这一点。ScaleMAP 通过执行*变量替换*来实现：每个成对的嵌入位移 $y_i - y_j$ 除以两个端点在原始空间中局部半径的几何平均值 $\sqrt{r_i r_j}$，而 UMAP 目标的其他部分保持不变。由于重新缩放均匀地应用于所有力，因此保持了 UMAP 邻域保留的局部平衡，同时重新引入了原始尺度信息。

**贡献**

1. 我们引入了 ScaleMAP，这是 UMAP 的修改版本，通过变量替换而非额外的损失项来注入局部尺度信息。同样的原理也适用于 PaCMAP。
2. 在标准基准测试和三种科学数据模态上，ScaleMAP 实现了 UMAP 级别的邻域保留，同时在密度保留方面广泛匹配或超过 DensMAP，并且分散点显著减少。
3. ScaleMAP 恢复了 UMAP 压缩的结构——与已知发育关系一致的转录组桥梁、高光谱成像中的稀疏光谱峰——并在流式细胞术数据中忠实地保留了跨越 17 个数量级的密度。

## 2 方法

### 2.1 UMAP 作为吸引力和排斥力

UMAP[1 (https://arxiv.org/html/2605.30597#bib.bib1)]在原始空间中构建一个带权重的 kNN 图。对于每个点 $x_i$ 及其 $k$ 个最近邻，定义有向隶属度权重

$$
\mu_{ij} = \exp\left(-\frac{d(x_i, x_j) - \rho_i}{\sigma_i}\right),
$$ (1)

其中 $\rho_i$ 是从 $x_i$ 到其最近邻的距离，$\sigma_i$ 是自适应带宽。相对于 $\sigma_i$ 较近的点权重接近 1；较远的点权重接近 0。为每个点选择带宽 $\sigma_i$，使得其到 $k$ 个邻居的总权重等于 $\log_2 k$，从而确保每个点无论局部密度如何都具有相当数量的有效邻居。这些有向权重通过 $v_{ij} = \mu_{ij} + \mu_{ji} - \mu_{ij}\mu_{ji}$ 进行对称化。

嵌入点 $y_i \in \mathbb{R}^2$ 通过图拉普拉斯算子的谱分解进行初始化[5 (https://arxiv.org/html/2605.30597#bib.bib5)]，然后通过交叉熵损失的随机梯度下降进行细化[1 (https://arxiv.org/html/2605.30597#bib.bib1)]，该损失分解为每条边的吸引和排斥更新步骤。记 $d_{ij}^2 = \|y_i - y_j\|^2$ 为嵌入空间的平方距离：

**吸引步骤。** 对于以概率正比于 $v_{ij}$ 采样的图边 $(i, j)$，将 $y_i$ 向 $y_j$ 移动：

$$
y_i \leftarrow y_i - \alpha \cdot \frac{2ab\,(d_{ij}^2)^{b-1}}{1 + a\,(d_{ij}^2)^b}\,(y_i - y_j).
$$ (2)

**排斥步骤。** 对于随机采样的非邻居 $k$，将 $y_i$ 推离 $y_k$：

$$
y_i \leftarrow y_i + \alpha \cdot \frac{2b}{(d_{ik}^2 + \epsilon)(1 + a\,(d_{ik}^2)^b)}\,(y_i - y_k),
$$ (3)

其中 $\alpha$ 是学习率，$\epsilon$ 是一个小常数，$a, b$ 通过校准到 UMAP 的 `min_dist` 参数来确定。自适应带宽 $\sigma_i$ 使得这些更新对局部密度的变化具有鲁棒性，但也丢弃了关于邻域绝对尺度的信息。

### 2.2 局部半径

DensMAP[4 (https://arxiv.org/html/2605.30597#bib.bib4)]引入了*局部半径*，作为原始空间中邻域尺度的度量：

$$
r_i^2 = \frac{\sum_j v_{ij}\, d(x_i, x_j)^2}{\sum_j v_{ij}}.
$$ (4)

这是从 $x_i$ 到其 UMAP 图邻居的加权 RMS 距离，重复使用现有权重 $v_{ij}$，无需引入额外的超参数。给定 kNN 图后，计算复杂度为 $O(n)$。

### 2.3 DensMAP：一个竞争性目标

DensMAP 通过向 UMAP 损失添加惩罚项来最大化 $\log r_o$（原始空间局部半径）与 $\log r_e$（嵌入空间局部半径）之间的 Pearson 相关系数：$\mathcal{L}_{\text{DensMAP}} = \mathcal{L}_{\text{UMAP}} - \lambda \, \text{Corr}(\log r_o, \log r_e)$。在每条边的更新方面，这会在吸引步骤中添加一个密度梯度，而排斥步骤保持不变：

$$
\textbf{吸引：} \quad y_i \leftarrow y_i + \Delta y_i^{\text{attr}} + \lambda \nabla_{y_i} \text{Corr}(\log r_e, \log r_o),
$$ (5)
$$
\textbf{排斥：} \quad y_i \leftarrow y_i + \Delta y_i^{\text{rep}},
$$ (6)

其中相关系数的梯度涉及嵌入局部半径对 $d_{ij}^2$ 的偏导数（完整表达式见[4 (https://arxiv.org/html/2605.30597#bib.bib4)]）。由于密度梯度可能与吸引力相反，而排斥力未被修改，DensMAP 可能将点分散到远离其邻域的位置——在我们的实验中，错位点的比例有时比 UMAP 大一个数量级。Wang 等人 [3 (https://arxiv.org/html/2605.30597#bib.bib3)] 在 UMAP 对嵌入初始化敏感性的背景下证明，一旦点远离其局部邻域，UMAP 的吸引力会迅速下降，这可能导致断开的点永远无法回到其邻域。

### 2.4 ScaleMAP：变量替换

ScaleMAP 没有添加竞争性目标，而是修改了进入现有 UMAP 力的距离。定义*重新缩放的平方距离*

$$
\tilde{d}_{ij}^2 = \frac{d_{ij}^2}{r_i r_j} = \frac{\|y_i - y_j\|^2}{r_i r_j}.
$$ (7)

将 $\tilde{d}_{ij}^2$ 代入交叉熵损失中的 $d_{ij}^2$ 并微分，得到 ScaleMAP 的更新规则。链式规则在位移方向引入了一个因子 $1/(r_i r_j)$：

**吸引步骤。**

$$
y_i \leftarrow y_i - \alpha \cdot \frac{2ab\,(\tilde{d}_{ij}^2)^{b-1}}{1 + a\,(\tilde{d}_{ij}^2)^b} \frac{y_i - y_j}{r_i r_j}.
$$ (8)

**排斥步骤。**

$$
y_i \leftarrow y_i + \alpha \cdot \frac{2b}{(\tilde{d}_{ik}^2 + \epsilon)(1 + a\,(\tilde{d}_{ik}^2)^b)} \frac{y_i - y_k}{r_i r_k}.
$$ (9)

系数函数与 UMAP 的 (2)-(3) 相同，但评估于 $\tilde{d}^2$ 而不是 $d^2$。没有引入新的损失项。由于重新缩放对称地进入吸引力和排斥力，保持了 UMAP 邻域保留的局部平衡。稀疏区域（$r_i, r_j$ 较大）的点每单位欧几里得位移感受到的力较弱，因此嵌入将其展开；密集区域中的点保持紧密聚集。我们在第 5 节中展示，用任一端点单独替代几何平均值 $\sqrt{r_i r_j}$ 会破坏嵌入。

### 2.5 计算开销和默认设置

原始空间中计算的局部半径具有由数据决定的距离尺度，而 UMAP 嵌入目标具有独立的距离尺度。因此，在代入 (7) 之前，我们对局部半径进行归一化：

$$
r_{\mathrm{normalized}}(i) = \frac{r_{\mathrm{original}}(i)}{P_\eta\left(\{r_{\mathrm{original}}(j)\}_{j=1}^n\right)}.
$$ (10)

这里，$n$ 表示总点数，$P_\eta$ 是归一化因子，即局部半径的第 $\eta$ 百分位数。我们对所有实验默认使用第 95 百分位数 $P_{95}$；我们在附录 A.5 中检查对此参数的敏感性。

我们使用与 UMAP 相同的谱初始化，并在每次迭代中应用此修改后的更新函数，这与 DensMAP 不同（DensMAP 仅在部分迭代中应用修改后的更新函数）。

ScaleMAP 相对于 UMAP 增加了 $O(n)$ 开销，与 DensMAP 相同：只需预先计算每个点的局部半径。我们对该步骤进行了并行化，否则可能成为大型数据集的瓶颈。然而，在方法之间的比较中，我们不修改 DensMAP 的实现。我们对 ScaleMAP 默认使用 800 个 epoch（UMAP 为 200，DensMAP 为 400）。尽管对于大多数数据集，ScaleMAP 在 200 和 800 个 epoch 下给出的嵌入在定性上几乎相同，但当两者都设置为 200 个 epoch 时，断点比例大于 UMAP。使用更多 epoch 可使断点比例适度降低（6-33%），同时仍保持实用的运行时间。比较见附录 A.3。

### 2.6 扩展到 PaCMAP

PaCMAP[3 (https://arxiv.org/html/2605.30597#bib.bib3)]在邻居选择时计算每点的距离尺度 $\sigma_i$（到第 4-6 个最近邻的平均距离）；在构建图时，成对距离除以 $\sigma_i \sigma_j$，尽管这些缩放后的距离在优化过程中不被使用。我们在嵌入中重新利用 $\sigma_i$，在重新缩放的距离 (7) 中用 $\sigma_i \sigma_j$ 替换 $r_i r_j$，并将类似的变量替换应用于 PaCMAP 的吸引和排斥更新。我们称之为 Scale-PaCMAP，并将其视为可移植性检查而非同等方法。出于与 ScaleMAP 相同的原因，我们在每个阶段使用的迭代次数也是 PaCMAP 默认值的两倍。

## 3 实验设置

#### 数据集。

我们在标准基准数据集——MNIST[6 (https://arxiv.org/html/2605.30597#bib.bib6)]、Fashion-MNIST[7 (https://arxiv.org/html/2605.30597#bib.bib7)]、COIL-20[8 (https://arxiv.org/html/2605.30597#bib.bib8)] 和 Mammoth[9 (https://arxiv.org/html/2605.30597#bib.bib9)]——以及三个科学数据集上进行评估：264,824 个 Tabula Sapiens 免疫细胞[10 (https://arxiv.org/html/2605.30597#bib.bib10)]，由提供的 50 维 SCVI 潜在嵌入表示[11 (https://arxiv.org/html/2605.30597#bib.bib11)]；一张 $610 \times 610$ 的 BCARS[12 (https://arxiv.org/html/2605.30597#bib.bib12)] 线虫性腺高光谱图像，具有 650 个光谱通道[13 (https://arxiv.org/html/2605.30597#bib.bib13)]；以及人类骨髓流式细胞术数据，具有 8 个原始荧光标记通道[14 (https://arxiv.org/html/2605.30597#bib.bib14)]。两个合成诊断数据集 XOI 和 Bridge 在第 4.1 节中描述。

#### 指标。

对于密度保留，我们在嵌入空间中计算局部半径