Limit Laws for Gromov-Wasserstein Alignment and Testing for Graph Symmetries

Music City Center 

The Gromov–Wasserstein (GW) problem, rooted in optimal transport theory, considers optimal alignment of metric-measure (mm) spaces that minimizes pairwise distance distortion. As such, it matches up the mm spaces' internal structures and offers a powerful framework for aligning heterogeneous datasets. Despite its broad applicability, a statistical and computational GW theory has started to develop only recently, with the derivation of sharp empirical convergence rates and algorithms for approximate computation subject to non-asymptotic convergence guarantees. In this work, we develop the first limit laws for empirical GW distances and describe consistent resampling schemes. We treat three important settings of GW alignment: (i) discrete-to-discrete (unregularized); (ii) semi-discrete (unregularized); and (iii) general distributions under moment constraints with entropic regularization. In particular, in the discrete case, we show that the limit can be expressed as a solution to a linear program with random Gaussian coefficients, which can be efficiently simulated. This enables inference with the GW distance, which we leverage for an application to graph-isomorphism testing.