  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 \emph{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 \emph{closed-form} lower bound with $\mathcal{O}(n^3)$
complexity, 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.
