mlsanityData to 14 Oct 2026

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

arXiv 2202.10723 ↗First posted 22 Feb 2022cs.LG cs.AI stat.MLcited by 18

Not on the map. Why?

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.

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

29 of 45 references.

References · 29

  1. 2013Distributed Representations of Words and Phrases and their Compositionalitycited by 3,474
  2. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,316
  3. 2018Computational Optimal Transportcited by 780
  4. 2017Joint Distribution Optimal Transportation for Domain Adaptationcited by 282
  5. 2015Persistence Images: A Stable Vector Representation of Persistent Homologycited by 236
  6. 2018Optimal Transport for structured data with application on graphscited by 172
  7. 2019Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learningcited by 170
  8. 2021Unbalanced minibatch Optimal Transport; applications to Domain Adaptationcited by 125
  9. 2020Missing Data Imputation using Optimal Transportcited by 100
  10. 2019Statistical bounds for entropic optimal transport: sample complexity and the central limit theoremcited by 85
  11. 2021Low-Rank Sinkhorn Factorizationcited by 67
  12. 2019Tree-Sliced Variants of Wasserstein Distancescited by 54
17 more
  1. 2019Learning Generative Models across Incomparable Spacescited by 53
  2. 2021Point-set Distances for Learning Representations of 3D Point Cloudscited by 48
  3. 2020Outlier-Robust Optimal Transportcited by 45
  4. 2019Asymptotic Guarantees for Learning Generative Models with the Sliced-Wasserstein Distancecited by 43
  5. 2018Persistence Fisher Kernel: A Riemannian Manifold Kernel for Persistence Diagramscited by 33
  6. 2021Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descentcited by 32
  7. 2017Sobolev GANcited by 29
  8. 2020Optimal Transport Kernels for Sequential and Parallel Neural Architecture Searchcited by 29
  9. 2021Statistical Analysis of Wasserstein Distributionally Robust Estimatorscited by 27
  10. 2021Testing Group Fairness via Optimal Transport Projectionscited by 23
  11. 2017Kernel method for persistence diagrams via kernel embedding and weight factorcited by 20
  12. 2019Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transportcited by 19
  13. 2021Diffusion Earth Mover's Distance and Distribution Embeddingscited by 18
  14. 2018Dynamical Optimal Transport on Discrete Surfacescited by 17
  15. 2021Entropy Partial Transport with Tree Metrics: Theory and Practicecited by 13
  16. 2021Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and Morecited by 11
  17. 2021Adversarial Regression with Doubly Non-negative Weighting Matricescited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 6; 2024: 5; 2025: 6; 2026: 1.

18 papers.

Sort:

  1. 2023Scalable Unbalanced Sobolev Transport for Measures on a Graphcited by 10
  2. 2024Generalized Sobolev Transport for Probability Measures on a Graphcited by 9
  3. 2023Optimal Transport for Measures with Noisy Tree Metriccited by 7
  4. 2024Tree-Sliced Wasserstein Distance: A Geometric Perspectivecited by 7
  5. 2023Scalable Counterfactual Distribution Estimation in Multivariate Causal Modelscited by 6
  6. 2025Distance-Based Tree-Sliced Wasserstein Distancecited by 4
  7. 2023Few-Shot Object Detection via Synthetic Features with Optimal Transportcited by 3
  8. 2024Efficient approximation of Earth Mover's Distance Based on Nearest Neighbor Searchcited by 3
  9. 2025Tree-Sliced Wasserstein Distance with Nonlinear Projectioncited by 3
  10. 2024Resistance Distance and Linearized Optimal Transport on Graphscited by 2
  11. 2025Spherical Tree-Sliced Wasserstein Distancecited by 2
  12. 2024SAVA: Scalable Learning-Agnostic Data Valuationcited by 1
6 more
  1. 2025Scalable Sobolev IPM for Probability Measures on a Graphcited by 1
  2. 2023Graph Fourier MMD for Signals on Graphscited by 0
  3. 2023An Empirical Study of Self-supervised Learning with Wasserstein Distancecited by 0
  4. 2025An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graphcited by 0
  5. 2025Generalized Sobolev IPM for Graph-Based Measurescited by 0
  6. 2026Sobolev--Ricci Curvaturecited by 0