Abstract: 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 $L^p$-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.

Lay Summary:

We study a mathematical method called Sobolev IPM, which helps compare two sets of data points in the form of probabilities. This is useful in machine learning, where we often need to compare data distributions, e.g., to tell whether they are similar or not. The Sobolev IPM problem is hard to calculate. Therefore, it has not been used much in real-world applications. We develop a way to make it much easier and faster to compute, especially when the data points in the sets are connected in a graph. More concretely, we connect Sobolev IPM to a simpler type of math, leading to a new version that gives us a fast answer with the new formula. Moreover, it is then possible to use Sobolev IPM even on large datasets. Furthermore, the new version can be used to build even more powerful tools, called kernels for comparing sets of data points. We then test the proposed approach on tasks like classifying documents and analyzing complex shapes, and obtain promising results.