TL;DR
Comparing persistence diagrams is a major computational bottleneck in Topological Data Analysis (TDA). This paper demonstrates that by injecting geometric data structures (like k-d trees) into classic bipartite matching algorithms, we can compute bottleneck and Wasserstein distances between diagrams orders of magnitude faster than existing standard software.
What Problem Does This Paper Address?
In Topological Data Analysis, the homological features of a dataset (like connected components, holes, and voids) across different scales are summarized in a 2D plot called a persistence diagram. To measure how similar two datasets are, researchers compute the distance between their persistence diagrams using either the Bottleneck distance or the Wasserstein distance.
Mathematically, finding these distances is a bipartite matching (or assignment) problem. While there are well-known combinatorial algorithms to solve this (e.g., the Hopcroft-Karp or Hungarian algorithms), they treat the problem purely as a graph, ignoring the fact that the vertices are points living in a 2D geometric space ($\mathbb{R}^2$). The authors tackle a highly practical question: can we exploit this spatial structure to make these distance computations significantly faster in practice?
Methods
The authors take classic combinatorial algorithms and replace linear graph searches with geometric proximity queries using k-d trees.
- For Bottleneck matching: They adapt the Hopcroft-Karp algorithm. Instead of building a layered graph combinatorially to find augmenting paths, they use a k-d tree to quickly find unmatched vertices within a specific radius. They first compute a tight approximation of the distance, then use a post-processing step to find the exact bottleneck distance.
- For Wasserstein matching: They adapt Bertsekas's auction algorithm, where "bidders" (points in diagram A) bid on "objects" (points in diagram B). They implement a weighted k-d tree to quickly find the most valuable object for a bidder, pruning subtrees that mathematically cannot offer a better deal.
- Auction with Integer Masses: In discretized data, many points often share the exact same coordinates. The authors introduce a variant of the auction algorithm that handles these overlapping points as a single "multi-bidder" with a specific mass (multiplicity). The algorithm only splits this mass when fractions of it need to be matched to different targets.
Datasets
The authors evaluated their algorithms on two types of data:
- Normal instances: Artificially generated persistence diagrams designed to mimic real-world data distributions, where the vast majority of points (topological noise) are concentrated near the diagonal, and a few points (true features) are further away.
- Real instances: Persistence diagrams generated from point clouds sampled uniformly from 4-dimensional and 9-dimensional spheres, processed using the Vietoris-Rips filtration via the DIPHA library.
Key Insights and Ideas
- Theory translates to practice: While asymptotic geometric improvements for matching problems have existed in theory for decades, this paper proves they translate to massive, practical real-world speedups.
- The diagonal is special: In TDA, points can be matched to the diagonal (representing features fading away) for "free." The authors mathematically prove that "skew edges" (matching an off-diagonal point to a diagonal point that isn't its direct orthogonal projection) can be entirely ignored. This safely cuts the search space in half.
- Multiplicity matters: Treating 100 identical points as a single entity with a mass of 100, rather than 100 individual points, prevents highly redundant calculations. Once the average multiplicity of points hits around 10, the "integer mass" auction algorithm vastly outperforms the standard auction algorithm.
Key Results
- Bottleneck Distance: The geometric Hopcroft-Karp algorithm is about 10x faster than its non-geometric counterpart for diagrams with 25,000 points. Compared to Dionysus (the only publicly available standard library at the time), it is over 400x faster for diagrams of just 2,800 points.
- Wasserstein Distance: The geometric auction algorithm is roughly 20x faster than the non-geometric version for 10,000 points. It also achieves a >400x speedup over Dionysus for larger instances.
- Memory Efficiency: The geometric auction algorithm uses strictly linear space. In contrast, making the non-geometric version competitively fast requires "lazy heaps," which consume quadratic space. The geometric approach saves massive amounts of RAM (e.g., using kilobytes instead of megabytes/gigabytes).
Limitations and Future Work
- Approximation vs. Exact: While the bottleneck algorithm computes the exact distance, the geometric auction algorithm for the Wasserstein distance computes a relative approximation (e.g., a 1% error margin). Computing the exact Wasserstein distance efficiently without massive overhead remains an open challenge.
- Future Directions: The authors suggest parallelizing the auction algorithm to handle even larger instances. They also plan to explore other spatial data structures (like range trees) and investigate grid-snapping approximation schemes to see if discretizing the space can further reduce computational time.
Summary updated