# Geometry of Graph Partitions via Optimal Transport

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

## Key facts

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

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

- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)
- [Unsupervised Ground Metric Learning using Wasserstein Singular Vectors](https://mlsanity.com/paper/2102.06278/) (2021)
- [Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2205.08115/) (2022)
- [Graph Cuts with Arbitrary Size Constraints Through Optimal Transport](https://mlsanity.com/paper/2402.04732/) (2024)
- [Implications of Distance over Redistricting Maps: Central and Outlier Maps](https://mlsanity.com/paper/2203.00872/) (2022)
- [Fused Gromov-Wasserstein Distance with Feature Selection](https://mlsanity.com/paper/2605.12161/) (2026)

## Abstract (arXiv)

We define a distance metric between partitions of a graph using machinery from optimal transport. Our metric is built from a linear assignment problem that matches partition components, with assignment cost proportional to transport distance over graph edges. We show that our distance can be computed using a single linear program without precomputing pairwise assignment costs and derive several theoretical properties of the metric. Finally, we provide experiments demonstrating these properties empirically, specifically focusing on its value for new problems in ensemble-based analysis of political districting plans.