Research map / Learning theory and algorithms / Optimal transport
A Class of Topological Pseudodistances for Fast Comparison of Persistence Diagrams
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Extended Topological Pseudodistances (ETD), a tunable-complexity class of PD distances built from 1D Wasserstein distances of projections onto a finite set of angles, interpolating between persistence statistics and sliced Wasserstein distance.
Problem
Comparing persistence diagrams is computationally expensive with Wasserstein-type distances (cubic cost), while cheap persistence-statistics vectorizations lack discriminative power and may not distinguish distinct diagrams.
Approach
Project each persistence diagram (augmented with diagonal projections) onto a finite set of directions, compute 1D Wasserstein distances via sorting, and sum over directions and homology dimensions; the number of angles tunes complexity between PS and SWD.
Key results
- On Outex kNN, ETD_A4, ETD_A8, ETD_A16 and PS reach 0.99 accuracy, matching WD (0.98) and Hera WD (0.99), while basic ETD_A1 gets 0.89.
- Basic ETD_A1 takes about 4.19 ms per distance on Outex versus 459.24 ms for WD and 404.09 ms for SWD.
- On the autoencoder experiment, ETD_A1 is about 19.4x faster than SWD with one slice, and ETD is orders of magnitude faster than WD (3.69 ms vs 12544.96 ms).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ETD A4 instead of basic ETD A1 (ablation) | ETD · Outex | accuracy: 0.89 -> 0.99 | Helped |
| Use ETD A2 instead of basic ETD A1 (ablation) | ETD · Outex | accuracy: 0.89 -> 0.83 | Hurt |
| Increase projection angles from A1 to A8 (ablation) | ETD · Shrec07 | accuracy: 0.8 -> 0.9 | Helped |
| Increase projection angles from A1 to A2 (ablation) | ETD · Fashion-MNIST | accuracy: 0.7 -> 0.7 | No clear effect |
| Use NumPy implementation instead of standard ETD implementation (ablation) | ETD A1 · Fashion-MNIST H1 | time (milliseconds): 1.48 -> 0.06 | Helped |
| Use basic ETD A1 instead of WD | distance computation · Shrec07 H1 | time (milliseconds): 305774.22 -> 12.34 | Helped |
| Use basic ETD A1 instead of PS | distance computation · Fashion-MNIST H1 | time (milliseconds): 8.30 -> 1.48 | Helped |
| Increase the number of projection angles (ablation) | ETD · Outex | accuracy: 0.89 -> 0.83; 0.89 -> 0.99 | Mixed |
| Increase the number of projection angles (ablation) | ETD · Fashion-MNIST | accuracy: 0.7 -> 0.7 | No clear effect |
| Use ETD A1 instead of SWD with one slice | distance computation · Autoencoder RELU | time (milliseconds): 70.33 -> 6.00 | Helped |
Surprising findings
- The basic ETD_A1 (single angle) has lower kNN accuracy (0.89) on Outex than PS and the larger ETD variants, showing that a single projection loses discriminative information.
- On Shrec07 the PS distance achieves only 0.4 accuracy, far below ETD (0.8-0.9), contrary to the expectation that simple statistics suffice.
Limitations
- Theoretical accuracy guarantees are weak: stability bounds depend on M and the large-n limit, and the paper gives no strong accuracy guarantees.
- Experiments are small-scale (10-class Outex subset, 285 Shrec07 training meshes, 1000 Fashion-MNIST training samples) and use only kNN classification.
- Some reported table values are inconsistent or contain typos (e.g., ETD_A4 timing entry), and the claim that ETD_A1 accuracy is competitive is weaker than the larger-A variants.
Experimental setup
Datasets: Outex SHREC07 Fashion-MNIST synthetic concentric balls in R^100
Benchmarks: Outex SHREC07 Fashion-MNIST
Metrics: kNN accuracy average computation time (ms)
Baselines: WD Hera WD SWD PS Fisher Kernel Pot WD
Builds on: Sliced Wasserstein distance Persistence Statistics Wasserstein distance Hera
Closest papers by meaning
- Sliced Wasserstein Kernel for Persistence Diagrams (ICML 2017 · similarity 0.92)
- Wasserstein convergence of Cech persistence diagrams for samplings of submanifolds (NeurIPS 2024 · similarity 0.90)
- Persistence Fisher Kernel: A Riemannian Manifold Kernel for Persistence Diagrams (NeurIPS 2018 · similarity 0.89)
- Large Scale computation of Means and Clusters for Persistence Diagrams using Optimal Transport (NeurIPS 2018 · similarity 0.88)
- Persistent Homology for High-dimensional Data Based on Spectral Methods (NeurIPS 2024 · similarity 0.86)
- Topological Periodicity Test (TopPT) via Confidence Bound of Time-Delay Embeddings (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.