Abstract
The Gromov-Wasserstein (GW) distance enables comparing metric measure spaces based solely on their internal structure, making it invariant to isomorphic transformations. This property is particularly useful for comparing datasets that naturally admit isomorphic representations, such as unlabelled graphs or objects embedded in space. However, apart from the recently derived empirical convergence rates for the quadratic GW problem, a statistical theory for valid estimation and inference remains largely obscure. Pushing the frontier of statistical GW further, this work derives the first limit laws for the empirical GW distance across several settings of interest: (i) discrete, (ii) semi-discrete, and (iii) general distributions under moment constraints under the entropically regularized GW distance. The derivations rely on a novel stability analysis of the GW functional in the marginal distributions. The limit laws then follow by an adaptation of the functional delta method. As asymptotic normality fails to hold in most cases, we establish the consistency of an efficient estimation procedure for the limiting law in the discrete case, bypassing the need for computationally intensive resampling methods. We apply these findings to testing whether collections of unlabelled graphs are generated from distributions that are isomorphic to each other.
Introduction
The Gromov-Wasserstein (GW) distance has emerged as a cornerstone in optimal transport for comparing structured datasets that lack a common coordinate system. By focusing on internal metric structures rather than external embeddings, GW distance provides a natural metric for comparing unlabelled graphs, protein structures, and single-cell genomic data. It is inherently "isomorphism-invariant," meaning it measures the discrepancy between the underlying structures of two objects regardless of how they are oriented or labeled.
However, despite its widespread application in machine learning, the statistical foundations of GW distance—specifically its asymptotic behavior as sample sizes increase—remained largely uncharacterized. This work establishes the first limit laws for the empirical GW distance, providing the rigorous framework necessary for performing hypothesis testing and structural alignment with statistical certainty.
The Statistical Challenge
The core difficulty in analyzing GW distance lies in its quadratic nature. Unlike standard Optimal Transport (OT), which is a linear program, GW involves a quadratic optimization problem that is generally NP-hard. This complexity extends to its statistical properties; until now, we lacked the "limit laws" necessary to determine the distribution of the empirical GW distance as sample sizes ($n$) grow. Without these laws, researchers cannot calculate p-values or construct confidence intervals, leaving structural comparisons without a measure of statistical significance. We cannot say with certainty whether two graph models are truly isomorphic or merely look similar due to sampling noise.
Methodology: Linearizing the Quadratic
The authors bridge this gap by leveraging a recently discovered variational formulation of the quadratic GW problem. This approach effectively "linearizes" the functional, expressing the GW distance as an infimum over a family of standard (linear) optimal transport problems.
Using this formulation, they apply the functional delta method—a robust statistical tool for deriving the distribution of functionals of empirical measures—to derive limit laws across three critical regimes:
- Discrete: Comparing finite point sets or specific graphs.
- Semi-discrete: Comparing a finite sample to a continuous distribution.
- Entropic: Comparing general distributions using entropically regularized GW distance, a common technique used to speed up OT computations.
Beyond the Naive Bootstrap
A significant finding of this research is that the limit distribution of the GW distance is often non-Gaussian (it does not follow a standard bell curve). This has profound implications for practitioners: the standard "naive bootstrap" method, commonly used to estimate error bars by resampling data, fails to provide valid inference in this context because the non-linearity of the GW derivative at the point of isomorphism breaks standard assumptions.
To address this, the authors propose a direct estimation procedure. By solving a sequence of linear programs, they can simulate the limiting law under the null hypothesis. This method is significantly more efficient than attempting to solve the original NP-hard GW problem repeatedly through resampling, making statistical inference computationally feasible for structured data.
Applications: Graph Isomorphism Testing
The theoretical results are applied to the problem of testing graph isomorphism. The authors introduce a clever way to embed graph distributions into Euclidean space such that the GW distance between the embeddings is zero if and only if the original graph models are isomorphic.
Their proposed test is proven to be "consistent," meaning the probability of correctly identifying non-isomorphic graphs approaches 1 as the number of samples increases. Numerical experiments on random graph models and continuous shapes (such as 3D cubes and spheres) validate these findings, showing that Type 1 errors (false positives) correctly approach the target significance level as the number of sampled graphs increases.
Key Results and Insights
- First-of-their-kind Limit Laws: The paper provides the first rigorous proofs for the distributional limits of empirical GW distances.
- Entropic Normality: The authors show that while the standard GW limit is complex, the entropically regularized GW distance becomes Gaussian once the regularization parameter is sufficiently high, allowing for simpler inference in those specific cases.
- Computational Efficiency: By reducing the estimation of the limit distribution to linear programming, the authors bypass the computational bottlenecks of traditional resampling.
Limitations and Future Work
While this work marks a major step forward, several challenges remain. The current variational framework relies heavily on the properties of Euclidean spaces; extending these limit laws to general metric spaces, such as manifolds or hyperbolic spaces, remains an open problem. Additionally, while the direct estimator is efficient, the initial "graph matching" step required to initialize the solver still faces scaling issues with very large graphs. Finally, while the authors provide limit laws for the regularized continuous case, the unregularized continuous case remains a difficult theoretical frontier.
Summary updated