基于拉普拉斯最优传输的集群感知匹配

arXiv: 2607.16178v1

论文信息

标题: Cluster-Aware Matching via Laplacian Optimal Transport

作者: Gabriel Samberg, YoonHaeng Hur, Yuehaw Khoo, et al.

发布日期: 2026-07-17

arXiv ID: 2607.16178v1

PDF 链接: 下载 PDF

引言：当匹配遇到聚类结构

在许多机器学习和数据科学任务中，点集匹配是一个根本性问题。传统上，匹配旨在建立两个点集之间精确的点到点对应关系，广泛应用于计算机视觉中的刚性/非刚性配准和生物信息学等领域。然而，现实世界中的点云往往不是无结构的散点集合，而是从带有内在聚类结构的分布中采样得到。这些聚类往往代表着对象的语义部件（如人体的四肢、蛋白质的功能基团），因此，更有意义的匹配应当是区域到区域的对齐，而非单纯的点到点对应。

一个直接的做法是：先对每个点云独立聚类，再对聚类结果进行匹配。但这种两阶段方法面临聚类不稳定性的困境，会因分区不一致严重降低后续匹配质量。如图 1(a)所示，对两个相似三维人体形状独立做谱聚类，往往得到不协调的分区，进而导致无法建立有意义的跨对象对应。因此，将匹配与聚类视为耦合问题，通过共享结构信息来提升稳健性，成为一个重要的研究方向。

针对这一挑战，本文提出了拉普拉斯最优传输（Laplacian Optimal Transport, LapOT）框架，通过在最优传输问题中加入基于图拉普拉斯的二次正则化项，使最优耦合天然地遵从点集的簇结构。此外，作者还提出了精炼同步聚类（Refined Simultaneous Clustering, RSC）方法，利用 LapOT 学到的簇感知耦合来生成一致的分区，从而克服独立聚类的局限性。

核心方法：拉普拉斯最优传输 (LapOT)

从最优传输到簇感知匹配

最优传输（OT）是点匹配的一个有力工具。给定两个点集的权重向量 a∈Δna\in\Delta_n, b∈Δmb\in\Delta_m 以及代价矩阵 C∈Rn×mC\in\mathbb{R}^{n\times m}，标准的正则化最优传输问题为：

min⁡π∈Πa,b⟨π,C⟩−λH(π),\min_{\pi\in\Pi_{a,b}} \langle\pi, C\rangle - \lambda H(\pi),

其中 H(⋅)H(\cdot) 为香农熵，λ>0\lambda>0 控制熵正则化强度。这类问题可通过 Sinkhorn 算法高效求解。然而，标准 OT 并未利用点集内部的相似性结构，无法保证最优耦合矩阵具有块状结构或平滑性，从而难以实现区域级的匹配。

拉普拉斯正则化的引入

LapOT 的核心思想是在 OT 目标中加入两项拉普拉斯二次型，以强调在点云的相似图中相邻的点（很可能属于同一簇）应具有相似的匹配模式。具体地，为点集 {Xi}\{X_i\} 和 {Yj}\{Y_j\} 分别构建相似矩阵 KX∈Rn×nK_X\in\mathbb{R}^{n\times n}、KY∈Rm×mK_Y\in\mathbb{R}^{m\times m}（如高斯核 e−d2/σe^{-d^2/\sigma} 或图的邻接矩阵）。定义非归一化图拉普拉斯矩阵 LX=diag(KX1n)−KXL_X = \mathrm{diag}(K_X 1_n) - K_X 和 LYL_Y 同理。对于耦合矩阵 π\pi，我们有：

⟨π,LXπ⟩=12∑i,i′(KX)ii′∥πi−πi′∥22,⟨π,πLY⟩=12∑j,j′(KY)jj′∥π⋅j−π⋅j′∥22,\langle\pi, L_X\pi\rangle = \frac12 \sum_{i,i'} (K_X)_{ii'} \|\pi_i - \pi_{i'}\|_2^2,\quad \langle\pi, \pi L_Y\rangle = \frac12 \sum_{j,j'} (K_Y)_{jj'} \|\pi_{\cdot j} - \pi_{\cdot j'}\|_2^2,

