  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 sketching 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.
