Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem¶

会议: NeurIPS 2026
arXiv: 2303.05978
论文: https://arxiv.org/abs/2303.05978
领域: 学习理论
关键词: 格罗莫夫-瓦瑟斯坦距离, 连续最优传输, 神经最优传输, 极小极大优化, 领域对齐基准

一句话总结¶

本文系统揭示了现有声称求解连续格罗莫夫-瓦瑟斯坦（GW）最优传输的方法严重依赖离散技术和数据显式相关性的致命缺陷，证明其在统计独立的真实数据下近乎完全失效，并提出了首个基于对偶极小极大化、完全摆脱离散近似的可扩展连续神经求解器 NeuralGW。

研究背景与动机¶

格罗莫夫-瓦瑟斯坦（Gromov-Wasserstein, GW）最优传输因其能够跨越不同度量空间、仅基于各域内部几何结构（如内积、欧氏距离、余弦相似度）寻找最具等距保真度映射的优良特性，近年来在跨语言词向量对齐、单细胞多组学数据整合、跨模态表示学习等任务中受到广泛关注。传统的离散 GW 仅能为给定的有限样本集求解二分置换或耦合矩阵，无法对新样本进行样本外推断（out-of-sample estimation）；因此，学界提出了一系列连续 GW 求解器（如基于重构变换的 StructuredGW、流匹配模型 FlowGW、重心回归的 AlignGW 以及基于 Gromov-Monge gap 正则项的 RegGW 等），旨在从经验分布中学习跨空间的参数化连续映射 $T: \mathbb{R}^{d_x} \to \mathbb{R}^{d_y}$。

然而，尽管这些算法在基准测试中展现出令人瞩目的性能，其理论有效性与真实实用边界却存在严重脱节。深究现有工作所采用的实验设置可以发现，大多数算法实际验证的数据集（如双语词典对齐、同一供体的骨髓细胞谱分析）在源域与目标域样本之间暗含了极其强烈的隐式配对或统计相关性。在这种强相关设置下，离散 GW 本质上退化为在预配对样本上寻找最优置换排列的退化匹配问题。而在实际跨模态或单细胞分析中，由于多组学检测技术的破坏性，从同一细胞同时获取多种组学测量是物理上不可行的，数据在本质上是相互独立的非相关（uncorrelated）采样。当回归标准的 i.i.d. 独立采样假定时，依赖小批量离散最优传输求解器的算法是否依然有效，构成了领域长期忽视的盲区。

更关键的技术瓶颈在于，离散 GW 求解对应非凸二次规划，计算复杂度随样本量 $N$ 呈二次方甚至更高阶膨胀，导致现有连续求解器只能在几千个样本的小规模子集上运行离散求解，再套用神经网络进行拟合。在非相关数据下，经验测度间的 GW 样本复杂度已被证明呈现指数级恶化（$O(N^{-2/\min(d_x, d_y)})$），小样本经验几何结构严重偏离母体真实几何，导致现有算法在真实设置下全面崩溃。核心 idea：通过构建相关度 $\alpha \in [0, 1]$ 连续可调的双语嵌入对齐基准，对现有连续 GW 算法进行压力测试揭示其在无相关数据下的失效本质；同时基于内积 GW 的理论对偶重构，提出首个完全绕过离散近似、支持大样本随机采样的三层极小极大连续神经求解器 NeuralGW。

方法详解¶

整体框架¶

本文提出的研究体系包含两大部分：一是量化评估连续 GW 求解器对数据相关性依赖度的基准评测协议；二是用于克服离散方法缺陷的新型连续神经最优传输求解器 NeuralGW。在评测流程中，通过受控相关度参数 $\alpha \in [0, 1]$ 将原本具有天然配对关系的基准语料（如 Twitter-GloVe 或 MUSE-BPEmb）系统性地构造成从完全相关（$\alpha=1$）、部分相关（$0<\alpha<1$）到完全独立（$\alpha=0$）的训练集，以测试各模型对先验配对关系的敏感度。

