The problem of comparing distributions endowed with their own geometry appears in various settings, e.g. when comparing graphs, high-dimensional point clouds, shapes, and generative models. Although the Gromov Wasserstein (GW) distance is usually presented as the natural geometry to handle such comparisons, computing it involves solving a NP-hard problem. In this paper, we propose the Anchor Energy (AE) and Anchor Wasserstein (AW) distances, simpler alternatives to GW that build upon the representation of each point in each distribution as the 1D distribution of its distances to all other points. We propose a sweep line algorithm to compute AE \emph{exactly} in $O(n^2 \log n)$, where $n$ is the size of each measure, compared to a naive implementation of AE requires $O(n^3)$ efforts. This is quasi-linear w.r.t. the description of the problem itself. AW can be pending a single $n^3$ effort, in addition to the $O(n^2)$ cost of running the Sinkhorn algorithm. We also propose robust versions of AE and AW using rank-based criteria rather than cost values. We show in our experiments that the AE and AW distances perform well in 3D shape comparison and graph matching, at a fraction of the computational cost of popular GW approximations.

本文介绍了在机器学习领域中，比较支持异构空间上的两个概率测度的问题。为了解决这个问题， 提出了一种新的 Anchor Energy（AE）和 Anchor Wasserstein（AW）距离。作者提出的算法可以准确地计算AE。在各种实验条件下，AE和AW的表现良好，且计算成本比主流的GW逼近算法低得多。

异质空间概率测度的快速和稳健比较