# Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 45 references that are in the map.
- First posted on arXiv 22 Feb 2022.

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

- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Joint Distribution Optimal Transportation for Domain Adaptation](https://mlsanity.com/paper/1705.08848/) (2017)
- [Persistence Images: A Stable Vector Representation of Persistent Homology](https://mlsanity.com/paper/1507.06217/) (2015)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [Missing Data Imputation using Optimal Transport](https://mlsanity.com/paper/2002.03860/) (2020)
- [Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem](https://mlsanity.com/paper/1905.11882/) (2019)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Tree-Sliced Variants of Wasserstein Distances](https://mlsanity.com/paper/1902.00342/) (2019)
- [Learning Generative Models across Incomparable Spaces](https://mlsanity.com/paper/1905.05461/) (2019)
- [Point-set Distances for Learning Representations of 3D Point Clouds](https://mlsanity.com/paper/2102.04014/) (2021)
- [Outlier-Robust Optimal Transport](https://mlsanity.com/paper/2012.07363/) (2020)
- [Asymptotic Guarantees for Learning Generative Models with the Sliced-Wasserstein Distance](https://mlsanity.com/paper/1906.04516/) (2019)
- [Persistence Fisher Kernel: A Riemannian Manifold Kernel for Persistence Diagrams](https://mlsanity.com/paper/1802.03569/) (2018)
- [Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent](https://mlsanity.com/paper/2106.08502/) (2021)
- [Sobolev GAN](https://mlsanity.com/paper/1711.04894/) (2017)
- [Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search](https://mlsanity.com/paper/2006.07593/) (2020)
- [Statistical Analysis of Wasserstein Distributionally Robust Estimators](https://mlsanity.com/paper/2108.02120/) (2021)
- [Testing Group Fairness via Optimal Transport Projections](https://mlsanity.com/paper/2106.01070/) (2021)
- [Kernel method for persistence diagrams via kernel embedding and weight factor](https://mlsanity.com/paper/1706.03472/) (2017)
- [Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport](https://mlsanity.com/paper/1905.10812/) (2019)
- [Diffusion Earth Mover's Distance and Distribution Embeddings](https://mlsanity.com/paper/2102.12833/) (2021)
- [Dynamical Optimal Transport on Discrete Surfaces](https://mlsanity.com/paper/1809.07083/) (2018)
- [Entropy Partial Transport with Tree Metrics: Theory and Practice](https://mlsanity.com/paper/2101.09756/) (2021)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Adversarial Regression with Doubly Non-negative Weighting Matrices](https://mlsanity.com/paper/2109.14875/) (2021)

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

- [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)
- [Optimal Transport for Measures with Noisy Tree Metric](https://mlsanity.com/paper/2310.13653/) (2023)
- [Tree-Sliced Wasserstein Distance: A Geometric Perspective](https://mlsanity.com/paper/2406.13725/) (2024)
- [Scalable Counterfactual Distribution Estimation in Multivariate Causal Models](https://mlsanity.com/paper/2311.00927/) (2023)
- [Distance-Based Tree-Sliced Wasserstein Distance](https://mlsanity.com/paper/2503.11050/) (2025)
- [Few-Shot Object Detection via Synthetic Features with Optimal Transport](https://mlsanity.com/paper/2308.15005/) (2023)
- [Efficient approximation of Earth Mover's Distance Based on Nearest Neighbor Search](https://mlsanity.com/paper/2401.07378/) (2024)
- [Tree-Sliced Wasserstein Distance with Nonlinear Projection](https://mlsanity.com/paper/2505.00968/) (2025)
- [Resistance Distance and Linearized Optimal Transport on Graphs](https://mlsanity.com/paper/2404.15261/) (2024)
- [Spherical Tree-Sliced Wasserstein Distance](https://mlsanity.com/paper/2503.11249/) (2025)
- [SAVA: Scalable Learning-Agnostic Data Valuation](https://mlsanity.com/paper/2406.01130/) (2024)
- [Scalable Sobolev IPM for Probability Measures on a Graph](https://mlsanity.com/paper/2502.00737/) (2025)
- [Graph Fourier MMD for Signals on Graphs](https://mlsanity.com/paper/2306.02508/) (2023)
- [An Empirical Study of Self-supervised Learning with Wasserstein Distance](https://mlsanity.com/paper/2310.10143/) (2023)
- [An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph](https://mlsanity.com/paper/2502.00739/) (2025)
- [Generalized Sobolev IPM for Graph-Based Measures](https://mlsanity.com/paper/2510.25591/) (2025)
- [Sobolev--Ricci Curvature](https://mlsanity.com/paper/2603.12652/) (2026)

## Abstract (arXiv)

Optimal transport (OT) is a popular measure to compare probability distributions. However, OT suffers a few drawbacks such as (i) a high complexity for computation, (ii) indefiniteness which limits its applicability to kernel machines. In this work, we consider probability measures supported on a graph metric space and propose a novel Sobolev transport metric. We show that the Sobolev transport metric yields a closed-form formula for fast computation and it is negative definite. We show that the space of probability measures endowed with this transport distance is isometric to a bounded convex set in a Euclidean space with a weighted ℓp distance. We further exploit the negative definiteness of the Sobolev transport to design positive-definite kernels, and evaluate their performances against other baselines in document classification with word embeddings and in topological data analysis.