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.

我们提出了一种新的方法，通过动态规划技术加速精确梯度计算，将复杂度从立方降低到二次，从而突破了原有的计算瓶颈，可以在总二次时间内获得新的熵解，这几乎是最优复杂度。大量实验证实了我们方法的高效性和有效性。