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

Tam Le, Truyen Nguyen, Dinh Q. 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 $\ell_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 is a fundamental task in machine learning, essential for applications ranging from document classification to shape analysis. The 1-Wasserstein distance, or Earth Mover’s Distance, is widely regarded as the gold standard for this task due to its ability to incorporate the geometry of the underlying space. However, standard OT faces two significant hurdles: computational inefficiency (requiring linear programming) and mathematical indefiniteness, which prevents its direct use in kernel-based methods like Support Vector Machines (SVMs).

While Tree-Wasserstein (TW) was introduced to mitigate these issues by restricting data to tree structures, many real-world datasets exhibit complex geometries better represented by general graphs. This work introduces Sobolev Transport, a metric that extends the benefits of TW to general graph structures while maintaining computational efficiency and kernel compatibility.

Methodology

Sobolev Transport is an integral probability metric that relaxes the strict Lipschitz constraint of the dual 1-Wasserstein formulation. By utilizing a graph-based Sobolev space, the authors derive a closed-form solution for the transport distance.

The Graph-Based Approach

The method operates on a graph where nodes represent data points. By selecting a "root node" and identifying shortest paths from this root to all other nodes, the derivative of a function on the graph is redefined. This relaxation allows the complex optimization problem of OT to be solved via a simple mathematical formula.

Algorithm and Slicing

The computation involves a two-step process:

  1. Preprocessing: A single run of Dijkstra’s algorithm identifies shortest paths from the root to all other nodes.
  2. Computation: The distance is calculated in linear time by summing mass differences along the pre-computed edges.

To capture the full geometry of the graph, the authors propose "Sliced Sobolev Transport," which averages distances computed from multiple randomly selected root nodes.

Empirical Evaluation

The proposed metric was evaluated on document classification tasks (using word2vec embeddings) and Topological Data Analysis (TDA) persistence diagrams.

Computational time comparison between standard Optimal Transport (OT) and Sobolev Transport variants.

As shown in Figure 3, Sobolev Transport variants ($k_{S_1^1}, k_{S_2^2}$) achieve significant reductions in time consumption compared to standard OT ($k_{OT}$). In large-scale experiments, such as the Orbit dataset, the kernel matrix computation time dropped from over 39 hours for OT to just 25 minutes for Sobolev Transport.

Classification accuracy on the CLASSIC dataset comparing OT, Tree-Wasserstein (TW), and Sobolev kernels.

Beyond speed, the Sobolev kernels demonstrate superior performance in classification tasks. Figure 4 illustrates that on the CLASSIC dataset, Sobolev kernels and Tree-Wasserstein (TW) significantly outperform the standard OT baseline, achieving accuracies above 90% compared to OT's ~55%.

Conclusion

Sobolev Transport provides a scalable, kernel-friendly alternative to traditional Optimal Transport for graph-structured data. By bypassing the linear programming bottleneck and guaranteeing positive-definite kernels, it enables the application of transport-based metrics to large-scale machine learning pipelines. Future research will focus on learning optimal graph structures directly from data to further enhance the metric's representational power.

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 $\ell_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 Q. 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