GW距离对偶理论大突破！新算法+样本复杂度，图同构检验效率起飞
Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing
📖 AI 总结
该研究提出了一种适用于所有有限支撑度量测度空间的Gromov-Wasserstein（GW）距离对偶性新结果，涵盖有无熵正则化两种情况。基于此对偶形式，作者推导了有限度量空间间经验GW距离的样本复杂度，以及在适当中心化和缩放下的极限分布。此外，论文设计了具有形式收敛保证的新算法来求解正则化GW问题。这些统计与算法进展共同构建了一个高效框架，用于基于样本检验固定节点数图集上两个分布是否同构。该工作将GW距离的理论适用范围从欧氏分布扩展至一般有限空间，为图结构数据的分布比较与同构检测提供了理论支撑和实用工具。
🔑 关键词速览
| Gromov-Wasserstein (GW) distance | 一种度量两个度量测度空间之间差异的距离，仅基于其内在结构，常用于图或分布的比较。 |
| metric measure (mm) space | 带有度量结构和概率测度的空间，用于描述数据点之间的距离和分布。 |
| entropic regularization | 在最优传输问题中加入熵项以平滑解并提高计算效率的正则化技术。 |
| sample complexity | 指为保证估计精度或算法性能所需的样本数量。 |
| isomorphism testing | 检验两个结构（如图）是否在某种变换下等价（同构）的问题。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