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

Graph Matching Relaxations and Amortization for Supervised Graph Prediction
Sep 14, 2026Federico Méndez, Paul Krzakala, Gabriel Melo +3Learning to Optimize Graph Matching
LTCI, Télécom Paris · Institut Polytechnique de Paris · CMAP, École Polytechnique
Sliced Orlicz-Wasserstein
Sep 26, 2026Binh Thuan Tran, Khai NguyenOptimal Transport Sliced Wasserstein Distance
LAMA, LIGM, Université Gustave Eiffel · Department of Statistics and Data Science, Texas A&M University
Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs
Mar 27, 2026David Gentile, James M. MurphyWasserstein Barycenters Optimal Transport
Tufts University, Dept. of Mathematics, Medford, MA, USA

Sep 14, 2026J/K move · Enter open · S save

Graph Matching Relaxations and Amortization for Supervised Graph Prediction

Federico Méndez, Paul Krzakala, Gabriel Melo, Charlotte Laclau+2

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

Learning to Optimize Graph Matching Optimal Transport Wasserstein Distance

Open paper AskPDF arXiv

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.

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