PaperlayerView exact revision on arXiv

Source-linked AI summary

Sierpiński--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximation

Sebastien Tchitchek, Julien Tierny

arXiv:2609.01528v1cs.CGcs.LG

TL;DR

Persistence-diagram comparison requires repeated Wasserstein assignments that can be costly at scale. The paper introduces dSK, which uses diagonal-aware SK scalar encodings and one-dimensional assignment, and reports substantial speedups with competitive clustering and kernel-based analysis. The construction is limited by the need for a common normalization triangle and can overestimate W2.

  • Problem

    Repeated evaluation of 2-Wasserstein distances becomes costly for large diagram collections and iterative algorithms, motivating fast distances that remain faithful to W2 geometry.

  • Method

    dSK encodes diagonally augmented persistence diagrams through the SK first-hit selector, solves a sorting-based one-dimensional assignment, and provides explicit point correspondences, Hilbert structure, and a Gaussian kernel.

  • Results

    Across 12 collections, dSK achieved a 626× median per-collection speedup and 2100× aggregate speedup over W2, while Hilbert k-means and Gaussian spectral clustering achieved mean ARIs of 0.756 and 0.800.

  • Takeaways & Limitations

    dSK combines efficient W2-related comparison with explicit correspondences and compatibility with Euclidean and kernel-based learning pipelines.

  • Takeaways & Limitations

    All diagrams must share a normalized persistence triangle known in advance, and dSK provides only one-sided control of W2, so it may substantially overestimate W2.

Abstract

from arXiv · show

This paper introduces the Sierpiński-Knopp (SK) Wasserstein distance, a fast metric between persistence diagrams. The SK-Wasserstein distance, denoted $d_{\mathrm{SK}}$, maps diagram points and their diagonal projections to the unit interval via the Sierpiński-Knopp space-filling curve on the upper diagonal triangle. The encoded point sets are then efficiently matched via one-dimensional optimal assignment, in \(O(N\log N)\) steps, yielding an explicit diagonal-aware point assignment between the two input persistence diagrams. We show that the SK-Wasserstein distance controls the classical \(2\)-Wasserstein distance between diagrams, admits an explicit isometric embedding into a Hilbert space, and induces a positive-definite Gaussian kernel, making the resulting geometry directly compatible with Euclidean and kernel-based learning methods. A tighter surrogate dissimilarity, noted \(W_Γ\), is also introduced based on the point assignments along the curve. Experiments on 12 scientific collections comprising 227 diagrams show median per-collection speedup of \(d_{\mathrm{SK}}\) over state-of-the-art approximations of \(W_2\) is \(626\times\), while the aggregate speedup over the full benchmark is \(2100\times\). Average-linkage partitions obtained from \(d_{\mathrm{SK}}\) and \(W_Γ\) each exactly match the corresponding \(W_2\) partition on 8 of the 12 collections. Hilbert \(k\)-means and Gaussian spectral clustering, both based on \(d_{\mathrm{SK}}\), achieve mean adjusted Rand indices (ARI) of \(0.756\) and \(0.800\), respectively, with respect to the benchmark reference partitions, compared to \(0.750\) obtained by average linkage on \(W_2\). The Gaussian \(d_{\mathrm{SK}}\) kernel supports other kernel-based analysis tasks, as illustrated by its use for contiguous segmentation of ordered diagram collections in our experiments.

1 Introduction

