An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph

• URL: http://arxiv.org/abs/2502.00739v2
• Date: Fri, 24 Oct 2025 02:52:05 GMT
• Title: An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph
• Authors: Tam Le, Truyen Nguyen, Hideitsu Hino, Kenji Fukumizu,
• Abstract summary: We investigate optimal transport (OT) for measures on graph metric spaces with different total masses.<n>To mitigate the limitations of traditional $Lp$ geometry, Orlicz-Wasserstein (OW) and generalized Sobolev transport ( GST) employ Orlicz geometric structure.<n>We establish theoretical background to solve Orlicz-EPT using a binary search algorithmic approach.
• Score: 26.692344867327332
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We investigate optimal transport (OT) for measures on graph metric spaces with different total masses. To mitigate the limitations of traditional $L^p$ geometry, Orlicz-Wasserstein (OW) and generalized Sobolev transport (GST) employ Orlicz geometric structure, leveraging convex functions to capture nuanced geometric relationships and remarkably contribute to advance certain machine learning approaches. However, both OW and GST are restricted to measures with equal total mass, limiting their applicability to real-world scenarios where mass variation is common, and input measures may have noisy supports, or outliers. To address unbalanced measures, OW can either incorporate mass constraints or marginal discrepancy penalization, but this leads to a more complex two-level optimization problem. Additionally, GST provides a scalable yet rigid framework, which poses significant challenges to extend GST to accommodate nonnegative measures. To tackle these challenges, in this work we revisit the entropy partial transport (EPT) problem. By exploiting Caffarelli & McCann (2010)'s insights, we develop a novel variant of EPT endowed with Orlicz geometric structure, called Orlicz-EPT. We establish theoretical background to solve Orlicz-EPT using a binary search algorithmic approach. Especially, by leveraging the dual EPT and the underlying graph structure, we formulate a novel regularization approach that leads to the proposed Orlicz-Sobolev transport (OST). Notably, we demonstrate that OST can be efficiently computed by simply solving a univariate optimization problem, in stark contrast to the intensive computation needed for Orlicz-EPT. Building on this, we derive geometric structures for OST and draw its connections to other transport distances. We empirically illustrate that OST is several-order faster than Orlicz-EPT.

Related papers

