Source-linked AI summary
Sliced Wasserstein Kernel for Persistence Diagrams
Mathieu Carrière, Marco Cuturi, Steve Oudot
TL;DR
Persistence diagrams are stable and useful, but their space lacks a natural Hilbert structure and existing diagram distances are unsuitable for straightforward kernel construction. The paper defines a Sliced Wasserstein kernel, proves stability and discriminativity relative to d1, and evaluates an accelerated implementation. Its discriminativity guarantee requires diagrams with cardinality bounded by a finite N.
Problem
Persistence diagrams are useful stable descriptors, but their non-Hilbert space and non-negative-definite natural distances complicate their use in learning kernels.
Method
The paper uses a conditionally negative definite Sliced Wasserstein approximation of d1 to define a tunable RBF kernel for persistence diagrams.
Results
The kernel is proved stable and discriminative, with strong equivalence to d1, and experimentally outperforms kernels from and [34] on several supervised classification problems.
Takeaways & Limitations
The proposed kernel preserves metric information between persistence diagrams while supporting kernel-based learning and faster approximate computation.
Takeaways & Limitations
The discriminativity result requires persistence diagrams with finite cardinalities bounded by some N ∈ N*.
Abstract
from arXiv · showhide
Persistence diagrams (PDs) play a key role in topological data analysis (TDA), in which they are routinely used to describe topological properties of complicated shapes. PDs enjoy strong stability properties and have proven their utility in various learning contexts. They do not, however, live in a space naturally endowed with a Hilbert structure and are usually compared with specific distances, such as the bottleneck distance. To incorporate PDs in a learning pipeline, several kernels have been proposed for PDs with a strong emphasis on the stability of the RKHS distance w.r.t. perturbations of the PDs. In this article, we use the Sliced Wasserstein approximation SW of the Wasserstein distance to define a new kernel for PDs, which is not only provably stable but also provably discriminative (depending on the number of points in the PDs) w.r.t. the Wasserstein distance $d_1$ between PDs. We also demonstrate its practicality, by developing an approximation technique to reduce kernel computation time, and show that our proposal compares favorably to existing kernels for PDs on several benchmarks.
1 Introduction
Persistence diagrams are useful, stable TDA descriptors, but their non-Hilbert geometry complicates learning. The paper introduces a Sliced Wasserstein kernel designed to retain stability while adding discriminative power.
- Persistence diagrams encode topological properties of complex data as point clouds with multiplicities in R2.They support applications including statistical learning, geometric inference, computer vision, materials science, and brain science.
- Their stability under data perturbations is a major strength, but standard learning methods require a Hilbert structure that diagram space lacks.Operations such as addition, averaging, and scalar products do not generally have direct analogues for persistence diagrams.
- Existing persistence-diagram kernels use either explicit feature maps or implicit constructions based on specialized comparisons.Examples include sampled functions, sorted distance-matrix entries, polynomial coefficients, heat-equation solutions, and related methods.
- Diagram distances are not negative semi-definite, whereas the Sliced Wasserstein relaxation has this property and can support kernel construction.This provides the mathematical basis for using Sliced Wasserstein geometry in persistence-diagram kernels.
- The proposed kernel is proved stable and discriminative, approximated for faster computation, and experimentally outperforms kernels from and [34] on several supervised classification problems.The paper also supplies distortion bounds quantifying how Sliced Wasserstein mimics diagram distances.
2 Background
The background defines persistence diagrams, diagram distances, positive-definite kernels, and Wasserstein distances for equal-mass measures. It motivates a Sliced Wasserstein kernel because ordinary diagram distances are unsuitable for direct Gaussian-kernel construction.
- 2.1 Persistent Homology: Persistent homology tracks topological events across sublevel sets and records each feature’s creation and destruction times in a persistence diagram.Points may represent connected components, loops, voids, or other topological features, with coordinates on the extended real line.
- 2.1 Persistent Homology: Persistent homology uses homological algebra to convert sublevel-set filtrations into compatible vector spaces and linear maps, with Gaussian elimination providing an implementation route.
- 2.1 Persistent Homology: A p-diagram distance minimizes the p-cost over partial bijections, while the bottleneck distance is the p=+∞ case.Unmatched points are compared with their projections onto the diagonal, and d_p approaches d_∞ as p grows.
- 2.1 Persistent Homology: Persistence diagrams are stable under small perturbations of their originating functions and can encode topology complementary to geometric or statistical quantities.They can also be invariant under reparametrization of the data.
- 2.2 Kernel Methods: Positive-definite kernels induce RKHS feature maps and Hilbert distances, and the paper seeks one whose induced distance has low distortion relative to d1.
- 2.2 Kernel Methods: Exponentiating a distance yields a Gaussian-type kernel for all bandwidths only when the distance is conditionally negative definite.The paper notes that d1 and squared diagram distances do not generally satisfy this requirement.
- 2.2 Kernel Methods: The proposed approach uses a conditionally negative definite Sliced Wasserstein approximation of d1 to define a tunable RBF kernel.Its bandwidth parameter is σ.
- 2.3 Wasserstein distance for unnormalized measures on R: For equal-mass nonnegative measures on the real line, the 1-Wasserstein distance is expressed through couplings, quantile functions, and a Lipschitz dual formulation.The measures have common mass r, and generalized quantile functions are defined for their normalized versions.
3 The Sliced Wasserstein Kernel
The paper defines the Sliced Wasserstein kernel by projecting persistence diagrams onto lines and integrating Wasserstein distances of the projections. It proves stability and metric equivalence with d1, while establishing conditional negative definiteness for kernel construction.
- 3 The Sliced Wasserstein Kernel: The Sliced Wasserstein distance projects persistence-diagram measures onto lines and integrates the resulting Wasserstein distances over directions.The construction augments each diagram with diagonal projections before comparing projected measures.
- 3 The Sliced Wasserstein Kernel: SW is conditionally negative definite, enabling construction of a valid positive definite kernel from it.The proof uses the conditional negative definiteness of the projected distance and linearity of integration.
- 3.2 Metric Equivalence: SW is stable with respect to d1 on persistence diagrams with bounded cardinality.This stability result is stated as Theorem 3.3 for the domain DbN.
- 3.2 Metric Equivalence: SW is discriminative with respect to d1 on persistence diagrams with bounded cardinality.Theorem 3.4 establishes discriminativity under the bounded-cardinality assumption.
N. Let S+
The discriminativity proof partitions projection directions into intervals where point-orderings remain fixed, then lower-bounds the resulting cosine integrals. The paper further establishes injectivity and proposes an approximation for faster kernel computation.
- N. Let S+: The proof partitions the half-circle using directions determined by pairwise point alignments, with at most M + 1 intervals when diagram cardinalities are bounded by N.The bound is |Θ| ≤ 2N(2N − 1) + 2 = M + 1.
- N. Let S+: The integral of |cos(·)| over each interval is lower-bounded using cosine concavity, producing a quadratic bound in the interval length.For interval length at most π, the bound is at least (θk+1 − θk)^2/(2π).
- N. Let S+: Within each interval, the ordering of projected diagram points remains unchanged, so the Wasserstein matching induces a fixed correspondence.This fixed correspondence supports the interval-wise lower bound used in the discriminativity argument.
- N. Let S+: The resulting argument concludes that SW is discriminative and that its induced feature map is continuous and injective with respect to d1.Injectivity extends to finite bounded persistence diagrams, beyond the initial bounded-cardinality formulation.
- Approximate computation: Exponentiating kSW can produce a universal kernel for applications including tests on distributions of persistence diagrams.This follows from the stated universal-kernel construction using exp(kSW).
- Approximate computation: The approximate kernel samples M directions, sorts projected points, averages ℓ1 distances, and runs in O(MNlog(N)) time.The approximation remains a kernel, and experiments found that few directions can suffice for good classification accuracies.
4 Experiments
The experiments compare kSW with kPSS and kPWG on 3D shape segmentation, orbit recognition, and texture classification, evaluating accuracy and computational cost. Across tasks, kSW is competitive or superior, while its approximation reduces computation with little accuracy loss.
- Experimental setting: The benchmark compares kSW, kPSS, and kPWG using classification accuracy and computational cost.Results are averaged over 10 LIBSVM C-SVM runs, with cross-validated cost factors.
- 3D shape segmentation: For 3D shape segmentation, kSW outperforms competing kernels for most categories, with lower result variance but generally higher training times.The task assigns relative-location labels to points using persistence diagrams computed from geodesic distance functions.
- Orbit recognition: For orbit recognition, a 6-direction kSW approximation yields a large accuracy increase and substantially improves training time under grid-search tuning.The task recovers one of five orbit parameters from persistence diagrams of generated orbits.
- Texture classification: For texture classification, kSW nearly achieves the best accuracy and has the best timing among the compared kernels.The approximation has little impact on accuracy while significantly reducing training time.
- Metric distortion: The kSW-induced distances are less spread than alternatives in the Airplane segmentation comparison, suggesting greater discriminative behavior.Their behavior also resembles that of a Gaussian kernel applied directly to d1.
5 Conclusion
The Sliced Wasserstein kernel is introduced as a persistence-diagram kernel equivalent to the first diagram distance, with fast approximations and favorable empirical performance.
- The Sliced Wasserstein kernel is provably equivalent to the first diagram distance between persistence diagrams.
- Fast algorithms approximate the kernel and support its practical computation.
- Experiments on several datasets show substantial improvements in accuracy and training times over competing kernels when parameters are tuned by grid search.
- Its infinite divisibility substantially facilitates parameter tuning through cross validation.