The paper introduces dSK as a fast, diagonal-aware persistence-diagram metric that replaces planar assignment with sorting-based one-dimensional transport. It also establishes links to W2 geometry, Hilbert embeddings, Gaussian kernels, and explicit point correspondences.

  • Method: dSK retains diagonal augmentation while replacing the two-dimensional assignment problem in the persistence triangle with one-dimensional assignment on [0, 1].The SK first-hit selector assigns scalar codes to augmented diagram points, which are compared through one-dimensional 1-Wasserstein transport.
  • Theory and computation: Sorting scalar lists yields fast dSK evaluation, while the SK curve’s 1/2-Hölder regularity controls the classical 2-Wasserstein distance.The one-dimensional assignment has a monotone closed-form solution, and dSK provides a computationally attractive W2 surrogate.
  • Learning compatibility: dSK has an explicit cumulative L1 representation, an isometric Hilbert embedding, and a positive-definite Gaussian kernel.These structures support Euclidean embedding and kernel-based learning on normalized persistence diagrams.
  • Related work: Unlike sliced constructions, dSK uses one deterministic injective encoding and returns a single explicit diagram-level assignment in the birth–death plane.The comparison directly targets quadratic diagram geometry rather than only first-Wasserstein geometry.
  • Assignments and surrogates: The monotone SK assignment produces an explicit diagonal-aware correspondence between input diagrams, which can be re-evaluated in the plane to define WΓ.WΓ is a tighter numerical surrogate for W2 but does not retain dSK’s metric and Hilbertian guarantees.

2 Preliminaries

The preliminaries define persistence diagrams, their normalization and diagonal-aware 2-Wasserstein comparison, then construct the finite-level SK traversal and its limiting first-hit selector.

  • Persistence diagrams: Persistence diagrams record topological features through birth–death pairs obtained as filtration thresholds cross critical values.Features far from the diagonal have larger persistence, while noise-induced features typically lie close to it.
  • Normalization: All diagrams are jointly normalized into the same persistence triangle so relative birth, death, and persistence scales are preserved across the collection.The framework can also normalize diagrams from point clouds or other filtered data.
  • 2-Wasserstein comparison: Diagonal augmentation adds projections of unmatched off-diagonal points, equalizes diagram cardinalities, and assigns zero cost to diagonal-to-diagonal matches.The resulting bijective assignment defines the standard diagonal-aware 2-Wasserstein distance.
  • SK construction: The recursive SK construction subdivides triangular cells and associates them with ordered dyadic subintervals of [0, 1].At each refinement, the first- and second-visited children receive the left and right interval halves, respectively.
  • Selectors: At level L, the finite selector assigns a point to the left endpoint of the first-visited dyadic interval whose cell contains it, with O(L) query cost.The finite selectors converge pointwise to the first-hit selector, which is injective on the persistence triangle.

3 Sierpiński–Knopp Wasserstein distance between normalized persistence diagrams

dSK compares normalized persistence diagrams by encoding off-diagonal points and diagonal projections on [0, 1], then solving a one-dimensional assignment problem. This preserves diagonal-aware matching while enabling sorting-based evaluation, W2 control, and explicit point assignments.

  • Construction: dSK uses two layers: an injective SK-curve encoding of diagram points and diagonal projections, followed by one-dimensional assignment between augmented encodings.The augmentation mirrors standard matching by allowing unmatched features to pair with the diagonal.
  • Construction: The augmented scalar lists are matched by the monotone optimal coupling for one-dimensional W1, and the resulting pairing can be lifted back to the persistence triangle.Retaining point identities yields an explicit partial assignment, with unmatched points assigned to the diagonal.
  • Computational properties: O(N log N) evaluation follows from sorting two length-N lists of selector values once the relevant encodings have been computed.For fixed refinement level L, the total implementation cost is O(N(L + log N)).
  • Theoretical properties: The 1/2-Hölder regularity of the SK curve gives a constant-factor upper control of W2 by dSK, making dSK a fast surrogate for repeated W2 evaluations.For the normalized curve, the control constant is CSK = 2.
  • Surrogate dissimilarity: WΓ evaluates costs along the SK-induced correspondence and is a tighter upper surrogate for W2, but it is not a metric because its assignments can violate the triangle inequality.In the counterexample, WΓ(X, Z) ≈ 0.348 exceeds WΓ(X, Y) + WΓ(Y, Z) ≈ 0.183.
  • Theoretical properties: The dSK geometry is quantitatively comparable to W2 on any fixed finite collection of normalized persistence diagrams, although no universal reverse inequality is expected.The finite-collection statement provides a scope boundary for comparability.

4 Hilbertian Geometry and Gaussian Kernel Induced by dSK

