The Gromov-Wasserstein (GW) framework adapts ideas from optimal transport to allow for the comparison of probability distributions defined on different metric spaces. Scalable computation of GW distances and associated matchings on graphs and point clouds have recently been made possible by state-of-the-art algorithms such as S-GWL and MREC. Each of these algorithmic breakthroughs relies on decomposing the underlying spaces into parts and performing matchings on these parts, adding recursion as needed. While very successful in practice, theoretical guarantees on such methods are limited. Inspired by recent advances in the theory of quantization for metric measure spaces, we define Quantized Gromov Wasserstein (qGW): a metric that treats parts as fundamental objects and fits into a hierarchy of theoretical upper bounds for the GW problem. This formulation motivates a new algorithm for approximating optimal GW matchings which yields algorithmic speedups and reductions in memory complexity. Consequently, we are able to go beyond outperforming state-of-the-art and apply GW matching at scales that are an order of magnitude larger than in the existing literature, including datasets containing over 1M points.
翻译:Gromov-Wasserstein (GW) 框架从最理想的运输角度调整观点,以便比较不同计量空间所定义的概率分布。最近,通过S-GWL和MREC等最先进的算法,可以对图形和点云上的GW距离和相关匹配进行可缩放的计算。这些算法的每一个突破都依赖于将基础空间分解成部件并对这些部分进行匹配,从而增加所需的循环。虽然在实践中非常成功,但这类方法的理论保障有限。在计量空间量化理论的最新进展的启发下,我们定义了Quatized Gromov Wasserstein(QGW):一个将部件作为基本对象并适合GW问题理论上层等级的衡量标准。这一表述激励了一种新的算法,以适应最佳的GW匹配,从而产生算法速度的加速和记忆复杂性的减少。因此,我们能够超越表现的状态,在尺度上应用GW匹配,而GW的尺度比现有文献的尺寸要大,包括超过现有M级。