# Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching

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

## Key facts

- Cited by 103 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2019.

## Built on by (most cited first, 30 of 103)

- [CLIP-Event: Connecting Text and Images with Event Structures](https://mlsanity.com/paper/2201.05078/) (2022)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [Online Graph Dictionary Learning](https://mlsanity.com/paper/2102.06555/) (2021)
- [Graph Auto-Encoder Via Neighborhood Wasserstein Reconstruction](https://mlsanity.com/paper/2202.09025/) (2022)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Hierarchical Multi-Marginal Optimal Transport for Network Alignment](https://mlsanity.com/paper/2310.04470/) (2023)
- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (2022)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Template based Graph Neural Network with Optimal Transport Distances](https://mlsanity.com/paper/2205.15733/) (2022)
- [Quantized Gromov-Wasserstein](https://mlsanity.com/paper/2104.02013/) (2021)
- [Implicit Graphon Neural Representation](https://mlsanity.com/paper/2211.03329/) (2022)
- [Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics](https://mlsanity.com/paper/2505.12709/) (2025)
- [On Transportation of Mini-batches: A Hierarchical Approach](https://mlsanity.com/paper/2102.05912/) (2021)
- [ZegOT: Zero-shot Segmentation Through Optimal Transport of Text Prompts](https://mlsanity.com/paper/2301.12171/) (2023)
- [DIGRAC: Digraph Clustering Based on Flow Imbalance](https://mlsanity.com/paper/2106.05194/) (2021)
- [Wasserstein Barycenter-based Model Fusion and Linear Mode Connectivity of Neural Networks](https://mlsanity.com/paper/2210.06671/) (2022)
- [Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport](https://mlsanity.com/paper/2301.12721/) (2023)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications](https://mlsanity.com/paper/2306.15963/) (2023)
- [Enhancing CLIP Robustness via Cross-Modality Alignment](https://mlsanity.com/paper/2510.24038/) (2025)
- [It's a (Blind) Match! Towards Vision-Language Correspondence without Parallel Data](https://mlsanity.com/paper/2503.24129/) (2025)
- [DistDF: Time-Series Forecasting Needs Joint-Distribution Wasserstein Alignment](https://mlsanity.com/paper/2510.24574/) (2025)
- [Entropic Gromov-Wasserstein between Gaussian Distributions](https://mlsanity.com/paper/2108.10961/) (2021)
- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [The Z-Gromov-Wasserstein Distance](https://mlsanity.com/paper/2408.08233/) (2024)
- [InfiGFusion: Graph-on-Logits Distillation via Efficient Gromov-Wasserstein for Model Fusion](https://mlsanity.com/paper/2505.13893/) (2025)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)

## Abstract (arXiv)

We propose a scalable Gromov-Wasserstein learning (S-GWL) method and establish a novel and theoretically-supported paradigm for large-scale graph analysis. The proposed method is based on the fact that Gromov-Wasserstein discrepancy is a pseudometric on graphs. Given two graphs, the optimal transport associated with their Gromov-Wasserstein discrepancy provides the correspondence between their nodes and achieves graph matching. When one of the graphs has isolated but self-connected nodes (i.e., a disconnected graph), the optimal transport indicates the clustering structure of the other graph and achieves graph partitioning. Using this concept, we extend our method to multi-graph partitioning and matching by learning a Gromov-Wasserstein barycenter graph for multiple observed graphs; the barycenter graph plays the role of the disconnected graph, and since it is learned, so is the clustering. Our method combines a recursive K-partition mechanism with a regularized proximal gradient algorithm, whose time complexity is O(K(E+V)logK V) for graphs with V nodes and E edges. To our knowledge, our method is the first attempt to make Gromov-Wasserstein discrepancy applicable to large-scale graph analysis and unify graph partitioning and matching into the same framework. It outperforms state-of-the-art graph partitioning and matching methods, achieving a trade-off between accuracy and efficiency.