dSK has a cumulative L1 representation that is injective and induces an explicit isometric Hilbert embedding. Its squared distance is conditionally negative definite, yielding a positive-definite Gaussian kernel for learning with persistence diagrams.

  • Gaussian kernel: The squared distance is conditionally negative definite, so exp(−dSK(X1, X2)^2/(2σ^2)) is a positive-definite Gaussian kernel.The kernel is the standard Gaussian kernel restricted to the embedded diagram space.
  • Cumulative representation: The squared dSK distance equals the L1 distance between the diagrams’ cumulative signatures on [0, 1].Thus the complete dSK geometry is encoded by a one-dimensional cumulative signal.
  • Cumulative representation: The cumulative encoding is injective: it recovers the signed measure, its positive and negative parts, and ultimately the original normalized persistence diagram.Disjoint supports separate off-diagonal contributions from diagonal cancellations.
  • Hilbertian geometry: An explicit embedding Φ maps diagrams into L2([0, 1] × R) so that Hilbert-space distance equals dSK.This makes dSK compatible with Euclidean embedding methods and vector-based learning pipelines.
  • Gaussian kernel: The Gaussian kernel supports support vector machines, kernel ridge regression, Gaussian processes, spectral or kernel clustering, and MMD-based comparisons.Given selector values, kernel evaluation has the same O(N log N) complexity as dSK itself.

5 Experimental evaluation

The evaluation benchmarks SK-based constructions on 12 scientific collections against numerical W2 references, examining convergence, geometric faithfulness, neighbourhood preservation, clustering agreement, and computational cost.

  • Scientific benchmark: The benchmark contains 227 persistence diagrams from 12 scientific collections, with collection sizes ranging from 7 to 48 diagrams.The diagrams contain 3,376,524 persistence pairs in total, and individual diagrams range from 22 to 102,735 pairs.
  • Convergence: At L = 30, median relative Frobenius errors are 6.97×10−8 for dSK,30 and 4.50×10−6 for WΓ,30.The corresponding worst-case errors are 1.41 × 10−5 and 6.63 × 10−5, respectively.
  • Convergence: At L = 30, every collection has Spearman correlation 1.000000 and NN@3 = 1.000 relative to L = 40 for both constructions.Thus, the reported refinement preserves global pairwise rankings and each sample’s three nearest neighbours at numerical precision.
  • Computational performance: dSK,30 is 34.7×–5007× faster than TTK W2 across collections, with a median speedup of 626×.Across the benchmark, recorded filter-computation times are 3401 seconds for W2 and 1.62 seconds for dSK,30.
  • Clustering agreement: The dSK,30 and WΓ,30 average-linkage partitions exactly match W2 on 8 of 12 collections, with median ARI 1.000 and mean ARIs 0.897 and 0.905.The dSK partition differs from W2 on four named collections, so exact preservation is not universal.

5.4 Application to Hilbertian and kernel-based clustering

The study compares three dSK-based clustering pipelines and finds Gaussian dSK spectral clustering strongest on average, while kernel segmentation also recovers temporal structure in ordered diagrams.

  • Clustering results: Average-linkage clustering on W2 obtained a mean ARI of 0.750 and perfect agreement on 7 collections, providing the comparison baseline.ARI values measure agreement with benchmark reference groups, with the number of clusters fixed from metadata.
  • Clustering results: 0.800 mean ARI was achieved by Gaussian dSK spectral clustering, versus 0.756 for Hilbert k-means and 0.667 for average linkage on dSK,30.The pipelines achieved perfect agreement on 7, 6, and 5 of 12 collections, respectively.
  • Clustering results: Gaussian dSK spectral clustering improved five collections and worsened none relative to direct average linkage on dSK.The largest gains included Viscous Fingering, Sea Surface Height, Volcanic Eruptions, and Vortex Street.
  • Clustering results: On Asteroid Impact and Earthquake, dSK average linkage matched W2 average linkage exactly, with ARIs of −0.077 and 0.368, respectively.The limited agreement on these collections therefore was not attributed to replacing W2 with dSK,30.
  • Temporal segmentation: Kernel segmentation of the 20-diagram Asteroid Impact sequence recovered two reference boundaries exactly, with boundary MAE 0.67 and ARI 0.756.Across eight eligible collections, it tied the best clustering ARI on six and exceeded all three clustering methods on Earthquake.

