# Scalable Unbalanced Sobolev Transport for Measures on a Graph arXiv: https://arxiv.org/abs/2302.12498 ยท HTML: https://mlsanity.com/paper/2302.12498/ ## Key facts - Cited by 10 papers in the map (data through 14 Oct 2026). - Builds on 39 of its 61 references that are in the map. - First posted on arXiv 24 Feb 2023. ## Builds on (most cited first, 30 of 39) - [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018) - [Persistence Images: A Stable Vector Representation of Persistent Homology](https://mlsanity.com/paper/1507.06217/) (2015) - [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015) - [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018) - [Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measures](https://mlsanity.com/paper/1508.07941/) (2015) - [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) - [Proximal Optimal Transport Modeling of Population Dynamics](https://mlsanity.com/paper/2106.06345/) (2021) - [Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation](https://mlsanity.com/paper/2010.05862/) (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) - [On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm](https://mlsanity.com/paper/2002.03293/) (2020) - [Sinkhorn Divergences for Unbalanced Optimal Transport](https://mlsanity.com/paper/1910.12958/) (2019) - [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) - [Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search](https://mlsanity.com/paper/2006.07593/) (2020) - [Outlier-Robust Optimal Transport: Duality, Structure, and Statistical Analysis](https://mlsanity.com/paper/2111.01361/) (2021) - [Bending Graphs: Hierarchical Shape Matching using Gated Optimal Transport](https://mlsanity.com/paper/2202.01537/) (2022) - [Testing Group Fairness via Optimal Transport Projections](https://mlsanity.com/paper/2106.01070/) (2021) - [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022) - [Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport](https://mlsanity.com/paper/1905.10812/) (2019) - [Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics](https://mlsanity.com/paper/2202.10723/) (2022) - [Fast Unbalanced Optimal Transport on a Tree](https://mlsanity.com/paper/2006.02703/) (2020) - [Unnormalized Optimal Transport](https://mlsanity.com/paper/1902.03367/) (2019) - [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021) ## Built on by (most cited first, 10 of 10) - [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) - [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) - [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) - [An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph](https://mlsanity.com/paper/2502.00739/) (2025) ## Abstract (arXiv) Optimal transport (OT) is a popular and powerful tool for comparing probability measures. However, OT suffers a few drawbacks: (i) input measures required to have the same mass, (ii) a high computational complexity, and (iii) indefiniteness which limits its applications on kernel-dependent algorithmic approaches. To tackle issues (ii)--(iii), Le et al. (2022) recently proposed Sobolev transport for measures on a graph having the same total mass by leveraging the graph structure over supports. In this work, we consider measures that may have different total mass and are supported on a graph metric space. To alleviate the disadvantages (i)--(iii) of OT, we propose a novel and scalable approach to extend Sobolev transport for this unbalanced setting where measures may have different total mass. We show that the proposed unbalanced Sobolev transport (UST) admits a closed-form formula for fast computation, and it is also negative definite. Additionally, we derive geometric structures for the UST and establish relations between our UST and other transport distances. We further exploit the negative definiteness to design positive definite kernels and evaluate them on various simulations to illustrate their fast computation and comparable performances against other transport baselines for unbalanced measures on a graph.