Research map / Learning theory and algorithms / Optimal transport
Generalized Sobolev Transport for Probability Measures on a Graph
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes generalized Sobolev transport (GST), a metric on graph-supported probability measures built from N-functions (Orlicz geometry) that generalizes Sobolev transport and reduces to a univariate optimization, and is several orders faster than Orlicz-Wasserstein.
Problem
Sobolev transport (ST) on graphs is tied to the L^p geometry and hard to adapt to other geometries, while Orlicz-Wasserstein (OW) is computationally expensive due to a two-level optimization.
Approach
Replace the L^p Lipschitz/Sobolev constraint in ST with an Orlicz-Sobolev constraint defined by an N-function and its complementary function; the resulting distance has a closed form as a univariate infimum over k, which recovers ST for Phi(t)=c t^p and OW on trees for Phi(t)=t.
Key results
- GST is about 100x, 5000x and 3000x faster than OW for Phi_0, Phi_1, Phi_2 respectively on AMAZON pairs with M=10^3 nodes.
- For Phi_1 and Phi_2, GST takes under 25 seconds for 10^4 pairs while OW takes at least 17 hours.
- GST with Phi_1 and Phi_2 improves document classification accuracy over GST-Phi_0 and performs favorably against OW in SVM experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GST-Φ0 instead of OW-Φ0 | Graph-based transport computation · AMAZON (10^4 sampled pairs; G_Log and G_Sqrt, M=10^3) | speedup: 100× faster | Helped |
| Use GST-Φ1 instead of OW-Φ1 | Graph-based transport computation · AMAZON (10^4 sampled pairs; G_Log and G_Sqrt, M=10^3) | speedup: 5000× faster | Helped |
| Use GST-Φ2 instead of OW-Φ2 | Graph-based transport computation · AMAZON (10^4 sampled pairs; G_Log and G_Sqrt, M=10^3) | speedup: 3000× faster | Helped |
| Use GST-Φ1 instead of GST-Φ0 (ablation) | GST document classification · TWITTER, RECIPE, CLASSIC, AMAZON | classification performance | Helped |
| Use GST-Φ2 instead of GST-Φ0 (ablation) | GST document classification · TWITTER, RECIPE, CLASSIC, AMAZON | classification performance | Helped |
| Use GST instead of OW | Graph-based distance for document classification · TWITTER, RECIPE, CLASSIC, AMAZON | classification performance | Helped |
| Use OW-Φ0-Tree instead of OW-Φ0 | Document classification · TWITTER, RECIPE, CLASSIC, AMAZON | classification performance | Mixed |
| Use GST instead of OW | Graph-based distance for topological data analysis · Orbit, MPEG7 | classification performance | Helped |
| Use OW-Φ0-Tree instead of OW-Φ0 | Topological data analysis · Orbit, MPEG7 | classification performance | Helped |
Limitations
- Only balanced measures (equal total mass) are considered; unbalanced extension is future work
- Classification gains are described as preliminary evidence
- Computation of general N-functions still requires a numerical univariate solver
Experimental setup
Datasets: TWITTER RECIPE CLASSIC AMAZON Orbit MPEG7
Benchmarks: TWITTER RECIPE CLASSIC AMAZON Orbit MPEG7
Metrics: SVM classification accuracy computation time
Baselines: Orlicz-Wasserstein (OW) Sobolev transport (ST) OW on random tree
Builds on: Sobolev transport Orlicz-Wasserstein Kantorovich-Rubinstein duality
Closest papers by meaning
- An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph (NeurIPS 2025 · similarity 0.94)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.88)
- Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · similarity 0.87)
- A Provably Convergent and Practical Algorithm for Gromov–Wasserstein Optimal Transport (NeurIPS 2026 · similarity 0.87)
- Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation (NeurIPS 2026 · similarity 0.87)
- Learning Ultrametric Trees for Optimal Transport Regression (AAAI 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.