6 Limitations

The method requires common normalization and offers only one-sided W2 control; the alternative WΓ dissimilarity lacks metric and Hilbertian guarantees, while quadratic costs remain outlier-sensitive.

  • Normalization: All compared diagrams must lie in the same normalized persistence triangle, requiring a common bounding box known in advance.Changing the normalization range can alter previous scalar encodings and require recomputing distances and representations.
  • Distance control: The dSK bound prevents arbitrary underestimation of W2 but supplies no dataset-independent relative upper bound on dSK in terms of W2.dSK may substantially overestimate W2 because its monotone scalar assignment can differ from the planar optimum and charges some diagonal-projection pairings.
  • WΓ: WΓ may violate the triangle inequality because its pairwise SK-induced assignments can be mutually incompatible across triples.It is therefore a dissimilarity rather than a metric and cannot support metric-based indexing or guarantees.
  • WΓ: WΓ has no Hilbertian guarantee, so a Gaussian transformation of WΓ is not guaranteed to be positive definite.This distinguishes WΓ from dSK for kernel-based methods.
  • Robustness: The quadratic W2 cost disproportionately weights large displacements, making W2-based aggregation sensitive to outlier diagrams.WΓ inherits this limitation because it evaluates the SK-induced coupling with the same quadratic planar cost.

7 Conclusion

The paper introduces dSK as a fast diagonal-aware metric with explicit assignments, W2 control, and Hilbertian and kernel structure. Across scientific benchmarks, it substantially accelerates comparison while supporting competitive clustering and segmentation analyses.

  • Core construction: dSK replaces the planar partial-assignment problem with a one-dimensional assignment solvable by sorting in O(N log N), while retaining explicit diagonal-aware point correspondences.The correspondence can support downstream applications requiring point assignments.
  • Theory: Theoretical analysis shows that dSK controls classical diagram W2 and admits an explicit isometric Hilbert embedding with a positive-definite Gaussian kernel.These properties connect the metric to Euclidean and kernel-based learning methods.
  • Surrogate comparison: WΓ re-evaluates the monotone SK assignment with the planar quadratic cost and provides a tighter numerical surrogate for W2, but lacks dSK’s metric and Hilbertian guarantees.The two constructions therefore trade computational and structural guarantees against closer numerical agreement.
  • Benchmark results: 626× median per-collection speedup and approximately 2100× aggregate speedup were obtained for dSK,30 over W2 across 12 collections.The benchmark contained 227 persistence diagrams and 3.38 million persistence pairs.
  • Applications: 0.800 mean ARI was achieved by Gaussian-kernel spectral clustering, compared with 0.756 for Hilbert k-means and 0.750 for average linkage on W2.Average-linkage partitions from dSK,30 and WΓ,30 each exactly reproduced the corresponding W2 partition on 8 of 12 collections.

A Proofs

The appendix formalizes the normalized persistence triangle, the injective selector induced by the SK curve, and the one-dimensional measure construction defining dSK.

  • Definitions: The ambient domain is the upper diagonal triangle A△, with the diagonal Δ contained inside it.Persistence diagrams are represented by finite atomic measures supported off the diagonal.
  • Definitions: The diagonal projection is defined by Euclidean orthogonal projection onto Δ.This projection supplies the diagonal representatives used in the augmented comparison.
  • SK selector: A continuous space-filling curve S maps [0,1] onto A△, and the selector ι chooses the minimum parameter in each fiber.The selector is well-defined, Borel measurable, and injective.
  • SK selector: The images of diagonal and off-diagonal points under ι are disjoint, preserving the distinction needed for diagonal-aware encoding.Injectivity establishes this disjointness directly.
  • Measure encoding: Each diagram is encoded by positive and negative atomic measures on [0,1], with equal total mass and a signed difference recording diagonal cancellations.The dSK construction combines these measures into a one-dimensional Wasserstein comparison.
  • Distance definition: The dSK distance is defined through one-dimensional transport between the augmented scalar marginals of two diagrams.For equal-mass atomic measures, the associated transport admits a monotone matching formulation.

