# Resistance Distance and Linearized Optimal Transport on Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 68 references that are in the map.
- First posted on arXiv 23 Apr 2024.

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

- [Linear Optimal Transport Embedding: Provable Wasserstein classification for certain rigid transformations and perturbations](https://mlsanity.com/paper/2008.09165/) (2020)
- [Quantitative stability of optimal transport maps and linearization of the 2-Wasserstein space](https://mlsanity.com/paper/1910.05954/) (2019)
- [The Cumulative Distribution Transform and Linear Pattern Classification](https://mlsanity.com/paper/1507.05936/) (2015)
- [Quadratically-Regularized Optimal Transport on Graphs](https://mlsanity.com/paper/1704.08200/) (2017)
- [Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics](https://mlsanity.com/paper/2202.10723/) (2022)
- [Partitioning signal classes using transport transforms for data analysis and machine learning](https://mlsanity.com/paper/2008.03452/) (2020)
- [Linearized Wasserstein dimensionality reduction with approximation guarantees](https://mlsanity.com/paper/2302.07373/) (2023)
- [The Linearized Hellinger--Kantorovich Distance](https://mlsanity.com/paper/2102.08807/) (2021)
- [Scalable Unbalanced Sobolev Transport for Measures on a Graph](https://mlsanity.com/paper/2302.12498/) (2023)
- [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024)
- [Linear Optimal Partial Transport Embedding](https://mlsanity.com/paper/2302.03232/) (2023)
- [Geometrical Insights for Implicit Generative Modeling](https://mlsanity.com/paper/1712.07822/) (2017)
- [Optimal Transport Based Seismic Inversion: Beyond Cycle Skipping](https://mlsanity.com/paper/2002.00031/) (2020)
- [Linearized optimal transport on manifolds](https://mlsanity.com/paper/2303.13901/) (2023)
- [Manifold learning in Wasserstein space](https://mlsanity.com/paper/2311.08549/) (2023)
- [The quadratic Wasserstein metric for inverse data matching](https://mlsanity.com/paper/1911.06911/) (2019)
- [On a Generalization of Wasserstein Distance and the Beckmann Problem to Connection Graphs](https://mlsanity.com/paper/2312.10295/) (2023)
- [A New Notion of Effective Resistance for Directed Graphs-Part I: Definition and Properties](https://mlsanity.com/paper/1310.5163/) (2013)
- [Computation of Optimal Transport on Discrete Metric Measure Spaces](https://mlsanity.com/paper/1707.06859/) (2017)
- [Transport type metrics on the space of probability measures involving singular base measures](https://mlsanity.com/paper/2201.00875/) (2022)
- [A New Notion of Effective Resistance for Directed Graphs-Part II: Computing Resistances](https://mlsanity.com/paper/1310.5168/) (2013)
- [Vector-Valued Optimal Mass Transport](https://mlsanity.com/paper/1611.09946/) (2016)

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

- [Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs](https://mlsanity.com/paper/2603.26940/) (2026)
- [Neural Algorithmic Reasoning for Graph Saddle Point Problems](https://mlsanity.com/paper/2610.07255/) (2026)

## Abstract (arXiv)

We study the linearization of a discrete transportation distance between probability distributions on finite weighted graphs originally due to Maas (``Gradient flows of the entropy for finite Markov chains,'' J. Funct. Anal. 261(8), 2011) which demonstrates various connections to the underlying combinatorial structure of the graph. For a connected graph and a reference density μ on its vertices, our main result is a nonasymptotic local linearization theorem showing that if nu is a small additive perturbation of μ then their squared discrete transportation distance is controlled above and below by the quadratic form of the pseudoinverse of a re-weighted graph Laplacian matrix. When the reference measure is stationary for the simple random walk on the graph, the weights agree with the original graph and this yields the quadratic form (μ-nu)^top Lw^dagger (μ-nu), which can be viewed as a form of resistance distance between probability measures. This distance has a number of combinatorial and variational characterizations, including Beckmann and Benamou--Brenier formulas, a dual homogeneous Sobolev norm formula, a spanning 2-forest formula, and a representation through random walk hitting times. Finally, we show that on the resulting ``resistance manifold,'' the gradient flow of the chi2 functional is the continuous-time random walk and that its geodesic strong convexity modulus equals the spectral gap of the normalized Laplacian. From this geometric vantage point, one recovers the classical fact that the spectral gap of the normalized Laplacian controls the exponential convergence rate of the random walk to stationarity.