论文标题
Gromov-Wasserstein的快速和可融合算法在图形数据中
Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data
论文作者
论文摘要
在本文中，我们研究了用于计算Gromov-Wasserstein（GW）距离的一类有效算法的设计和分析。由Luo-Tseng误差界条件〜\ citep {luo1992error}，两种建议的算法，称为Bregman交替投影梯度（BAPG）和混合Bregman近端梯度（HBPG）享受融合保证。在特定于任务的属性下，我们的分析进一步提供了新颖的理论见解，以指导如何选择最佳拟合方法。结果，我们能够提供全面的实验，以验证方法在许多任务中的有效性，包括图形对齐，图形分区和形状匹配。就墙壁锁定时间和建模性能而言，所提出的方法可实现最新的结果。
In this paper, we study the design and analysis of a class of efficient algorithms for computing the Gromov-Wasserstein (GW) distance tailored to large-scale graph learning tasks. Armed with the Luo-Tseng error bound condition~\citep{luo1992error}, two proposed algorithms, called Bregman Alternating Projected Gradient (BAPG) and hybrid Bregman Proximal Gradient (hBPG) enjoy the convergence guarantees. Upon task-specific properties, our analysis further provides novel theoretical insights to guide how to select the best-fit method. As a result, we are able to provide comprehensive experiments to validate the effectiveness of our methods on a host of tasks, including graph alignment, graph partition, and shape matching. In terms of both wall-clock time and modeling performance, the proposed methods achieve state-of-the-art results.
