期刊
MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, ECML PKDD 2021: RESEARCH TRACK, PT III
卷 12977, 期 -, 页码 811-827出版社
SPRINGER INTERNATIONAL PUBLISHING AG
DOI: 10.1007/978-3-030-86523-8_49
关键词
Gromov-Wasserstein distance; Optimal transport; Metric space registration
The Gromov-Wasserstein (GW) framework allows for comparing probability distributions on different metric spaces, with recent algorithms enabling scalable computation of GW distances. The newly defined Quantized Gromov Wasserstein (qGW) introduces a metric treating parts as fundamental objects and fitting into a hierarchy of theoretical upper bounds. This formulation leads to a new algorithm for approximating optimal GW matchings, resulting in algorithmic speedups and reductions in memory complexity, allowing application at larger scales than previously seen in the literature.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据