Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics

Tam Le, Truyen Nguyen, Dinh Phung, Viet Anh Nguyen

Abstract

Optimal transport (OT) is a popular measure to compare probability distributions. However, OT suffers a few drawbacks such as (i) a high complexity for computation, (ii) indefiniteness which limits its applicability to kernel machines. In this work, we consider probability measures supported on a graph metric space and propose a novel Sobolev transport metric. We show that the Sobolev transport metric yields a closed-form formula for fast computation and it is negative definite. We show that the space of probability measures endowed with this transport distance is isometric to a bounded convex set in a Euclidean space with a weighted $l_p$ distance. We further exploit the negative definiteness of the Sobolev transport to design positive-definite kernels, and evaluate their performances against other baselines in document classification with word embeddings and in topological data analysis.

Introduction

Comparing probability distributions—such as word frequencies in documents or persistence diagrams in topology—is a fundamental task in machine learning. Optimal Transport (OT) is often the preferred metric because it accounts for the underlying geometry of the data. However, OT faces two major drawbacks: high computational complexity (typically scaling at $O(n^3)$) and a lack of negative definiteness, which makes it difficult to use in standard kernel-based algorithms like Support Vector Machines (SVMs).

Previous attempts to scale OT, such as Tree-Wasserstein (TW), require mapping data onto a tree structure. While fast, this oversimplifies the geometry by ignoring loops and complex connectivity found in most real-world datasets.

Sobolev Transport on Graphs

To address these issues, we propose Sobolev Transport ($S_p$), a framework that operates on general graph metric spaces. By allowing for general graphs (such as $k$-nearest neighbor or random graphs), the metric captures more of the data's true manifold structure compared to tree-based approximations.

Figure 1: Sobolev Transport is defined over general graph metric spaces, allowing it to capture complex connectivity and manifold structures that tree-based methods might ignore.

Key Innovations

  • Closed-Form Solution: By relaxing the Lipschitz continuity constraint of standard $W_1$ transport to a graph-based Sobolev space constraint, we derive a closed-form formula. This makes the distance calculation nearly instantaneous—linear in the number of edges—after a one-time preprocessing step.
  • Negative Definiteness: We prove that for $1 \le p \le 2$, the distance is negative definite. This allows researchers to define valid positive-definite kernels, such as $k(x, y) = \exp(-t \cdot S_p(x, y)^p)$, for use in standard machine learning workflows.
  • Slicing for Robustness: To reduce sensitivity to the choice of a root node in the graph, we introduce Sliced Sobolev Transport, which averages the distance over multiple randomly chosen root nodes.

Experimental Results

We evaluated Sobolev Transport across two distinct domains: document classification (using word2vec embeddings) and Topological Data Analysis (TDA) using persistence diagrams.

Accuracy and Performance

In document classification tasks, Sobolev Transport variants ($k_{S_1}$ and $k_{S_2}$) consistently matched or outperformed baselines. For example, on the CLASSIC dataset, Sobolev Transport achieved approximately 95% accuracy, significantly higher than the ~55% seen with the standard OT baseline.

Figure 4: Accuracy comparison on the CLASSIC dataset. Sobolev Transport kernels ($k_{S_1}$, $k_{S_2}$) significantly outperform the standard Optimal Transport ($k_{OT}$) baseline.

Massive Speedups

The computational efficiency is a major highlight of this framework. In TDA experiments on the Orbit dataset, computing the kernel matrix with standard OT required over 39 hours. In contrast, Sobolev Transport finished the same task in just 25 minutes. The method also scales gracefully to graphs with over 40,000 nodes, a regime where traditional OT solvers typically fail or require massive resources.

Conclusion

Sobolev Transport provides a significant step forward for practitioners who need the geometric sensitivity of Optimal Transport but require the scalability of simple Euclidean distances. By bridging the gap between computational efficiency and structural representation, it offers a robust and mathematically sound tool for high-dimensional data analysis.

Summary updated

Abstract

Optimal transport (OT) is a popular measure to compare probability distributions. However, OT suffers a few drawbacks such as (i) a high complexity for computation, (ii) indefiniteness which limits its applicability to kernel machines. In this work, we consider probability measures supported on a graph metric space and propose a novel Sobolev transport metric. We show that the Sobolev transport metric yields a closed-form formula for fast computation and it is negative definite. We show that the space of probability measures endowed with this transport distance is isometric to a bounded convex set in a Euclidean space with a weighted l_p distance. We further exploit the negative definiteness of the Sobolev transport to design positive-definite kernels, and evaluate their performances against other baselines in document classification with word embeddings and in topological data analysis.
BibTeX
@inproceedings{le2022sobolev,
  author = {Tam Le and Truyen Nguyen and Dinh Phung and Viet Anh Nguyen},
  title = {{Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=8cMxyh5fOjZ},
}
Figure