论文标题
使用重要性稀疏的Gromov-Wasserstein距离有效近似
Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification
论文作者
论文摘要
作为度量度量空间的有效度量，Gromov-Wasserstein（GW）距离显示了匹配结构化数据（如点云和图形）问题的潜力。但是，由于较高的计算复杂性，其实践中的应用受到限制。为了克服这一挑战，我们提出了一种新颖的重要性稀疏方法，称为\ textsc {spar-gw}，以有效地近似GW距离。特别是，我们的方法没有考虑密集的耦合矩阵，而是利用一种简单但有效的采样策略来构建稀疏的耦合矩阵并使用几乎没有计算进行更新。提出的\ textsc {spar-gw}方法适用于GW距离，并以任意地面成本为单位，并将复杂性从$ o（n^4）$减少到$ o（n^{2+δ}）$，用于任意的小$δ> 0 $。从理论上讲，在轻度的规律性条件下，建立了拟议的GW距离估计的收敛性和一致性。另外，可以扩展此方法以近似GW距离的变体，包括熵GW距离，融合的GW距离和不平衡的GW距离。实验显示了我们的\ textsc {spar-gw}对合成和现实世界任务中最新方法的优越性。
As a valid metric of metric-measure spaces, Gromov-Wasserstein (GW) distance has shown the potential for matching problems of structured data like point clouds and graphs. However, its application in practice is limited due to the high computational complexity. To overcome this challenge, we propose a novel importance sparsification method, called \textsc{Spar-GW}, to approximate GW distance efficiently. In particular, instead of considering a dense coupling matrix, our method leverages a simple but effective sampling strategy to construct a sparse coupling matrix and update it with few computations. The proposed \textsc{Spar-GW} method is applicable to the GW distance with arbitrary ground cost, and it reduces the complexity from $O(n^4)$ to $O(n^{2+δ})$ for an arbitrary small $δ>0$. Theoretically, the convergence and consistency of the proposed estimation for GW distance are established under mild regularity conditions. In addition, this method can be extended to approximate the variants of GW distance, including the entropic GW distance, the fused GW distance, and the unbalanced GW distance. Experiments show the superiority of our \textsc{Spar-GW} to state-of-the-art methods in both synthetic and real-world tasks.
