Orlicz-Sobolev with Musielak: An Efficient Regularization Approach for Graph-based IPM

Tam Le; Truyen Nguyen; Hideitsu Hino; Kenji Fukumizu

cs.LGOct 29, 2025

Orlicz-Sobolev with Musielak: An Efficient Regularization Approach for Graph-based IPM

Authors: Tam Le, Truyen Nguyen, Hideitsu Hino, Kenji Fukumizu

Organizations: University of Akron

Abstract

We study the Sobolev IPM problem for probability measures supported on a graph metric space, where critic function is constrained to lie within the unit ball defined by Sobolev norm. Sobolev IPM is intrinsically coupled with $L^p$ geometric structure within its definition, limiting its ability to incorporate other prior geometry beyond the $L^p$ paradigm. Conversely, the classic optimal transport is flexible, easy to adapt to various geometric structures by simply changing its ground cost. An important example is Orlicz-Wasserstein (OW) which utilizes Orlicz geometric structure to generalize the $L^p$ within the standard $p$ -order Wasserstein, and remarkably play a vital role to advance machine learning methodologies. Inspired by recent advantages of OW, in this work, we leverage a specific class of convex functions for Orlicz geometry to mitigate such limitation for Sobolev IPM, and propose the generalized Sobolev IPM (GSI). Our GSI approach encompasses Sobolev IPM as a special case while accommodating diverse geometric priors beyond $L^p$ . It however brings up significant computational hurdles that compound those already notoriously inherent in Sobolev IPM. To address these challenges, we theoretically establish a novel connection between Orlicz-Sobolev norm and Musielak norm which facilitates a novel efficient regularization for GSI. By further exploiting the underlying graph structure, we show that the regularized GSI reduces to a simple univariate optimization problem, achieving notably computational efficiency, enabling its usage in practical applications. We empirically illustrate that the regularized GSI is several-order faster than the popular OW in computation, and its performances compare favorably to other transport baselines for comparing graph-based measures in document classification and topological data analysis.

Figures & tables

Figure 1: Time consumption on

{\mathbb{G}}_{\text{Log}}

Figure 2: SVM results and time consumption for kernel matrices with graph

{\mathbb{G}}_{\text{Log}}

. For each dataset, the numbers in the parenthesis are the number of classes; the number of documents; and the maximum number of unique words for each document respectively.

Figure 3: SVM results and time consumption for kernel matrices with graph

{\mathbb{G}}_{\text{Log}}

. For each dataset, the numbers in the parenthesis are respectively the number of PD; and the maximum number of points in PD.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Datasets	The number of pairs
TWITTER	4394432
RECIPE	8687560
CLASSIC	22890777
AMAZON	29117200
Orbit	11373250
MPEG7	18130

Appendix

Table 1: The number of pairs of probability measures on datasets for kernelized SVM.

Figure 4: Time consumption for GSI-M and OW on

{\mathbb{G}}_{\text{Sqrt}}

with 1K nodes and about 32K edges.

Figure 5: Time consumption for GSI-M, GST and OW on

{\mathbb{G}}_{\text{Log}}

with 1K nodes and about 7K edges.

Figure 6: Time consumption for GSI-M, GST and OW on

{\mathbb{G}}_{\text{Sqrt}}

with 1K nodes and about 32K edges.

Figure 7: SVM results and time consumption for kernel matrices with graph

{\mathbb{G}}_{\text{Sqrt}}

Figure 8: SVM results and time consumption for kernel matrices with graph

{\mathbb{G}}_{\text{Sqrt}}

	$\Phi_{0}$	$\Phi_{1}$	$\Phi_{2}$	$\Phi_{3}$
${\mathbb{G}}_{\text{Log}}$ (10K, 100K)	$70.55\pm 0.41$	$72.68\pm 0.58$	$71.85\pm 0.61$	$71.78\pm 0.61$
${\mathbb{G}}_{\text{Sqrt}}$ (10K, 1M)	$70.78\pm 0.47$	$72.45\pm 0.46$	$72.15\pm 0.46$	$71.86\pm 0.50$
${\mathbb{G}}_{\text{Log}}$ (1K, 7K)	$70.84\pm 0.38$	$72.52\pm 0.36$	$72.35\pm 0.34$	$72.03\pm 0.40$
${\mathbb{G}}_{\text{Sqrt}}$ (1K, 32K)	$70.99\pm 0.50$	$72.25\pm 0.42$	$72.57\pm 0.48$	$72.05\pm 0.44$
${\mathbb{G}}_{\text{Log}}$ (100, 500)	$70.05\pm 0.33$	$71.92\pm 0.44$	$71.36\pm 0.42$	$71.22\pm 0.26$
${\mathbb{G}}_{\text{Sqrt}}$ (100, 1K)	$69.81\pm 0.45$	$71.71\pm 0.30$	$71.29\pm 0.43$	$70.96\pm 0.43$

