本文系统梳理 Gromov-Wasserstein（GW）距离及其变体在数据降维（Dimensionality Reduction）领域的最新进展。核心路线：从经典 GW 出发，经过半松弛 GW（semi-relaxed GW）到分布缩减（Distributional Reduction），并结合嵌入学习、有监督扩展和流匹配等方向。

背景：为什么 GW 适合降维？

降维的核心目标是：给定高维数据 $X \subset \mathbb{R}^D$，找一个低维嵌入 $Z \subset \mathbb{R}^d$（$d \ll D$），使得 $Z$ 尽可能”保持” $X$ 的某种结构。

GW 距离天然适合这个任务，因为它度量两个度量空间之间的差异——而不要求空间维度相同、特征可比。这正是降维的设定：高维空间和低维空间维度不同、特征不可比，但我们可以要求它们的内部点间距离结构一致。

标准 GW 距离： \(\text{GW}(P, Q) = \min_{\pi \in \Pi(\mu,\nu)} \sum_{i,j,k,l} \|d_X(x_i, x_k) - d_Y(y_j, y_l)\|^2 \, \pi_{ij} \pi_{kl}\)

Group 1：核心 GW 降维方法

1.1 Eufrazio et al. [arXiv:2501.13732] — 基于 GW 的降维

将降维重写为 GW 对齐问题：

\[\min_{Z} \text{GW}(\mu_X, \nu_Z)\]
  • 高维数据 $\mu_X$ 和低维嵌入 $\nu_Z$ 的 GW 距离最小化
  • 超越传统 MDS：MDS 固定点到点的对应关系（$\pi = I$），GW 同时学习对应关系和嵌入位置
  • 梯度下降交替优化 $\pi$ 和 $Z$

与经典算法的关系：

方法 GW 视角
MDS 固定 $\pi = I$，只优化 Z
Isomap 用测地距离替换欧氏距离，其他同 MDS
GW-DR (本文) 不固定 $\pi$，同时学对应+嵌入

1.2 Van Assel et al. [arXiv:2310.03398] — 半松弛 GW 插值聚类与降维

semi-relaxed GW (srGW)：

\[\text{srGW}(D_X, D_Z, \mu, \nu) = \min_{\pi \in \Pi(\mu, \nu)} \sum_{i,j,k,l} |d_X(x_i, x_k)^2 - d_Z(z_j, z_l)^2| \, \pi_{ij} \pi_{kl}\]

关键特性：目标分布的权重 $\nu$ 可以学习（部分松弛）。

嵌入样本数 行为
$n_{emb} = n_{input}$ 退化为经典降维
$n_{emb} < n_{input}$ 样本缩减——多点到一点
维度无约束 运输计划 $\pi$ 给出硬聚类
中间状态 聚类 + 降维同时做

一个参数 $\lambda$ 连续控制从”纯降维”到”纯聚类”的过渡。

1.3 Van Assel et al. [arXiv:2402.02239] — 分布缩减（Distributional Reduction）

系统化扩展，提出统一框架：

\[\boxed{\text{分布缩减} = \text{降维} + \text{聚类 统一在 GW 框架下}}\]
  • 学一个缩减表示 $Y = {y_1, \ldots, y_m}$（$m \ll n$）和权重 $b \in \mathbb{R}^m$
  • $m = n$ → 经典 MDS
  • $m \ll n$ + 低维 Y → 降维
  • $m \ll n$ + 维度无约束 → 聚类
  • 支持多尺度分析：选择不同 $m$ 在不同分辨率下看数据

数学本质：在 Wasserstein 空间中学一个低维多面体（simplex）近似。

1.4 Clark, Needham, Weighill [arXiv:2405.15959] — 推广到任意度量空间

传统降维：$\mathbb{R}^D \to \mathbb{R}^d$

本文：$\mathbb{R}^D \to$ 任意度量空间（圆 $S^1$、图、树、流形）

\[\min_{Z \subset \mathcal{M}} \text{srGW}(D_X, D_Z)\]
  • 建立 srGW 与 Gromov-Hausdorff 距离的理论联系
  • srGW 是 GH 的”可计算松弛”
  • 应用例子：政治选区重划嵌入圆环 $S^1$，判断是否 gerrymandering

Group 2：嵌入 / 表征学习

2.1 Bai et al. [arXiv:2410.16669] — 线性部分 GW 嵌入 (LPGW)

痛点：GW 复杂度 $O(n^4)$，每次新样本都要重算。

LPGW：

\[\text{LPGW}(P, Q) = \|\phi(P) - \phi(Q)\|\]
  • $\phi$ 是显式特征映射，将概率测度映射到特征向量
  • 选参考分布 $\mu_0$，对每个分布找 $\mu_0$ 到 $P$ 的最优部分运输
  • 运输方向作为特征

好处：$K$ 个分布间距离计算从 $O(K^2)$ 降到 $O(K)$

2.2 Eufrazio et al. [arXiv:2604.23912] — Bary-GWMDS

多视图数据降维：