在算法构建层面，针对内积形式的连续格罗莫夫-瓦瑟斯坦问题（$\text{innerGW}_2^2$），NeuralGW 彻底抛弃了在离散耦合矩阵上进行 Sinkhorn 迭代或重心的传统范式，而是借助 Vayer (2020) 的理论对偶转换，将二次二次距离最小化问题等价转化为带有正交投影矩阵 $P \in \mathbb{R}^{d_x \times d_y}$ 的极小极大对偶博弈。整个系统由传输网络（Mover）$T_\gamma$、对偶势函数（Critic）$f_\theta$ 以及流形约束投影矩阵 $P_\omega$ 共同组成，直接从源域分布 $\mathbb{P}$ 与目标域分布 $\mathbb{Q}$ 中抽取无配对小批量样本进行交替随机梯度更新，训练流水线如下图所示：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["经验分布采样<br/>X ~ ℙ, Y ~ ℚ（无配对假定）"] --> B["数据相关度调制基准<br/>α ∈ [0,1] 控制隐式配对比例"]
    B --> C["连续内积 GW 对偶重构<br/>min_P max_f min_T 鞍点目标"]
    C --> D["三层交替对抗优化<br/>传输映射 T_γ 更新 (k_T=10 次)"]
    D --> E["对偶势函数 f_θ 更新<br/>结合 R1 梯度正则项稳定对抗"]
    E --> F["流形约束矩阵 P_ω 更新<br/>GeoTorch 约束行范数归一化"]
    F --> G["收敛输出连续传输映射<br/>T*: ℝ^d_x → ℝ^d_y（支持新样本推断）"]

关键设计¶

1. 数据相关度可控基准：揭示离散代理在独立样本下的失效本质
现有文献普遍在具有内在配对关系的数据集上评估算法，造成了算法无需显式配对也能学习对齐的假象。为了严格解耦数据统计相关性对求解器的影响，本文提出了一种可控指数滑动采样机制：给定总规模为 $N = N_{\text{train}} + N_{\text{test}}$ 的完全配对样本，将训练集划分为两半，引入参数 $\alpha \in [0, 1]$ 表示保留配对关系的样本比例。在构建训练数据时，源域选取前 $N_{\text{train}}/2$ 个样本索引，目标域则选取偏移区间 $[\lceil(1-\alpha)(N_{\text{train}}/2)\rceil, \lceil(1-\alpha/2)N_{\text{train}}\rceil]$ 的索引。当 $\alpha=1$ 时两域索引完全对齐（完全相关）；当 $\alpha=0$ 时源域与目标域选取的词汇集合互不相交（完全不相关且独立）。实验表明，现有算法（StructuredGW, FlowGW, AlignGW）在 $\alpha=1$ 时表现优良，但随着 $\alpha$ 趋向 0，性能呈断崖式下滑，证明其本质上是在对样本进行置换恢复，并未真正学到母体分布间的内蕴等距几何映射。

