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:
- Preprocessing: A single run of Dijkstra’s algorithm identifies shortest paths from the root to all other nodes.
- 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.
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.
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