Define the cumulative discrepancy

The construction compares diagonal-augmented persistence diagrams by encoding their points on [0, 1] and measuring a cumulative signed discrepancy between the resulting measures.

  • Monotone assignment: For sorted encoded lists, the one-dimensional assignment pairs entries monotonically and computes the sum of absolute coordinate differences.This is the closed-form one-dimensional Wasserstein assignment.
  • Cumulative discrepancy: The cumulative discrepancy H(t) is the difference between the two encoded measures’ masses on [0, t].Equivalently, it records the difference between cumulative counts below each threshold t.
  • Cumulative discrepancy: The absolute cumulative discrepancy integrates to the one-dimensional assignment cost.The crossing-event argument identifies the cumulative integral with the monotone matching cost.
  • Measure construction: The diagonal-aware construction forms equal-mass encoded measures by combining each diagram’s points with the other diagram’s diagonal projections.The two multisets contain encoded original points from one diagram and encoded diagonal projections from the other.
  • Complexity: Consequently, dSK can be evaluated in O(N log N) time by sorting two length-N lists and making a linear pass.The relevant encoded values must first be computed from the selector and diagonal projections.
  • Geometric control: The fixed Sierpiński–Knopp curve is 1/2-Hölder, which yields control of the diagonal-aware 2-Wasserstein distance by dSK.The resulting comparison transports the one-dimensional coupling back to the persistence triangle.

A.0.1 Kernelization: conditional negative definiteness of d2

The cumulative L1 representation makes dSK conditionally negative definite and Hilbertian, enabling a positive-definite Gaussian kernel and explicit learning-oriented embeddings.

  • Conditional negative definiteness: The absolute value is conditionally negative definite, so integrating pointwise inequalities shows that dSK^2 is conditionally negative definite.The proof applies the scalar result to cumulative signatures and integrates over t.
  • L1 representation: The signed-measure construction represents dSK through cumulative functions HD and HE on [0, 1].The distance is the L1 difference between these cumulative signatures.
  • Gaussian kernel: For every σ > 0, the Gaussian kernel exp(−dSK^2/(2σ^2)) is positive definite.This follows by applying Schoenberg’s theorem to the conditionally negative definite squared distance.
  • Injectivity: The cumulative signature is injective, so distinct persistence diagrams remain distinguishable in the L1 representation.Disjoint supports for ordinary and diagonal- projected points allow recovery of the diagram encoding.
  • Hilbert embedding: An explicit map Φ embeds diagrams into L2([0, 1] × R) isometrically, making dSK a Hilbertian metric.The squared Hilbert-space distance equals dSK^2.
  • Kernel consequences: The Gaussian kernel is characteristic and universal on compact subsets of the diagram space.The paper connects these properties to kernel machines and distributional methods such as MMD.

B.1 Kernel-based contiguous segmentation of ordered collections

The Gaussian dSK kernel supports fixed-k contiguous segmentation of ordered persistence-diagram collections by minimizing within-segment kernel dispersion.

  • Task setup: The segmentation task treats ordered diagram collections as contiguous segments, including temporal change-point settings.More generally, the stored order may represent another ordered parameterization.
  • Objective: A segment’s cost is the sum of squared feature-space distances from its diagrams to their segment mean.This cost is equivalently expressed through the Gaussian dSK kernel.
  • Optimization: Dynamic programming finds globally optimal boundaries after fixing k to the number of reference groups.Reference labels and boundary locations are withheld from the optimization and used only for evaluation.
  • Constraint: The procedure permits one-sample segments because no minimum segment length is imposed.Such a segment can be selected when it reduces total within-segment dispersion.
  • Evaluation: Boundary MAE evaluates boundary displacement, whereas ARI evaluates the complete predicted partition.The metrics therefore assess localization and sample assignment, respectively.
  • Evaluation scope: Only 8 of 12 collections are eligible because their reference labels must form exactly k contiguous blocks in stored order.The table reports results for this eligibility subset using the Gaussian dSK kernel at L = 30.
Loading 2609.01528v1…