# Scalable Sobolev IPM for Probability Measures on a Graph

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 67 references that are in the map.
- First posted on arXiv 2 Feb 2025.

## Builds on (most cited first, 30 of 39)

- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [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)
- [PointConv: Deep Convolutional Networks on 3D Point Clouds](https://mlsanity.com/paper/1811.07246/) (2018)
- [Persistence Images: A Stable Vector Representation of Persistent Homology](https://mlsanity.com/paper/1507.06217/) (2015)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Pointwise Convolutional Neural Networks](https://mlsanity.com/paper/1712.05245/) (2017)
- [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)
- [Learning metrics for persistence-based summaries and applications for graph classification](https://mlsanity.com/paper/1904.12189/) (2019)
- [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)
- [Point-set Distances for Learning Representations of 3D Point Clouds](https://mlsanity.com/paper/2102.04014/) (2021)
- [Graph Kernels: A Survey](https://mlsanity.com/paper/1904.12218/) (2019)
- [Persistence Fisher Kernel: A Riemannian Manifold Kernel for Persistence Diagrams](https://mlsanity.com/paper/1802.03569/) (2018)
- [Sobolev GAN](https://mlsanity.com/paper/1711.04894/) (2017)
- [Nonparametric Density Estimation under Adversarial Losses](https://mlsanity.com/paper/1805.08836/) (2018)
- [Fisher GAN](https://mlsanity.com/paper/1705.09675/) (2017)
- [Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses](https://mlsanity.com/paper/1902.03511/) (2019)
- [Kernel method for persistence diagrams via kernel embedding and weight factor](https://mlsanity.com/paper/1706.03472/) (2017)
- [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)
- [Distributional Robustness with IPMs and links to Regularization and GANs](https://mlsanity.com/paper/2006.04349/) (2020)
- [Smooth p-Wasserstein Distance: Structure, Empirical Approximation, and Statistical Applications](https://mlsanity.com/paper/2101.04039/) (2021)
- [How Well Can Generative Adversarial Networks Learn Densities: A Nonparametric View](https://mlsanity.com/paper/1712.08244/) (2017)
- [Entropy Partial Transport with Tree Metrics: Theory and Practice](https://mlsanity.com/paper/2101.09756/) (2021)
- [Estimating Certain Integral Probability Metric (IPM) is as Hard as Estimating under the IPM](https://mlsanity.com/paper/1911.00730/) (2019)

## Built on by (most cited first, 1 of 1)

- [Generalized Sobolev IPM for Graph-Based Measures](https://mlsanity.com/paper/2510.25591/) (2025)

## Abstract (arXiv)

We investigate the Sobolev IPM problem for probability measures supported on a graph metric space. Sobolev IPM is an important instance of integral probability metrics (IPM), and is obtained by constraining a critic function within a unit ball defined by the Sobolev norm. In particular, it has been used to compare probability measures and is crucial for several theoretical works in machine learning. However, to our knowledge, there are no efficient algorithmic approaches to compute Sobolev IPM effectively, which hinders its practical applications. In this work, we establish a relation between Sobolev norm and weighted Lp-norm, and leverage it to propose a novel regularization for Sobolev IPM. By exploiting the graph structure, we demonstrate that the regularized Sobolev IPM provides a closed-form expression for fast computation. This advancement addresses long-standing computational challenges, and paves the way to apply Sobolev IPM for practical applications, even in large-scale settings. Additionally, the regularized Sobolev IPM is negative definite. Utilizing this property, we design positive-definite kernels upon the regularized Sobolev IPM, and provide preliminary evidences of their advantages for comparing probability measures on a given graph for document classification and topological data analysis.