Source-linked AI summary
Geometry Helps to Compare Persistence Diagrams
Michael Kerber, Dmitriy Morozov, Arnur Nigmetov
TL;DR
Assignment problems lack rigorous evidence about whether geometric structure helps in practice, despite extensive asymptotic study. This paper implements geometric bottleneck and Wasserstein matching algorithms using k-d trees and finds faster, lower-memory computation, including substantially improved persistence-diagram comparisons.
Problem
The paper addresses the lack of rigorous practical evaluation of whether geometry benefits assignment problems, motivated by persistence-diagram distance computation in topological data analysis.
Method
The paper implements geometric bottleneck and Wasserstein matching algorithms using k-d trees for proximity-based search, including an auction variant for points with multiplicities.
Results
The geometric matching implementations improve running time and space consumption over purely combinatorial counterparts and significantly outperform Dionysus for persistence-diagram comparison.
Takeaways & Limitations
Geometry enables faster computation of bottleneck and Wasserstein distances for two-dimensional bipartite point sets and persistence diagrams.
Takeaways & Limitations
The bottleneck procedure is not output-sensitive in the number of candidate pairs, although the authors expect it to be fast when a good initial approximation keeps the relevant sets small.
Abstract
from arXiv · showhide
Exploiting geometric structure to improve the asymptotic complexity of discrete assignment problems is a well-studied subject. In contrast, the practical advantages of using geometry for such problems have not been explored. We implement geometric variants of the Hopcroft--Karp algorithm for bottleneck matching (based on previous work by Efrat el al.) and of the auction algorithm by Bertsekas for Wasserstein distance computation. Both implementations use k-d trees to replace a linear scan with a geometric proximity query. Our interest in this problem stems from the desire to compute distances between persistence diagrams, a problem that comes up frequently in topological data analysis. We show that our geometric matching algorithms lead to a substantial performance gain, both in running time and in memory consumption, over their purely combinatorial counterparts. Moreover, our implementation significantly outperforms the only other implementation available for comparing persistence diagrams.
1 Introduction
The paper investigates whether geometric structure improves assignment problems in practice, focusing on bottleneck and Wasserstein distances between persistence diagrams. It develops geometric matching implementations and reports practical gains in computation and memory use.
- 1 Introduction: The paper asks whether geometric structure, previously studied for asymptotic improvements, also provides practical benefits for assignment problems.Its study centers on geometric versus purely combinatorial matching implementations.
- 1 Introduction: Persistence diagrams summarize homological information as planar point sets, and their distances act as proxy measures for data-set similarity.The relevant distances are Wasserstein or bottleneck distances under the L∞ metric.
- 1 Introduction: For bottleneck matching, the implementation augments Hopcroft–Karp with k-d trees that prune searches for remote matching vertices.This geometric strategy is compared with the combinatorial version that linearly scans vertices.
- 1 Introduction: For Wasserstein matching, the paper implements an auction-algorithm variant using weighted k-d trees to reduce the search range for best matches.The implementation is evaluated against a non-geometric auction algorithm and Dionysus.
- 1 Introduction: The paper extends the auction method to points with multiplicities, representing each mass as one entity and splitting it adaptively when needed.The mass-aware variant incurs overhead at low multiplicities but gains an advantage around average multiplicity 10, with the gap increasing thereafter.
- 1 Introduction: The present article adds auction matching with integer masses to its ALENEX 2016 conference version.The updated version also includes the associated discussion and evaluation.
2 Background
The paper formulates persistence-diagram distances as geometric assignment problems, using bottleneck and q-Wasserstein matching costs. A reduction constructs a weighted bipartite graph whose optimal matching preserves these distances, while removing skew edges simplifies the graph without changing the optimum.
- Assignment problem: The assignment problem seeks a minimum-cost perfect matching in a weighted bipartite graph; bottleneck and q-Wasserstein costs use the maximum edge weight or the q-norm of matching weights.For q = 1, the Wasserstein cost is the sum of edge weights, and as q tends to infinity it approaches bottleneck distance.
- Persistent homology and diagrams: Persistence diagrams summarize connectivity changes across scales as planar point sets, and distances between them serve as proxy measures of data-set similarity.The diagrams are stable: small changes in the input data cause only small changes in the diagram.
- Persistence distance as a matching problem: The persistence-distance construction forms a weighted complete bipartite graph from off-diagonal points and their diagonal projections, with L∞-based edge costs.The two vertex sets have equal size, and diagonal-to-diagonal edges have weight zero.
- Persistence distance as a matching problem: The graph’s optimal bottleneck and q-Wasserstein matching costs equal the corresponding persistence-diagram distances.For q > 1, the q-Wasserstein problem can be reduced to a 1-Wasserstein problem by raising edge weights to the q-th power and taking the q-th root.
- Graph simplification: An optimal matching contains no skew edges, so removing all skew pairs preserves the result while saving roughly a factor of two in graph size.The same conclusion holds for both bottleneck and Wasserstein distance.
- Experiments: Experiments use artificially generated normal instances and Vietoris–Rips diagrams from point clouds, with qualitative algorithmic differences consistent across additional tested settings.The largest reported diagrams contain 5762 points in dimension 9 and 1679 points in dimension 4.
3 Bottleneck matchings
The geometric bottleneck algorithm avoids explicit graph construction by combining matching tests, near-neighbor searches, and approximation-based candidate filtering. Experiments show improved practical scaling and substantially faster computation than combinatorial and Dionysus implementations.
- Exact bottleneck computation: The bottleneck distance is the smallest radius r for which the threshold graph G[r] contains a perfect matching.The exact value can be found by testing perfect matchings while searching over edge weights.
- Matching procedure: Hopcroft–Karp finds vertex-disjoint augmenting paths through layered subgraphs until all vertices are matched or no augmenting path remains.A perfect matching exists exactly when the maximum matching has n edges.
- Geometric acceleration: Near-neighbor queries replace explicit layer-subgraph construction, using deletable point sets to find vertices within radius r.The geometric structure exploits the metric graph rather than scanning every edge.
- Complexity: The geometric algorithm has an O(n^1.5 log n) bottleneck-distance bound for persistence diagrams, matching the stated theorem.Earlier geometric matching analysis gives O(n^1.5 log n) in R2 under the L∞ metric.
- Approximation and exact post-processing: The implementation first computes a δ-approximation, then searches an L∞ annulus to identify candidate pairs and computes the exact bottleneck distance from them.A 3-approximation initializes the search, while coordinate-based filtering constructs candidate sets.
- Limitation: The exact post-processing is not output-sensitive because intermediate coordinate candidate sets can exceed the final candidate set.The method is expected to remain fast when the initial approximation makes these sets small.
- Experiments: The geometric version scales better experimentally, runs roughly 10 times faster on the largest normal instance, and exceeds a 400-fold speed-up over Dionysus at 2800 points.The fitted practical exponent is α = 1.4 for the geometric version versus α = 2.3 for the non-geometric version.
4 Wasserstein matchings
The paper adapts the auction algorithm for Wasserstein matching, using ε-scaling and geometric data structures to accelerate best-object searches. Experiments show that the geometric implementation substantially improves runtime and memory usage, while also outperforming Dionysus on tested instances.
- Auction algorithm: The auction algorithm treats one side as bidders and the other as objects, maximizing benefit minus price while maintaining a partial matching.For minimum-cost matching, benefits are set to the negated edge costs.
- Auction algorithm: Each bid selects the best and second-best objects, assigns the best object, and raises its price by the value gap plus ε.The process continues until the matching becomes perfect.
- Implementation variant: Switching from the Jacobi to the Gauss–Seidel auction improves runtime by an order of magnitude in the experiments.The Gauss–Seidel variant performs one bid per iteration, and every bid is immediately satisfied.
- Geometric acceleration: Geometric bidding uses a weighted k-d tree to find high-value objects while pruning remote subtrees; price updates propagate along the path to the root.This replaces exhaustive or heap-based searches with proximity queries using subtree weight bounds.
- Experiments: 4× faster at 1,000 points and nearly 20× faster at 10,000 points, geometric auction scales empirically as O(n^1.6) versus O(n^2.3) non-geometric.Both variants compute a relative 0.01-approximation; lazy heaps make the non-geometric version competitive but substantially increase memory consumption.
- Experiments: 50× to about 400× speed-up over Dionysus is observed on real instances as input size increases.For normal data, the speed-up already exceeds 1000× at 1,000 points, so the corresponding plot is omitted.
5 Wasserstein matchings for repeated points
The paper extends geometric auction matching to persistence diagrams containing repeated points by representing multiplicities as masses and splitting them adaptively. Experiments show advantages at higher masses, while runtime and memory depend on instance structure and slicing behavior.
- Mass representation: Auction with integer masses represents repeated points as multi-bidders and multi-objects with equal total mass.The algorithm handles multiplicities directly rather than replacing each repeated point with individual copies.
- Mass assignment: Multi-bidders receive enough highest-value slices to cover their unassigned mass, splitting a leftover slice when necessary.The selected slices are assigned with total mass exactly equal to the bidder’s unassigned mass.
- Correctness and approximation: The Gauss–Seidel description preserves the correctness proof and relative-error estimate used for the standard auction.The original approach used Jacobi updates, but the paper applies the same ε-scaling error formula to its Gauss–Seidel variant.
- Geometric implementation: The mass-aware method uses a global k-d tree whose leaves represent multi-objects and whose weights track cheapest-slice prices.Searches maintain candidate slices whose total mass exceeds the multi-bidder’s unassigned mass.
- Experiments: For average mass 10, mass-aware auction is comparable to standard auction; at average masses 50 and 100, its advantage is evident.Experiments use normal instances with 1,000–10,000 points and compare average masses 1, 10, 50, and 100.
- Experiments: Runtime does not increase much with average mass and may decrease, depending strongly on the instance and mass distribution.This observation comes from four instances containing 10,000 points each.
- Memory consumption: Memory usually scales linearly with the number of points for fixed average mass, but can grow with total mass if all slices shrink to size one.Such intensive slicing did not occur in the reported examples.
6 Conclusion
The paper concludes that geometric methods accelerate bottleneck and Wasserstein distance computation for two-dimensional point sets, with direct relevance to persistence-diagram analysis. It identifies several directions for improving and evaluating these methods further.
- Geometry helps compute bottleneck and Wasserstein distances of bipartite point sets in two dimensions.
- Faster distance computation is expected to have an immediate impact on the computational pipeline of topological data analysis.
- A future study should compare the k-d tree bottleneck implementation with range trees and other point-location data structures.The range-tree alternative is described as theoretically more time efficient but more space demanding.
- For Wasserstein matching, planned improvements include parallel auction algorithms for large instances and heuristics for special cases.
- For q = 1, common off-diagonal points can be removed from both persistence diagrams before applying the auction algorithm without changing the Wasserstein distance.This follows from Wq(X, Y) = Wq(X \S, Y \S) when S is the set of common off-diagonal points.
- Grid-based approximation is a possible approach for very large instances, but discretization introduces approximation error.Snapping points to grid vertices can create high multiplicities, and a crude error bound scales with the number of points and grid-cell diameter.