  The Gromov-Wasserstein distance is a notable extension of optimal transport.
In contrast to the classic Wasserstein distance, it solves a quadratic
assignment problem that minimizes the pair-wise distance distortion under the
transportation of distributions and thus could apply to distributions in
different spaces. These properties make Gromov-Wasserstein widely applicable to
many fields, such as computer graphics and machine learning. However, the
computation of the Gromov-Wasserstein distance and transport plan is expensive.
The well-known Entropic Gromov-Wasserstein approach has a cubic complexity
since the matrix multiplication operations need to be repeated in computing the
gradient of Gromov-Wasserstein loss. This becomes a key bottleneck of the
method. Currently, existing methods accelerate the computation focus on
sampling and approximation, which leads to low accuracy or incomplete transport
plan. In this work, we propose a novel method to accelerate accurate gradient
computation by dynamic programming techniques, reducing the complexity from
cubic to quadratic. In this way, the original computational bottleneck is
broken and the new entropic solution can be obtained with total quadratic time,
which is almost optimal complexity. Furthermore, it can be extended to some
variants easily. Extensive experiments validate the efficiency and
effectiveness of our method.
