  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.
