Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound
Comparing structured data from possibly different metric-measure spaces is a
fundamental task in machine learning, with applications in, e.g., graph
classification. The Gromov-Wasserstein (GW) discrepancy formulates a coupling
between the structured data based on optimal transportation, tackling the
incomparability between different structures by aligning the intra-relational
geometries. Although efficient local solvers such as conditional gradient and
Sinkhorn are available, the inherent non-convexity still prevents a tractable
evaluation, and the existing lower bounds are not tight enough for practical
use. To address this issue, we take inspiration from the connection with the
quadratic assignment problem, and propose the orthogonal Gromov-Wasserstein
(OGW) discrepancy as a surrogate of GW. It admits an efficient and closed-form
lower bound with the complexity of $\mathcal{O}(n^3)$, and directly extends to
the fused Gromov-Wasserstein (FGW) distance, incorporating node features into
the coupling. Extensive experiments on both the synthetic and real-world
datasets show the tightness of our lower bounds, and both OGW and its lower
bounds efficiently deliver accurate predictions and satisfactory barycenters
for graph sets.