基于拉普拉斯最优传输的聚类感知匹配

Cluster-Aware Matching via Laplacian Optimal Transport

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

3 分钟速览

  • 研究问题：在点云匹配中，传统方法追求精确的点对点对应，但当点云具有内在聚类结构时，区域到区域的对齐更为稳健。论文解决的是如何将聚类结构信息直接融入匹配过程，实现 “聚类感知” 的匹配。

  • 核心方法：提出拉普拉斯最优传输（LapOT），在经典最优传输问题中加入基于图拉普拉斯的二次正则化项，强制最优耦合矩阵的行与列遵从点云的相似性图结构；并在此基础上设计精炼同步聚类（RSC），利用该耦合矩阵生成跨点云的一致性聚类。

  • 关键结果：理论证明当正则化参数足够大或成本矩阵呈块常数时，最优耦合矩阵会退化为块常数结构，其非负秩不超过聚类数（见定理 1 及推论 1）；在 3D 形状对齐实验中，提出的方法在高噪声下比全局距离轮廓匹配（DPM）更鲁棒（见表 1，SNR=2.91dB 时相对误差 0.202 vs 0.255）。

  • 主要局限：方法性能依赖相似性图构造和正则化超参数的选择，论文未给出自动调参方案；低秩扩展算法需要用户指定秩 rr 和稳定参数 α\alpha。

  • 适合读者：从事形状匹配、3D 视觉、最优传输应用以及多视图聚类研究的学生与工程师。特别适合希望在匹配中显式利用数据几何结构的读者。

论文背景和研究动机

点云匹配是计算机视觉与模式识别中的基本问题，旨在建立两个点集之间有意义的对应关系。经典方法如二次匹配虽然直接比较点对之间的相对几何关系，却是 NP 难问题；基于轮廓（profile）的最优传输方法将匹配转化为线性规划，可高效求解，但仅依赖单点轮廓信息，忽略了区域级别的内在结构。

论文观察到，许多实际点云并非无结构散点，而是具有明显聚类结构的分布样本。例如人体点云中四肢、躯干自然形成不同聚类。此时点级别的精确匹配往往意义不大——同一区域内单点之间几乎可以任意互换。独立对两个点云分别聚类再进行簇匹配的思路看似自然，但聚类算法固有的不稳定性会导致两个点云上分区不一致，严重损害后续匹配质量（见图 1a）。

这一洞察催生了本文的核心动机：将匹配与聚类视为耦合问题，让匹配过程本身感知并利用聚类结构。

核心方法和技术细节

拉普拉斯最优传输（LapOT）

给定源点云 {X1,…,Xn}\{X_1,\dots,X_n\} 和目标点云 {Y1,…,Ym}\{Y_1,\dots,Y_m\}，用户首先在各点云上构建相似性图 KX∈Rn×nK_X\in\mathbb{R}^{n\times n} 和 KY∈Rm×mK_Y\in\mathbb{R}^{m\times m}（如通过 RBF 核）。随后计算未归一化的图拉普拉斯矩阵 LX=diag(KX1n)−KXL_X = \mathrm{diag}(K_X\mathbf{1}_n) - K_X 和 LYL_Y。

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)

这两个二次项的作用可以从行－列视角理解：

