# Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound

arXiv: https://arxiv.org/abs/2205.05838 · HTML: https://mlsanity.com/paper/2205.05838/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 41 references that are in the map.
- First posted on arXiv 12 May 2022.

## Builds on (most cited first, 11 of 11)

- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Similarity of Neural Network Representations Revisited](https://mlsanity.com/paper/1905.00414/) (2019)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Sliced Gromov-Wasserstein](https://mlsanity.com/paper/1905.10124/) (2019)
- [GraKeL: A Graph Kernel Library in Python](https://mlsanity.com/paper/1806.02193/) (2018)

## Built on by (most cited first, 3 of 3)

- [A Novel Sliced Fused Gromov-Wasserstein Distance](https://mlsanity.com/paper/2508.02364/) (2025)
- [Optimal Transport for Kernel Gaussian Mixture Models](https://mlsanity.com/paper/2310.18586/) (2023)
- [Gromov-Monge Flow Matching for Equivariant Graph Generation](https://mlsanity.com/paper/2608.26961/) (2026)

## Abstract (arXiv)

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 O(n3) 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.