• Variational Entropic Optimal Transport [67.76725267984578]
  We propose Variational Entropic Optimal Transport (VarEOT) for domain translation problems.<n>VarEOT is based on an exact variational reformulation of the log-partition $log mathbbE[exp(cdot)$ as a tractable generalization over an auxiliary positive normalizer.<n> Experiments on synthetic data and unpaired image-to-image translation demonstrate competitive or improved translation quality.
  arXiv  Detail & Related papers  (2026-02-02T15:48:44Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  This paper revisits the weighted strategy for non-stationary parametric bandits.<n>We propose a simpler weight-based algorithm that is as efficient as window/restart-based algorithms.<n>Our framework can be used to improve regret bounds of other parametric bandits.
  arXiv  Detail & Related papers  (2026-01-03T04:50:21Z)
• Generalized Sobolev IPM for Graph-Based Measures [26.692344867327332]
  We study the Sobolev IPM problem for measures supported on a graph metric space, where critic function is constrained to lie within the unit ball defined by Sobolev norm.<n>We propose to generalize Sobolev IPM through the lens of emphOrlicz geometric structure, which employs convex functions to capture nuanced geometric relationships.<n>This generalization encompasses classical Sobolev IPM as a special case while accommodating diverse geometric priors beyond traditional $Lp$ structure.
  arXiv  Detail & Related papers  (2025-10-29T14:59:26Z)
• Conic Formulations of Transport Metrics for Unbalanced Measure Networks and Hypernetworks [3.7687375904925484]
  This paper is concerned with the Conic Gromov-Wasserstein (CGW) distance introduced by S'ejourn'e, Vialard, and Peyr'e.<n>We provide a novel formulation in terms of semi-couplings, and extend the framework beyond the metric measure space setting.
  arXiv  Detail & Related papers  (2025-08-14T17:55:55Z)
• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning.<n>We introduce a novel approach to disentangled representation learning based on quadratic optimal transport.<n>We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs [48.84819106277247]
  We claim that effective resistance and optimal transport on graphs should be understood as one and the same, up to a choice of $p$.<n>We show explicit connections to optimal stopping times and random walks on graphs, graph Sobolev spaces, and a Benamou-Brenier type formula for $2$-Beckmann distance.<n>We propose further study of the usage of these metrics where Wasserstein distance may produce computational bottlenecks.
  arXiv  Detail & Related papers  (2024-04-23T17:50:52Z)
• Generalized Sobolev Transport for Probability Measures on a Graph [26.64899319099165]
  We study the optimal transport (OT) problem for measures supported on a graph metric space. We leverage a specific class of convex functions for Orlicz structure to propose the generalized Sobolev transport ( GST) We empirically illustrate that GST is several-order faster than the Orlicz-Wasserstein (OW)
  arXiv  Detail & Related papers  (2024-02-07T01:49:03Z)
• Tempered Calculus for ML: Application to Hyperbolic Model Embedding [70.61101116794549]
  Most mathematical distortions used in ML are fundamentally integral in nature. In this paper, we unveil a grounded theory and tools which can help improve these distortions to better cope with ML requirements. We show how to apply it to a problem that has recently gained traction in ML: hyperbolic embeddings with a "cheap" and accurate encoding along the hyperbolic vsean scale.
  arXiv  Detail & Related papers  (2024-02-06T17:21:06Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers. We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states. By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
  arXiv  Detail & Related papers  (2024-01-31T15:50:50Z)
• Scalable Unbalanced Sobolev Transport for Measures on a Graph [23.99177001129992]
  Optimal transport (OT) is a powerful tool for comparing probability measures. OT suffers a few drawbacks: (i) input measures required to have the same mass, (ii) a high computational complexity, and (iii) indefiniteness. 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. We show that the proposed unbalanced Sobolev transport admits a closed-form formula for fast computation, and it is also negative definite.
  arXiv  Detail & Related papers  (2023-02-24T07:35:38Z)
• Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
  We introduce a new family of SW distances, named Markovian sliced Wasserstein (MSW) distance, which imposes a first-order Markov structure on projecting directions. We compare distances with previous SW variants in various applications such as flows, color transfer, and deep generative modeling to demonstrate the favorable performance of MSW.
  arXiv  Detail & Related papers  (2023-01-10T01:58:15Z)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  Low-rank optimal transport (LOT) approach advocated in citescetbon 2021lowrank LOT is seen as a legitimate contender to entropic regularization when compared on properties of interest. We target each of these areas in this paper in order to cement the impact of low-rank approaches in computational OT.
  arXiv  Detail & Related papers  (2022-05-24T20:51:37Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity [11.280177531118206]
  We study the multi-marginal partial optimal transport (POT) problem between $m$ discrete (unbalanced) measures with at most $n$ supports. We first prove that we can obtain two equivalence forms of the multimarginal POT problem in terms of the multimarginal optimal transport problem via novel extensions of cost tensor. We demonstrate that the ApproxMPOT algorithm can approximate the optimal value of multimarginal POT problem with a computational complexity upper bound of the order $tildemathcalO(m3(n+1)m/ var
  arXiv  Detail & Related papers  (2021-08-18T06:46:59Z)
• Entropy Partial Transport with Tree Metrics: Theory and Practice [5.025654873456756]
  We consider an textitentropy partial transport (EPT) problem for nonnegative measures on a tree having different masses. We propose a novel regularization for EPT which admits fast computation and negative definiteness. We empirically demonstrate that our regularization also provides effective approximations.
  arXiv  Detail & Related papers  (2021-01-24T17:04:24Z)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  Projection robust (PR) OT seeks to maximize the OT cost between two measures by choosing a $k$-dimensional subspace onto which they can be projected. Our first contribution is to establish several fundamental statistical properties of PR Wasserstein distances. Next, we propose the integral PR Wasserstein (IPRW) distance as an alternative to the PRW distance, by averaging rather than optimizing on subspaces.
  arXiv  Detail & Related papers  (2020-06-22T14:35:33Z)
• Targeted free energy estimation via learned mappings [66.20146549150475]
  Free energy perturbation (FEP) was proposed by Zwanzig more than six decades ago as a method to estimate free energy differences. FEP suffers from a severe limitation: the requirement of sufficient overlap between distributions. One strategy to mitigate this problem, called Targeted Free Energy Perturbation, uses a high-dimensional mapping in configuration space to increase overlap.
  arXiv  Detail & Related papers  (2020-02-12T11:10:00Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  We introduce the Anchor Energy (AE) and Anchor Wasserstein (AW) distances, which are respectively the energy and Wasserstein distances instantiated on such representations. Our main contribution is to propose a sweep line algorithm to compute AE emphexactly in log-quadratic time, where a naive implementation would be cubic. We show that AE and AW perform well in various experimental settings at a fraction of the computational cost of popular GW approximations.
  arXiv  Detail & Related papers  (2020-02-05T03:09:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.