# Generalized Sobolev IPM for Graph-Based Measures

arXiv: https://arxiv.org/abs/2510.25591 · HTML: https://mlsanity.com/paper/2510.25591/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 29 Oct 2025.

## Builds on (most cited first, 28 of 28)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Persistence Images: A Stable Vector Representation of Persistent Homology](https://mlsanity.com/paper/1507.06217/) (2015)
- [Pointwise Convolutional Neural Networks](https://mlsanity.com/paper/1712.05245/) (2017)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Statistical and Topological Properties of Sliced Probability Divergences](https://mlsanity.com/paper/2003.05783/) (2020)
- [How Well Generative Adversarial Networks Learn Distributions](https://mlsanity.com/paper/1811.03179/) (2018)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [Tree-Sliced Variants of Wasserstein Distances](https://mlsanity.com/paper/1902.00342/) (2019)
- [Hierarchical Optimal Transport for Document Representation](https://mlsanity.com/paper/1906.10827/) (2019)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Sobolev GAN](https://mlsanity.com/paper/1711.04894/) (2017)
- [Nonparametric Density Estimation under Adversarial Losses](https://mlsanity.com/paper/1805.08836/) (2018)
- [Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses](https://mlsanity.com/paper/1902.03511/) (2019)
- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (2022)
- [Subspace Embedding and Linear Regression with Orlicz Norm](https://mlsanity.com/paper/1806.06430/) (2018)
- [Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics](https://mlsanity.com/paper/2202.10723/) (2022)
- [COPT: Coordinated Optimal Transport for Graph Sketching](https://mlsanity.com/paper/2003.03892/) (2020)
- [How Well Can Generative Adversarial Networks Learn Densities: A Nonparametric View](https://mlsanity.com/paper/1712.08244/) (2017)
- [Estimating Certain Integral Probability Metric (IPM) is as Hard as Estimating under the IPM](https://mlsanity.com/paper/1911.00730/) (2019)
- [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024)
- [Efficient Symmetric Norm Regression via Linear Sketching](https://mlsanity.com/paper/1910.01788/) (2019)
- [Fast Distance Oracles for Any Symmetric Norm](https://mlsanity.com/paper/2205.14816/) (2022)
- [Orlicz space regularization of continuous optimal transport problems](https://mlsanity.com/paper/2004.11574/) (2020)
- [Fused Partial Gromov-Wasserstein for Structured Objects](https://mlsanity.com/paper/2502.09934/) (2025)
- [Scalable Sobolev IPM for Probability Measures on a Graph](https://mlsanity.com/paper/2502.00737/) (2025)

## Abstract (arXiv)

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. While Le et al. (2025) achieved scalable computation by relating Sobolev norm to weighted Lp-norm, the resulting framework remains intrinsically bound to Lp geometric structure, limiting its ability to incorporate alternative structural priors beyond the Lp geometry paradigm. To overcome this limitation, we propose to generalize Sobolev IPM through the lens of Orlicz geometric structure, which employs convex functions to capture nuanced geometric relationships, building upon recent advances in optimal transport theory -- particularly Orlicz-Wasserstein (OW) and generalized Sobolev transport -- that have proven instrumental in advancing machine learning methodologies. This generalization encompasses classical Sobolev IPM as a special case while accommodating diverse geometric priors beyond traditional Lp structure. It however brings up significant computational hurdles that compound those already inherent in Sobolev IPM. To address these challenges, we establish a novel theoretical connection between Orlicz-Sobolev norm and Musielak norm which facilitates a novel regularization for the generalized Sobolev IPM (GSI). By further exploiting the underlying graph structure, we show that GSI with Musielak regularization (GSI-M) reduces to a simple univariate optimization problem, achieving remarkably computational efficiency. Empirically, GSI-M is several-order faster than the popular OW in computation, and demonstrates its practical advantages in comparing probability measures on a given graph for document classification and several tasks in topological data analysis.