Appendix

Table 2: Ablation study on different graphs and different

N

-functions for document classification on TWITTER dataset.

	$\Phi_{0}$	$\Phi_{1}$	$\Phi_{2}$	$\Phi_{3}$
${\mathbb{G}}_{\text{Log}}$ (1K, 7K)	$61.50\pm 5.41$	$75.00\pm 4.16$	$78.33\pm 5.49$	$72.67\pm 4.66$
${\mathbb{G}}_{\text{Sqrt}}$ (1K, 32K)	$65.17\pm 4.54$	$81.67\pm 6.25$	$81.67\pm 4.78$	$79.33\pm 6.58$
${\mathbb{G}}_{\text{Log}}$ (100, 500)	$68.17\pm 5.00$	$76.67\pm 4.29$	$75.67\pm 5.44$	$74.17\pm 5.24$
${\mathbb{G}}_{\text{Sqrt}}$ (100, 1K)	$72.17\pm 5.67$	$78.33\pm 6.15$	$77.67\pm 6.35$	$76.33\pm 5.33$

Appendix

Table 3: Ablation study on different graphs and different

N

-functions for TDA on MPEG7 dataset.

	$\Phi_{1}$	$\Phi_{2}$
${\mathbb{G}}_{\text{Log}}$	$72.42\pm 0.41$	$71.53\pm 0.44$
${\mathbb{G}}_{\text{Sqrt}}$	$72.31\pm 0.28$	$72.04\pm 0.25$

Appendix

Table 4: Ablation study on different root nodes for document classification on TWITTER dataset.

	$\Phi_{1}$	$\Phi_{2}$
${\mathbb{G}}_{\text{Log}}$	$74.50\pm 1.39$	$77.23\pm 2.02$
${\mathbb{G}}_{\text{Sqrt}}$	$79.92\pm 2.65$	$80.03\pm 2.61$

Appendix

Table 5: Ablation study on different root nodes for TDA on MPEG7 dataset.

	$\Phi_{1}$	$\Phi_{2}$
No perturbation	$72.68\pm 0.58$	$71.85\pm 0.61$
With perturbation	$72.14\pm 0.46$	$71.42\pm 0.39$

Appendix

Table 6: Ablation study on graph

{\mathbb{G}}_{\text{Log}}

with a minor perturbation of its edge weights for document classification on TWITTER dataset.

	$\Phi_{1}$	$\Phi_{2}$
No perturbation	$72.45\pm 0.46$	$72.15\pm 0.46$
With perturbation	$71.95\pm 0.44$	$71.87\pm 0.48$

Appendix

Table 7: Ablation study on graph

{\mathbb{G}}_{\text{Sqrt}}

with a minor perturbation of its edge weights for document classification on TWITTER dataset.

	$\Phi_{1}$	$\Phi_{2}$
No perturbation	$75.00\pm 4.16$	$78.33\pm 5.49$
With perturbation	$73.33\pm 4.67$	$76.17\pm 3.93$

Appendix

Table 8: Ablation study on graph

{\mathbb{G}}_{\text{Log}}

with a minor perturbation of its edge weights for TDA on MPEG7 dataset.

	$\Phi_{1}$	$\Phi_{2}$
No perturbation	$81.67\pm 6.25$	$81.67\pm 4.78$
With perturbation	$81.33\pm 6.31$	$81.17\pm 6.06$

Appendix

Table 9: Ablation study on graph

{\mathbb{G}}_{\text{Sqrt}}

with a minor perturbation of its edge weights for TDA on MPEG7 dataset.

	$\Phi_{1}$	$\Phi_{2}$
${\mathbb{G}}_{\text{Log}}$	$0.019\pm 0.011$	$0.026\pm 0.015$
${\mathbb{G}}_{\text{Sqrt}}$	$0.004\pm 0.002$	$0.005\pm 0.002$

Appendix

Table 10: The empirical gap between GSI-M and GST.

	$\Phi_{1}$	$\Phi_{2}$
${\mathbb{G}}_{\text{Log}}$	$293.06\pm 19.43$	$403.47\pm 26.75$
${\mathbb{G}}_{\text{Sqrt}}$	$165.45\pm 28.88$	$227.79\pm 39.75$

Appendix

Table 11: The empirical gap between GSI-M and OW.

