Research map / Graph learning / Graph algorithms and clustering
An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced 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.
Extends Orlicz-Wasserstein and generalized Sobolev transport to unbalanced measures on graphs via a calibrated EPT-to-OT reformulation (Orlicz-EPT) and a dual-based graph regularization (OST) that reduces to a univariate optimization.
Problem
Optimal transport between unbalanced (different total mass) measures on graph metric spaces with Orlicz geometry is computationally expensive (two-level optimization for OW/POT/UOT) and GST is restricted to equal-mass measures.
Approach
Reformulate entropy partial transport as a standard complete OT with a nonnegative calibrated ground cost (Orlicz-EPT), then use the dual EPT with graph-structure regularization of critic functions to obtain Orlicz-Sobolev transport (OST), computable via a univariate infimum over k using edge-wise mass differences.
Key results
- OST is at least 250x, 13800x and 11200x faster than Orlicz-EPT for Phi0, Phi1, Phi2 respectively in the time comparison on AMAZON.
- Orlicz-EPT with N-functions takes at least 2.6 days while OST takes under 21 seconds.
- OST performance is comparable to UOT on document classification, with OST-Phi1 and OST-Phi2 improving over OST-Phi0 on document classification and TDA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OST instead of Orlicz-EPT with Φ0 | Unbalanced measures on Amazon with G_Sqrt · Amazon, G_Sqrt computation | speedup: at least 250× | Helped |
| Use OST instead of Orlicz-EPT with Φ1 | Unbalanced measures on Amazon with G_Sqrt · Amazon, G_Sqrt computation | speedup: at least 13800× | Helped |
| Use OST instead of Orlicz-EPT with Φ2 | Unbalanced measures on Amazon with G_Sqrt · Amazon, G_Sqrt computation | speedup: at least 11200× | Helped |
| Use Φ1 or Φ2 instead of Φ0 in OST (ablation) | OST for document classification · Document classification | classification performance | Helped |
| Use Φ1 or Φ2 instead of Φ0 in OST (ablation) | OST for document classification · Document classification | computation time | Hurt |
| Use OST instead of UOT | Unbalanced-measure document classification · Document classification | classification performance | No clear effect |
| Use OST instead of UOT | Unbalanced-measure document classification · Document classification | computation time | Helped |
| Use OST instead of d0-Tree or regEPT-Tree | Unbalanced-measure document classification · Document classification | classification performance | Helped |
| Use Φ1 or Φ2 instead of Φ0 in OST (ablation) | OST for topological data analysis · TDA | classification performance | Helped |
Limitations
- Orlicz-EPT remains computationally prohibitive due to its two-level binary search over entropic OT
- Experiments show only initial evidence of advantages on document classification and TDA
- Requires a root node choice and measures supported on graph nodes for the discrete closed form
Experimental setup
Datasets: TWITTER RECIPE CLASSIC AMAZON Orbit MPEG7
Benchmarks: TWITTER RECIPE CLASSIC AMAZON Orbit MPEG7
Metrics: SVM classification accuracy time consumption
Baselines: OST-Phi0 unbalanced optimal transport d0-Tree regEPT-Tree Orlicz-EPT
Builds on: generalized Sobolev transport entropy partial transport Orlicz-Wasserstein unbalanced Sobolev transport
Closest papers by meaning
- Generalized Sobolev Transport for Probability Measures on a Graph (ICML 2024 · similarity 0.94)
- Learning Ultrametric Trees for Optimal Transport Regression (AAAI 2024 · similarity 0.87)
- Submodular framework for structured-sparse optimal transport (ICML 2024 · similarity 0.86)
- Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation (NeurIPS 2026 · similarity 0.86)
- Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · similarity 0.86)
- Joint Metric Space Embedding by Unbalanced Optimal Transport with Gromov–Wasserstein Marginal Penalization (ICML 2025 · similarity 0.86)
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.