Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Learning
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~\cite{luo1992error}, two proposed algorithms, called Bregman
Alternating Projected Gradient (BAPG) and hybrid Bregman Proximal Gradient
(hBPG) are proven to be (linearly) convergent. 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.