Figure 9: A geodetic graph with $10$ nodes $\left\{x_{1},x_{2},\dotsc,x_{10}\right\}$ and $15$ edges $\left\{e_{1},e_{2},\dotsc,e_{15}\right\}$ , and each edge length equals to $1$ , i.e., $w_{e_{j}}=1,\forall j$ . For any $x_{i},x_{j}$ , there is a unique shortest path between them, with a length $2$ . Therefore, it satisfies the uniqueness property of the shortest paths. Let $x_{1}$ be the unique-path root node (i.e., $z_{0}=x_{1}$ ), and subgraph $\widetilde{{\mathbb{G}}}$ containing $3$ nodes $\left\{x_{2},x_{3},x_{7}\right\}$ and $2$ edges $\left\{e_{2},e_{7}\right\}$ , then we have $\Lambda(x_{2})=\gamma(e_{1})=\widetilde{{\mathbb{G}}}$ .

Integral Probability Metrics

Integral probability metrics compare probability distributions by the largest expectation gap over a chosen class of test functions.

See all 13 papers

Sep 14, 2026

Graph Matching Relaxations and Amortization for Supervised Graph Prediction

End-to-end Supervised Graph Prediction (SGP) requires a permutation-invariant loss to compare predicted and target graphs with arbitrary node orderings. Such losses typically involve a costly graph-matching problem. We first study three Optimal Transport relaxations of this problem and show, theoretically and empirically, that the Gromov-Wasserstein (GW) objective is the most suitable for SGP. Then, to avoid solving the resulting inner optimization for every training example, we propose to amortize the graph matching (node alignment) problem. For each training sample, the loss function leverages a transport plan provided by a parametric matcher based on the differentiable Sinkhorn algorithm applied on empirical node distributions. The graph prediction module and the matcher are jointly learned. We showcase the efficiency of this approach on toy and real world SGP problems of increasing complexity including a novel Mass-spectra to Scaffold task that we introduce.

Federico Méndez, Paul Krzakala, Gabriel Melo +3

LTCI, Télécom Paris · Institut Polytechnique de Paris · CMAP, École Polytechnique

Learning to Optimize Graph Matching Optimal Transport Wasserstein Distance

Ask PDF

Sep 26, 2026

Sliced Orlicz-Wasserstein

We propose sliced Orlicz-Wasserstein (SOW) distance which is a generalization of sliced Wasserstein (SW) distance. SOW replaces the

L^p

norm in SW with a Luxemburg norm cost induced by an Orlicz function

φ

. First, we prove that SOW distance is a metric on the space of measures with finite Orlicz norm, and show that it recovers the SW distance when the Orlicz function is

φ(x)=x^p

. Next, we derive the topological properties of the SOW distance. In particular, we show that convergence under SOW implies weak convergence, and the converse is true under the compact support condition. We then present the theoretical results for estimating the SOW distance. We derive sample complexity for both the distance itself and the powered functional of the distance, and prove their minimax optimality. In addition, we discuss the computational algorithm for approximating the SOW distance by Monte-Carlo estimation and bisection search, as well as the associated approximation error and computational complexity analysis. Our experimental results reveal the superior computational efficiency of SOW compared with Orlicz-Wasserstein (OW) distance. Also, in the experiments, we demonstrate the favorable flexibility of SOW distance over SW in detecting differences between distributions by comparing their performance in two-sample tests and evaluating generative models on image datasets.

Binh Thuan Tran, Khai Nguyen

LAMA, LIGM, Université Gustave Eiffel · Department of Statistics and Data Science, Texas A&M University

Optimal Transport Sliced Wasserstein Distance

Ask PDF

Mar 27, 2026

Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs

The optimal transportation problem defines a geometry of probability measures which leads to a definition for weighted averages (barycenters) of measures, finding application in the machine learning and computer vision communities as a signal processing tool. Here, we implement a barycentric coding model for measures which are supported on a graph, a context in which the classical optimal transport geometry becomes degenerate, by leveraging a Riemannian structure on the simplex induced by a dynamic formulation of the optimal transport problem. We approximate the exponential mapping associated to the Riemannian structure, as well as its inverse, by utilizing past approaches which compute action minimizing curves in order to numerically approximate transport distances for measures supported on discrete spaces. Intrinsic gradient descent is then used to synthesize barycenters, wherein gradients of a variance functional are computed by approximating geodesic curves between the current iterate and the reference measures; iterates are then pushed forward via a discretization of the continuity equation. Analysis of measures with respect to given dictionary of references is performed by solving a quadratic program formed by computing geodesics between target and reference measures. We compare our novel approach to one based on entropic regularization of the static formulation of the optimal transport problem where the graph structure is encoded via graph distance functions, we present numerical experiments validating our approach, and we conclude that intrinsic gradient descent on the probability simplex provides a coherent framework for the synthesis and analysis of measures supported on graphs.

David Gentile, James M. Murphy

Tufts University, Dept. of Mathematics, Medford, MA, USA

Wasserstein Barycenters Optimal Transport

Ask PDF

Abstract

Integral Probability Metrics

Explore similar work

Graph Matching Relaxations and Amortization for Supervised Graph Prediction

Sliced Orlicz-Wasserstein

Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs