# Generalized Sobolev Transport for Probability Measures on a Graph arXiv: https://arxiv.org/abs/2402.04516 ยท HTML: https://mlsanity.com/paper/2402.04516/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Builds on 48 of its 72 references that are in the map. - First posted on arXiv 7 Feb 2024. ## Builds on (most cited first, 30 of 48) - [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) - [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) - [TrajectoryNet: A Dynamic Optimal Transport Network for Modeling Cellular Dynamics](https://mlsanity.com/paper/2002.04461/) (2020) - [Neural Optimal Transport](https://mlsanity.com/paper/2201.12220/) (2022) - [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021) - [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) - [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019) - [The Schr"odinger Bridge between Gaussian Measures has a Closed Form](https://mlsanity.com/paper/2202.05722/) (2022) - [Tree-Sliced Variants of Wasserstein Distances](https://mlsanity.com/paper/1902.00342/) (2019) - [Outlier-Robust Optimal Transport](https://mlsanity.com/paper/2012.07363/) (2020) - [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023) - [Asymptotic Guarantees for Learning Generative Models with the Sliced-Wasserstein Distance](https://mlsanity.com/paper/1906.04516/) (2019) - [Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent](https://mlsanity.com/paper/2106.08502/) (2021) - [Spherical Sliced-Wasserstein](https://mlsanity.com/paper/2206.08780/) (2022) - [Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search](https://mlsanity.com/paper/2006.07593/) (2020) - [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021) - [Outlier-Robust Optimal Transport: Duality, Structure, and Statistical Analysis](https://mlsanity.com/paper/2111.01361/) (2021) - [Quasi-Monte Carlo for 3D Sliced Wasserstein](https://mlsanity.com/paper/2309.11713/) (2023) - [Subspace Embedding and Linear Regression with Orlicz Norm](https://mlsanity.com/paper/1806.06430/) (2018) - [Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics](https://mlsanity.com/paper/2202.10723/) (2022) - [COPT: Coordinated Optimal Transport for Graph Sketching](https://mlsanity.com/paper/2003.03892/) (2020) - [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022) - [Outlier-Robust Wasserstein DRO](https://mlsanity.com/paper/2311.05573/) (2023) ## Built on by (most cited first, 9 of 9) - [Tree-Sliced Wasserstein Distance: A Geometric Perspective](https://mlsanity.com/paper/2406.13725/) (2024) - [Distance-Based Tree-Sliced Wasserstein Distance](https://mlsanity.com/paper/2503.11050/) (2025) - [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) - [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) ## Abstract (arXiv) We study the optimal transport (OT) problem for measures supported on a graph metric space. Recently, Le et al. (2022) leverage the graph structure and propose a variant of OT, namely Sobolev transport (ST), which yields a closed-form expression for a fast computation. However, ST is essentially coupled with the Lp geometric structure within its definition which makes it nontrivial to utilize ST for other prior structures. In contrast, the classic OT has the flexibility to adapt to various geometric structures by modifying the underlying cost function. An important instance is the Orlicz-Wasserstein (OW) which moves beyond the Lp structure by leveraging the Orlicz geometric structure. Comparing to the usage of standard p-order Wasserstein, OW remarkably helps to advance certain machine learning approaches. Nevertheless, OW brings up a new challenge on its computation due to its two-level optimization formulation. In this work, we leverage a specific class of convex functions for Orlicz structure to propose the generalized Sobolev transport (GST). GST encompasses the ST as its special case, and can be utilized for prior structures beyond the Lp geometry. In connection with the OW, we show that one only needs to simply solve a univariate optimization problem to compute the GST, unlike the complex two-level optimization problem in OW. We empirically illustrate that GST is several-order faster than the OW. Moreover, we provide preliminary evidences on the advantages of GST for document classification and for several tasks in topological data analysis.