其中 πi\pi_i 表示 π\pi 的第 ii 行（点 XiX_i 的匹配分布），π⋅j\pi_{\cdot j} 为第 jj 列。加入后，LapOT 问题定义为：

min⁡π∈Πa,b⟨π,C⟩+λx⟨π,LXπ⟩+λy⟨π,πLY⟩−λH(π).\min_{\pi\in\Pi_{a,b}} \langle\pi, C\rangle + \lambda_x\langle\pi, L_X\pi\rangle + \lambda_y\langle\pi, \pi L_Y\rangle - \lambda H(\pi).

直观上，若 (KX)ii′(K_X)_{ii'} 较大，即 XiX_i 和 Xi′X_{i'} 相似，则惩罚 ∥πi−πi′∥2\|\pi_i - \pi_{i'}\|^2 迫使它们的匹配分布接近；对于 YY 也一样。因此，最优耦合的行和列在相似图的平滑区域趋于相似，呈现出簇结构。当 λx=λy=0\lambda_x= \lambda_y=0 时，LapOT 退化回标准熵正则化 OT。

低秩扩展与优化

鉴于 LapOT 促使耦合具有低秩结构，作者进一步引入了基于非负秩的低秩 LapOT：将耦合约束为 π=Udiag(1r/g)V⊤\pi = U \mathrm{diag}(1_r/g) V^\top，其中 U∈R+n×rU\in\mathbb{R}^{n\times r}_+, V∈R+m×rV\in\mathbb{R}^{m\times r}_+, g∈R+rg\in\mathbb{R}^r_+ 且满足边际约束。优化采用镜像下降结合 Dykstra 算法，通过对 UU, VV, gg 进行交替投影，能够高效求解大规模问题，克服一般凸优化内点法的限制。

理论保证：簇感知性的严格刻画

论文的核心理论贡献在于严格证明了 LapOT 的解确实会被驱动到与簇结构一致的块常数形式。定理 1 假定 LXL_X 和 LYL_Y 来自具有 rr 和 ss 个连通分量的图（对应真实的簇），则最优耦合 π⋆\pi^\star 与它的行/列块平均之间的 Frobenius 偏差满足：

∥π⋆−PX,rπ⋆∥F2≤∥PX,rC−C∥∞λxμr+1X,∥π⋆−π⋆PY,s∥F2≤∥CPY,s−C∥∞λyμs+1Y,\|\pi^\star - P_{X,r}\pi^\star\|_F^2 \le \frac{\|P_{X,r}C - C\|_\infty}{\lambda_x \mu_{r+1}^X}, \quad \|\pi^\star - \pi^\star P_{Y,s}\|_F^2 \le \frac{\|C P_{Y,s} - C\|_\infty}{\lambda_y \mu_{s+1}^Y},

其中 PX,rP_{X,r} 是投影到 LXL_X 零特征空间（即簇指示向量空间）的算子，μr+1X\mu_{r+1}^X 是 LXL_X 的第一个非零特征值（表征簇间分离度）。当代价矩阵本身是块常数时（PX,rC=CP_{X,r}C=C 或 CPY,s=CC P_{Y,s}=C），则 π⋆\pi^\star 严格等于它的块平均，且非负秩不超过 rr 或 ss（推论 1）。当正则化参数 λx,λy→∞\lambda_x,\lambda_y\to\infty 时，π⋆\pi^\star 收敛到只考虑块平均代价的 OT 解（命题 1）。

当相似图为连通图时（例如实验中的 RBF 核图），定理 1 的理想假设不成立。命题 2 扩展至一般图：对于任意图拉普拉斯，π⋆\pi^\star 与其在低频率特征空间投影之间的偏差，由目标函数值差额和谱间隙控制。这为在连通图场景下应用 LapOT 提供了理论保障，即耦合集中在扩散算子的前几个特征向量上，近似于低秩的簇结构。这一后验界可在实验中计算，验证了方法在股票市场数据上的有效性。

精炼同步聚类 (RSC)：从耦合到一致分区

基于 LapOT 学到的簇感知耦合，作者提出了 RSC 算法，实现两个点云的一致分区：

  1. 求解 LapOT 以获得最优耦合 π⋆\pi^\star。
  2. 对 π⋆\pi^\star 的行和列分别应用 k-means（簇数为 k′k'），构建开关矩阵 πswitchX\pi^X_{\text{switch}} 和 πswitchY\pi^Y_{\text{switch}}，记录点是否属于同一粗分簇。
  3. 将初始相似矩阵 KXK_X, KYK_Y 与开关矩阵逐元素相乘，消去跨粗分簇的相似边，得到精炼相似矩阵 K~X\tilde{K}_X, K~Y\tilde{K}_Y。
  4. 基于 L~X\tilde{L}_X, L~Y\tilde{L}_Y 执行谱聚类（最终簇数 kk），产生最终一致分区。

开关矩阵捕捉了由匹配驱动的粗略簇结构（通常 k′k' 略大于 k/2k/2），为后续精细聚类提供了对齐的先验。实验显示（图 1(b), 图 3），RSC 克服了独立聚类的分割不一致问题，成功对人体、狗、海豚等三维形状生成语义一致且自然的聚类结果。

实验与分析

在三维形状的刚性配准任务中，RSC 被用于估计两个点云之间的旋转。首先通过 RSC 获得 5 个对齐的簇，然后在簇内进行距离分布匹配，最后用正交 Procrustes 问题估计旋转。与全局距离分布匹配（DPM）和 ICP 流水线对比，随着噪声水平增加（SNR 下降），RSC 的配准误差始终低于全局 DPM 和 ICP（表 1）。尤其在高噪声时（SNR≈2.91 dB），全局 DPM 的相对误差为 0.255，而 RSC 为 0.202，显示出簇约束匹配的鲁棒性。

在非欧几里得金融应用中，论文对 S&P 500 和日本股市前 50 只股票基于 5 年日回报率构建相关图，并用 Beta 值构造运输代价矩阵。LapOT 最优耦合可视化呈现明显的低秩或块结构（图 6），表明跨市场公司的行业簇大致对齐。对命题 2 的数值验证（图 7）表明，随着保留的前 ll 个特征向量增加，理论界与实际投影误差同时下降，证实了连通图下拉普拉斯正则化促使耦合集中在低频特征空间。

实践应用建议与未来方向

应用建议：

  • 相似图构建：选择适当的核函数和带宽至关重要。在已知簇数时，可以尝试构造稀疏图以突出簇结构；对于完全连通图，可通过加大 λx\lambda_x, λy\lambda_y 或利用命题 2 的后验界调整参数。
  • LapOT 超参：λx\lambda_x, λy\lambda_y 控制行/列平滑程度，可通过交叉验证或直接监控耦合的块常数性（如计算行/列的方差）来调节。λ\lambda 控制熵正则化水平，建议在数值稳定范围内取较小值。
  • RSC 策略：粗分簇数 k′k' 建议设为 kk 的 0.5-0.7 倍，以保留足够细粒度。对于大规模问题，可使用低秩 LapOT (rank r≈10r\approx 10) 加速。
  • 金融聚类：可结合多种距离度量（如相关性、Beta、波动率）构造多重代价矩阵，获得更丰富的跨市场对齐。

未来方向：

  • 发展自适应选择 λx,λy\lambda_x,\lambda_y 的方案，特别是当点云规模或簇数不同时。
  • 将 LapOT 推广到多图匹配和部分匹配问题，处理缺失点或异常值。
  • 结合深度学习，学习点云的潜在表示和相似图，实现端到端的簇感知匹配。
  • 增强对非平衡数据的鲁棒性，当边际分布与簇结构不一致时，需设计更灵活的约束。

总结

《Cluster-Aware Matching via Laplacian Optimal Transport》提出了一种创新且理论完备的框架，将聚类结构直接嵌入到最优传输匹配中。LapOT 通过图拉普拉斯正则化，自然地驱动耦合矩阵呈现块状平滑，从而实现区域级的稳健配准。严谨的理论分析不仅解释了理想簇分离场景下的精确恢复，还提供了连通图情况的后验界限，架起了理论与实践的桥梁。RSC 方法进一步将这种耦合转化为双向一致的分区，在三维形状配准和金融聚类中展现出优异性能。这项工作为匹配与聚类的联合学习开辟了新途径，对需要簇感知对齐的众多应用领域具有重要参考价值。