2. 内积连续 GW 的对偶极小极大重构：绕过二次非凸离散耦合瓶颈
针对源域空间维度高于目标域（$d_x \ge d_y$）且两者均配备内积度量 $c_{\mathcal{X}}(x, x') = \langle x, x' \rangle_{d_x}, c_{\mathcal{Y}}(y, y') = \langle y, y' \rangle_{d_y}$ 的连续问题： $$ \operatorname{innerGW}2^2(\mathbb{P}, \mathbb{Q}) = \min(x') $$ 传统方法直接优化离散化的四阶张量耦合矩阵，计算极其沉重。本文基于测度有限四阶矩假设，利用 Vayer 等人关于等距旋转与最优传输对偶的定理，证明了该问题可以严密转化为带有低维矩阵的 Kantorovich 形式，并进一步推导出连续极小极大优化公式： $$ \operatorname{innerGW}} = \mathbb{Q}} \int_{\mathbb{R}^{d_x} \times \mathbb{R}^{d_x}} \big|\langle x, x'\rangle_{d_x} - \langle T(x), T(x')\rangle_{d_y}\big|^2 d\mathbb{P}(x)d\mathbb{P2^2(\mathbb{P}, \mathbb{Q}) = \operatorname{Const}(\mathbb{P}, \mathbb{Q}) + \min(P, f, T) $$ 其中目标泛函定义为： $$ \mathcal{L}(P, f, T) = \int_{\mathbb{R}^{d_y}} f(y) d\mathbb{Q}(y) - \int_{\mathbb{R}^{d_x}} \big[\langle Px, T(x)\rangle_{d_y} + f(T(x))\big] d\mathbb{P}(x) $$ 该对偶形式将原本涉及样本对之间交互计算（二重积分）的四阶问题，巧妙解耦为单样本积分期望，从而允许使用标准蒙特卡洛小批量随机抽样，为大规模非相关数据上的连续优化奠定了理论基石。}} \max_{f: \mathbb{R}^{d_y} \to \mathbb{R}} \min_{T: \mathbb{R}^{d_x} \to \mathbb{R}^{d_y}} \mathcal{L

3. 三层交替对抗优化与流形约束：可扩展的大样本连续神经传输
为了将对偶形式转化为实用算法，NeuralGW 分别用多层感知机参数化传输映射 $T_\gamma$ 与连续势函数 $f_\theta$。对于降维投影矩阵 $P \in \mathbb{R}^{d_x \times d_y}$，理论要求其属于 Frobenius 范数约束集合 $F_{d_x, d_y} = \{P \mid \|P\|_{\mathcal{F}} = \min(\sqrt{d_x}, \sqrt{d_y})\}$。为了保证数值训练中严格保持行规范化，算法借助黎曼流形优化库 GeoTorch 将 $P_\omega$ 的每一行约束在单位超球面上。在优化阶段，算法执行三层嵌套随机梯度升降：由于传输映射 $T_\gamma$ 处于内层极小化位置，每步循环中优先更新 $T_\gamma$（迭代 $k_T = 10$ 次），而对偶势函数 $f_\theta$ 与投影矩阵 $P_\omega$ 分别交替更新 $k_f = 1$ 与 $k_P = 1$ 次。由于不再依赖 $O(N^2)$ 的离散匹配，模型能够直接在 40 万词向量的全量规模上进行端到端随机梯度训练。

损失函数 / 训练策略¶

在算法实现中，对于每批经验样本 $X = \{x_n\}_{n=1}^N \sim \mathbb{P}, Y = \{y_n\}_{n=1}^N \sim \mathbb{Q}$，各个模块的经验损失定义如下： - 投影矩阵损失（外层最小化）： $$ \mathcal{L}P = -\frac{1}{N}\sum $$ - }^N \langle P_\omega x_n, T_\gamma(x_n)\rangle_{d_y传输映射损失（内层最小化）： $$ \mathcal{L}T = -\frac{1}{N}\sum^N f_\theta(T_\gamma(x_n)) $$ - }^N \langle P_\omega x_n, T_\gamma(x_n)\rangle_{d_y} - \frac{1}{N}\sum_{n=1对偶势函数损失（中层最大化）：为抑制对抗博弈中的梯度爆炸并稳定极小极大动力系统，在势函数中引入类似于 WGAN 的 $R_1$ 梯度惩罚正则化项（权重 $\lambda = 0.1$）： $$ \mathcal{L}f = -\frac{1}{N}\sum f_\theta(y_i)|_2^2 $$ 模型使用 Adam 优化器，学习率设为 }^N f_\theta(T_\gamma(x_n)) - \frac{1}{N}\sum_{n=1}^N f_\theta(y_n) - \lambda \frac{1}{N}\sum_{i=1}^N |\nabla_{y_i$1 \times 10^{-4}$，大样本实验批大小设为 512，训练 100 个 epoch。

实验关键数据¶

主实验¶

论文在多语言词嵌入数据集 MUSE-BPEmb（英语 100 维 $\to$ 西班牙语 100 维，总样本数 60K，测试集 2048）上对比了基准离散求解器与连续求解器在不同相关度水平 $\alpha \in \{0.0, 0.5, 1.0\}$ 下的对齐指标（Top 10 命中率 $\uparrow$ 以及样本距真实配对距离比例 FOSCTTM $\downarrow$，越小越好，随机猜测为 0.5）。所有指标均在全量参考空间（60K 样本）中评估。

模型类型	求解器名称	$\alpha = 0.0$ (Top 10 / FOSCTTM)	$\alpha = 0.5$ (Top 10 / FOSCTTM)	$\alpha = 1.0$ (Top 10 / FOSCTTM)
离散基线	FlowGW	0.0013 / 0.4222	0.0029 / 0.3983	0.0267 / 0.3321
离散基线	AlignGW	0.0012 / 0.4056	0.0022 / 0.3768	0.0146 / 0.3085
离散基线	StructuredGW	0.0000 / 0.5037	0.0006 / 0.4541	0.0009 / 0.4443
连续方法	RegGW	0.0001 / 0.4521	0.0009 / 0.4411	0.0013 / 0.4384
连续方法	FlowGW (minibatch)	0.0006 / 0.4767	0.0007 / 0.4770	0.0008 / 0.4772
本文方法	NeuralGW (ours)	0.0518 (0.0633) / 0.3811 (0.1286)	0.0284 (0.0564) / 0.4379 (0.1067)	0.0748 (0.0751) / 0.3514 (0.1321)

在最严苛的无相关性设置 $\alpha=0.0$ 下，所有基线方法的 Top 10 准确率均接近于 0（FOSCTTM 接近 0.45-0.50，等同于随机猜测）；而 NeuralGW 取得了 0.0518 的 Top 10 准确率，大幅领先所有竞争对手，是唯一在完全非相关数据下具备几何学习能力的连续求解器。

消融实验与应力测试¶

下表展示了当 NeuralGW 在样本量受限的小数据集（Twitter-GloVe，训练样本 $N_{\text{train}}=6\text{K}$，在 400K 全局参考空间评估）及不同维度变换设置下的消融结果，直接揭示了对抗性神经求解器的数据饥饿特性与维度不对称瓶颈：

变换维度配置	相关度级别 $\alpha$	Top 1 准确率	Top 5 准确率	Top 10 准确率	余弦相似度 (Cosine)	FOSCTTM
$100 \to 50$ (高维降维)	$\alpha = 0.2$	0.000	0.000	0.003	0.100	0.462
$100 \to 50$ (高维降维)	$\alpha = 0.5$	0.000	0.001	0.004	0.107	0.470
$100 \to 50$ (高维降维)	$\alpha = 1.0$	0.000	0.003	0.005	0.117	0.447
$50 \to 25$ (低维降维)	$\alpha = 0.2$	0.000	0.001	0.003	0.165	0.441
$50 \to 25$ (低维降维)	$\alpha = 0.5$	0.001	0.004	0.007	0.176	0.423
$50 \to 25$ (低维降维)	$\alpha = 1.0$	0.000	0.000	0.004	0.174	0.435
$50 \to 100$ (低向高升维)	$\alpha = 0.2$	0.000	0.002	0.003	0.086	0.455
$50 \to 100$ (低向高升维)	$\alpha = 0.5$	0.000	0.003	0.005	0.084	0.459
$50 \to 100$ (低向高升维)	$\alpha = 1.0$	0.000	0.002	0.003	0.089	0.450
$25 \to 50$ (低向高升维)	$\alpha = 0.2$	0.000	0.002	0.005	0.113	0.440
$25 \to 50$ (低向高升维)	$\alpha = 0.5$	0.000	0.000	0.001	0.095	0.464
$25 \to 50$ (低向高升维)	$\alpha = 1.0$	0.001	0.003	0.005	0.124	0.436

在真实的生物骨髓单细胞多组学数据（Bone Marrow: ATAC+GEX 38 维 $\to$ ADT+GEX 50 维，$N_{\text{train}}=5000$）压力测试中，所有求解器（包括 FlowGW、AlignGW、StructuredGW 与 NeuralGW）无论 $\alpha$ 为 0.2、0.5 还是 1.0，Top 10 命中率全部卡死在 0.001 - 0.004，FOSCTTM 保持在 0.459 - 0.514 的随机基线水平，证实了真实生物多组学空间缺乏强等距结构时纯几何 GW 的根本困境。

关键发现¶

离散求解器的配对假象：现有方法在 $\alpha=1$ 时的优秀表现具有极高误导性，它们本质上依赖小批量样本内隐式配对提供的信息引导；一旦洗牌打乱或完全独立，离散最优传输求解出的几何耦合完全退化。
样本量对连续神经求解的决定性制约：NeuralGW 作为三层极小极大对抗优化模型，高度依赖大样本量（如 $90\text{K}-400\text{K}$）来拟合连续几何。当样本量压缩至 $6\text{K}$ 时，NeuralGW 的对齐指标同样退化至接近随机猜测。
高低维变换的不对称性：现有连续求解器理论上与实验中仅能单向处理高维向低维（$d_x \ge d_y$）的映射；在低维向高维（如 $50 \to 100$）映射时，由于流形嵌入的不变性缺失，所有方法全部失效。

亮点与洞察¶

尖锐的批判性视角：明确指出学界长期以来在连续 GWOT 评估中混淆“连续映射推断”与“离散置换恢复”的盲区，首次引入可控相关度 $\alpha$ 协议切断了信息泄露通道。
完全绕过离散近似的对偶转化：借助内积 GW 的理论性质将二次二次非凸问题重构为线性最优传输对偶博弈，使深度神经网络能够在无配对大数据集上按小批量随机梯度训练。
坦率的局限揭示与负面结果报告：不仅展示 NeuralGW 在大样本无相关场景下的优势，也全面展示了其在小样本下的欠拟合、对抗训练的高方差（大标准差）以及在生物异质数据上的失败，为后续研究指明了真实痛点。

局限与展望¶

作者承认的局限：NeuralGW 采用的极小极大对抗训练本质上非凸非凹，训练过程震荡严重，不同随机初始化参数下的性能方差极大；且方法要求大规模训练样本，在小样本场景下无法建立有效映射。
独立发现的局限：目前的对偶转换仅严格适用于内积代价（$\text{innerGW}_2^2$），对于一般欧氏距离或非内积几何结构，该极小极大等价性不再成立；同时模型仅支持 $d_x \ge d_y$ 的降维方向，升维映射在理论框架内未获解决。
未来改进方向：探索引入非对抗的连续重构方法（如基于单调势函数或双凸结构），并结合微弱弱监督/锚点先验（Fused Gromov-Wasserstein）来打破无监督等距对齐的内在对称性模糊。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [揭示了连续 GW 领域长期存在的评测假象，并给出了首个大样本对偶对抗连续求解器]
实验充分度: ⭐⭐⭐⭐⭐ [跨越合成高斯、Twitter-GloVe、MUSE-BPEmb 及单细胞骨髓数据，覆盖了严谨的应力测试与消融实验]
写作质量: ⭐⭐⭐⭐⭐ [逻辑严谨、数学推导扎实，深入剖析了负面结果与核心瓶颈]
价值: ⭐⭐⭐⭐⭐ [为跨模态无监督几何对齐树立了严谨的评估标杆，对最优传输理论在机器学习中的实际落地极具警示与指导意义]

变换维度配置	相关度级别 \(\alpha\)	Top 1 准确率	Top 5 准确率	Top 10 准确率	余弦相似度 (Cosine)	FOSCTTM
\(100 \to 50\) (高维降维)	\(\alpha = 0.2\)	0.000	0.000	0.003	0.100	0.462
\(100 \to 50\) (高维降维)	\(\alpha = 0.5\)	0.000	0.001	0.004	0.107	0.470
\(100 \to 50\) (高维降维)	\(\alpha = 1.0\)	0.000	0.003	0.005	0.117	0.447
\(50 \to 25\) (低维降维)	\(\alpha = 0.2\)	0.000	0.001	0.003	0.165	0.441
\(50 \to 25\) (低维降维)	\(\alpha = 0.5\)	0.001	0.004	0.007	0.176	0.423
\(50 \to 25\) (低维降维)	\(\alpha = 1.0\)	0.000	0.000	0.004	0.174	0.435
\(50 \to 100\) (低向高升维)	\(\alpha = 0.2\)	0.000	0.002	0.003	0.086	0.455
\(50 \to 100\) (低向高升维)	\(\alpha = 0.5\)	0.000	0.003	0.005	0.084	0.459
\(50 \to 100\) (低向高升维)	\(\alpha = 1.0\)	0.000	0.002	0.003	0.089	0.450
\(25 \to 50\) (低向高升维)	\(\alpha = 0.2\)	0.000	0.002	0.005	0.113	0.440
\(25 \to 50\) (低向高升维)	\(\alpha = 0.5\)	0.000	0.000	0.001	0.095	0.464
\(25 \to 50\) (低向高升维)	\(\alpha = 1.0\)	0.001	0.003	0.005	0.124	0.436