Comparing complex data objects—like image histograms, social networks, or the topological "shape" of a dataset—requires more than simple Euclidean distance. We need metrics that respect the underlying geometry of the data. Optimal Transport (OT), particularly the Wasserstein distance, has emerged as the gold standard for this task because it measures the minimum "work" required to transform one distribution into another.
However, a significant mathematical hurdle remains: most geometric distances are incompatible with standard machine learning tools like Support Vector Machines (SVMs) or Gaussian Processes. These algorithms require positive definite kernels, a property that standard Wasserstein distances often lack due to their non-zero curvature.
Recent research has focused on "flattening" these geometric distances—transforming them into mathematically valid kernels that are both computationally efficient and theoretically sound.
The Kernel Compatibility Problem
To use a distance metric $d(x, y)$ in a kernel-based model, we typically wrap it in an exponential, such as the Gaussian kernel: $K(x, y) = \exp(-\gamma d(x, y))$. For this kernel to be valid (positive definite), the underlying distance $d$ must be conditionally negative definite.
As noted by Soheil Kolouri, Yang Zou, and Gustavo K. Rohde in Sliced Wasserstein Kernels for Probability Distributions, the standard Wasserstein distance fails this test. Its geometric structure is "curved" in a way that prevents it from being easily embedded into a flat Hilbert space. This means that using raw OT distances in an SVM can lead to unstable optimization and unreliable results.
Slicing and Trees: Flattening through Projection
One way to solve the kernel problem is to simplify the transport task. In one dimension, the Wasserstein distance has a simple, closed-form solution that is negative definite.
Soheil Kolouri and colleagues popularized the Sliced Wasserstein distance, which projects high-dimensional distributions onto many 1D lines (slices), calculates the distance on those lines, and averages the results. This maintains the geometric intuition of OT while ensuring the resulting metric can be used as a valid kernel.
Taking this further, Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi introduced Tree-Sliced Variants of Wasserstein Distances. Instead of simple 1D lines, they project distributions onto tree structures. Trees capture more complex hierarchical relationships than lines but still allow for fast, closed-form calculations that satisfy the negative definiteness requirement for kernels.
Sobolev Transport on Graphs
When data lives on a graph—such as traffic patterns on a road network or functional connectivity in the brain—the challenge intensifies. Standard OT on graphs is computationally expensive, often requiring complex linear programming.
To address this, Tam Le, Truyen Nguyen, and Kenji Fukumizu developed Unbalanced Sobolev Transport (UST). By using Sobolev norms—which measure how "smoothly" one distribution can be transformed into another across the graph's edges—they derived a metric that:
- Admits a closed-form solution, making it orders of magnitude faster than standard OT.
- Handles unbalanced mass, allowing comparisons between distributions with different total sums.
- Is kernel-friendly, naturally satisfying the mathematical properties needed for SVMs.
This line of work was extended in Scalable Sobolev IPM for Probability Measures on a Graph, where the authors (including Hideitsu Hino) used regularized Integral Probability Metrics (IPMs) to create fast, scalable distances for document classification and topological analysis.
Applications in Topology and Graph Learning
The need for valid kernels extends to Topological Data Analysis (TDA). TDA represents data shapes as "persistence diagrams," but these diagrams don't fit into standard vectors. Jan Reininghaus and his team addressed this in A stable multi-scale kernel for topological machine learning by creating a multi-scale kernel that maps these diagrams into a space where they can be compared stably and efficiently.
Similarly, in the realm of graph classification, researchers like Kai Ma (Transport based Graph Kernels) and Asiri Wijesinghe (A Regularized Wasserstein Framework for Graph Kernels) have developed regularized transport frameworks. These methods ensure that the resulting graph similarity scores are positive semi-definite, allowing researchers to plug sophisticated structural comparisons directly into standard machine learning pipelines.
Summary
The transition from raw geometric distances to "kernel-friendly" metrics represents a bridge between two worlds: the expressive power of Optimal Transport and the robust utility of kernel methods. By using techniques like slicing, tree-projections, and Sobolev regularization, researchers have made it possible to compare complex distributions and graphs with both mathematical rigor and computational efficiency.