\[\min_{Z, \pi^{(1)}, \ldots, \pi^{(V)}} \sum_{v=1}^V \lambda_v \cdot \text{GW}(D^{(v)}, D_Z)\]
  • GW 重心：找嵌入 $Z$ 使其到各视图的 GW 距离加权和最小
  • 每个视图”结构投票”，通过 GW 对齐后取共识
  • Mean-GWMDS-C：聚类版，约束嵌入数量

2.3 Eufrazio et al. [arXiv:2604.02610] — 保结构多视图嵌入

两种策略： - Mean-GWMDS：平均距离矩阵后 GW 嵌入（简单但损失非线性结构） - Multi-GWMDS：每个视图独立 GW 嵌入，再从候选 Z 中选代表性嵌入

后者更精细：$\min_{Z} \sum_v \text{GW}(D_Z^{(v)}, D_Z)$

2.4 Xu et al. [arXiv:1901.06003] — GW 图匹配与节点嵌入

联合框架：同时做图匹配 + 节点嵌入

\[\min_{\pi, Z_1, Z_2} \text{GW}(D_{G_1}, D_{G_2}) + \lambda \cdot \text{reg}(Z_1, Z_2, \pi)\]
  • 固定 Z 优化 $\pi$ → 图匹配
  • 固定 $\pi$ 优化 $Z$ → 节点嵌入
  • 交替近端点法求解
  node2vec GW 方法
图数 单个图 两个不同图
对齐 不需要 自动学出跨图对应
应用 单个图分析 跨图匹配+嵌入

Group 3：扩展方向

3.1 Ryner & Karlsson [arXiv:2207.12279] — GW 型反馈正交化

不是直接最小化 GW，而是用 GW 结构做反馈：

  1. 扩散映射：数据点用 Markov 转移概率表示
  2. GW 型反馈：迭代修改转移概率矩阵使其正交化（簇间概率→0，簇内→1）
  3. 证明对某些参数全局收敛到唯一不动点

3.2 Ramesh et al. [arXiv:2605.27619] — 有监督分布缩减 (SDR)

将分布缩减推广到有监督：

\[\min_{Y, b, \pi} \underbrace{\text{FGW}(D_X, D_Y, \pi)}_{\text{保结构}} + \beta \cdot \underbrace{\text{MI}(Y, \text{label})}_{\text{标签依赖}}\]
  • Fused GW (FGW)：GW 中集成标签特征距离
  • 互信息最大化：嵌入携带标签信息
  • 学到的距离可用于非平稳核函数设计（高斯过程）

3.3 Cai et al. [arXiv:2510.23015] — Coupled Flow Matching (CPFM)

Flow Matching + GW 做可控降维+重建：

两个耦合流： - 潜伏流 $y_t$：先验 → 嵌入 - 数据流 $x_t$：嵌入条件 → 原始数据

GW 保证嵌入空间几何忠实反映原始数据结构：不只是压缩，而是”压缩后的空间几何 ≈ 原始空间几何”。

用户可指定保留哪些语义维度，残余信息存在流网络权重中可恢复。

整体逻辑关系

┌─────────────────────┐ │ GW 距离 — 基础 │ └────┬────────┬───────┘ │ │ ┌────────────┤ ├──────────────┐ ▼ ▼ ▼ ▼ ┌──────────┐ ┌──────────┐ ┌──────┐ ┌──────────┐ │ 纯降维 │ │聚类+降维 │ │嵌入 │ │ 扩展方向 │ │ #1 Eufrazio│ │#2 VanA │ │#5 Bai│ │ #9 反馈 │ │ #4 Clark │ │#3 VanA │ │#6-7E │ │#10 有监督 │ └──────────┘ │#10 Ramesh │ │#8 Xu │ │#11 流匹配 │ └──────────┘ └──────┘ └──────────┘

参考文献

  1. Eufrazio et al. A dimensionality reduction technique based on the Gromov-Wasserstein distance. arXiv:2501.13732
  2. Van Assel et al. Interpolating between Clustering and Dimensionality Reduction with Gromov-Wasserstein. arXiv:2310.03398
  3. Van Assel et al. Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein. arXiv:2402.02239
  4. Clark, Needham, Weighill. Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance. arXiv:2405.15959
  5. Bai et al. Linear Partial Gromov-Wasserstein Embedding. arXiv:2410.16669
  6. Eufrazio et al. Gromov-Wasserstein Methods for Multi-View Relational Embedding and Clustering. arXiv:2604.23912
  7. Eufrazio et al. Structure-Preserving Multi-View Embedding Using Gromov-Wasserstein Optimal Transport. arXiv:2604.02610
  8. Xu et al. Gromov-Wasserstein Learning for Graph Matching and Node Embedding. arXiv:1901.06003
  9. Ryner & Karlsson. Orthogonalization of data via Gromov-Wasserstein type feedback for clustering and visualization. arXiv:2207.12279
  10. Ramesh et al. Supervised Distributional Reduction via Optimal Transport and Dependence Maximization. arXiv:2605.27619
  11. Cai et al. Coupled Flow Matching. arXiv:2510.23015