⟨π,LXπ⟩=12∑i,i′(KX)ii′∥πi−πi′∥22\langle\pi, L_X\pi\rangle = \frac12\sum_{i,i'}(K_X)_{ii'}\|\pi_{i} - \pi_{i'}\|_2^2

当 XiX_i 和 Xi′X_{i'} 相似（(KX)ii′(K_X)_{ii'} 大），该惩罚鼓励它们在目标点云上的匹配分布 πi\pi_i 与 πi′\pi_{i'} 接近。于是相似源点的 “命运” 被耦合在一起。对称地，⟨π,πLY⟩\langle\pi, \pi L_Y\rangle 对目标点施加同样约束。

当 λx=λy=0\lambda_x = \lambda_y = 0，问题退化为标准熵正则最优传输。具体优化采用文献 [21] 的专用算法，基于 Sinkhorn 子程序迭代，在 λ\lambda 足够大时迭代次数独立于耦合规模。

低秩扩展

针对大规模问题，论文提出低秩版本。利用非负秩定义，强制耦合矩阵在复形 C(a,b,r)\mathcal{C}(a,b,r) 上分解为 Udiag(1r/g)V⊤U\mathrm{diag}(\mathbf{1}_r/g)V^\top。优化采用 KL 散度下的镜像下降法，Dykstra 算法交替投影至 C1\mathcal{C}_1 和 C2\mathcal{C}_2，自适应步长方案避免数值溢出。

精炼同步聚类（RSC）

算法流程（见算法 1）：

  1. 求解 LapOT 获得最优耦合 π⋆\pi^\star。
  2. 对 π⋆\pi^\star 的行和列分别应用 k′k'-means 聚类，构建 “开关矩阵” πswitchX\pi^X_{\mathsf{switch}}、πswitchY\pi^Y_{\mathsf{switch}}（同簇标记为 1，否则为 0）。
  3. 将原相似性矩阵与开关矩阵逐点相乘，得到精炼相似性矩阵 K~X\tilde{K}_X、K~Y\tilde{K}_Y。
  4. 重新计算图拉普拉斯后执行标准谱聚类，获得最终 kk 个簇。

开关矩阵引入的巧妙之处在于：通过聚类耦合矩阵的行（或列），将共享的匹配信息转化为对原始相似性图的筛选，切断跨簇的相似性边，从而缓解独立聚类的不稳定性。

创新点和贡献

理论层面，论文建立了 LapOT 解的簇约束性质。定理 1 指出，当 LXL_X、LYL_Y 分别由 rr、ss 个连通分支的图诱导时，耦合矩阵与其块平均化的偏差可由成本矩阵的逼近误差和谱隙控制：

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

推论 1 进一步保证：当成本矩阵在聚类划分上呈块常数时，最优耦合退化为确切的块常数矩阵，非负秩不超过聚类数。命题 2 将理论推广至连通图情形：解集中于图拉普拉斯的低频谱空间，从而解释近似聚类结构如何浮现。

方法层面，LapOT+RSC 提供了首个将匹配一致性反馈至聚类过程的端到端框架，相较 “先独立聚类再匹配” 的两阶段方案，显著提高了跨点云聚类的一致性（图 1 的直观对比）。

实验结果分析

3D 形状聚类与对齐

在 CAPOD 数据集上，RSC 在两个人体、狗、海豚形状上都产出一致且语义连贯的聚类，独立谱聚类则出现碎片化且不对应的分区。基于 RSC 的对齐流水线在高噪声下的刚性变换估计中表现出优异的鲁棒性：SNR=2.91dB 时，所提方法相对误差 0.202，低于全局 DPM 的 0.255 和 ICP 的 2.511（表 1），体现了簇约束有助于过滤异常匹配的潜力。

金融市场数据

在 S&P 500 与日本 Top 50 股票的联合聚类中，以 5 年日收益相关系数定义图相似性，以系统性风险（贝塔）定义成本矩阵。拉普拉斯正则化促使耦合矩阵呈现近似低秩块状结构（图 6），RSC 所得聚类反映出跨国家的行业板块对应（如半导体与汽车制造）。论文还数值验证了命题 2：投影误差随着低频特征空间维度增加而递减，且被理论上界控制（图 7）。

实践建议

  1. 点云配准任务：对于具有明显局部聚类结构的高维或三维点云（如人体关键点、分子构象），推荐在 RSC 框架下建立粗到细的对应关系。先以 LapOT 获得一致性聚类分块，在匹配簇内再做点级匹配，可有效抵御高噪声和异常值。

  2. 超参数配置：实现中需注意相似性图的构建方式（RBF 核的带宽 σ\sigma）、正则化强度 λx,λy\lambda_x, \lambda_y 和开关矩阵的预聚类数 k′k'。论文建议 k′k' 略高于最终聚类数 kk 的一半；使用基于度分布的非均匀边际权重（ai∝∑j(KX)ija_i \propto \sum_j (K_X)_{ij}）有助于突出图结构中的关键节点。

  3. 计算效率：在小规模问题上直接用凸优化器求解 LapOT；在大规模问题上可启用低秩扩展并谨慎设置稳定参数 α\alpha（例如取 10−310^{-3} 量级）。镜像下降的自适应步长取 γ∈[1,10]\gamma\in[1,10] 可保证数值稳定性。