Geometry Helps to Compare Persistence Diagrams

Michael Kerber, Dmitriy Morozov, Arnur Nigmetov

Abstract

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.

Introduction

In Topological Data Analysis (TDA), the homological features of a dataset—such as connected components, holes, and voids—across different scales are summarized in a 2D plot known as a persistence diagram. To quantify the similarity between two datasets, researchers compute the distance between their respective diagrams, typically using the Bottleneck or Wasserstein distances.

Mathematically, calculating these distances is equivalent to solving a bipartite matching (or assignment) problem. Traditional combinatorial algorithms, like Hopcroft-Karp or the Hungarian algorithm, treat this as a pure graph problem. However, this approach ignores the inherent spatial structure of the points in $\mathbb{R}^2$. This paper investigates whether exploiting this geometric structure can yield significant practical speedups.

Bipartite matching between two sets of points (red and blue) representing persistence diagrams.

Methods: Injecting Geometry into Matching

The core innovation lies in replacing linear graph searches with geometric proximity queries powered by k-d trees.

  • Bottleneck Matching: The authors adapt the Hopcroft-Karp algorithm. Instead of a purely combinatorial search for augmenting paths, they utilize a k-d tree to rapidly identify unmatched vertices within a specific radius. The process involves computing a tight approximation of the distance followed by a post-processing step to determine the exact bottleneck distance.
  • Wasserstein Matching: For Wasserstein distance, the authors adapt Bertsekas's auction algorithm. In this model, points in one diagram "bid" on points in another. A weighted k-d tree is implemented to quickly find the most valuable "object" for a "bidder," pruning subtrees that cannot mathematically offer a better deal.
  • Handling Multiplicity: In discretized data, many points often share identical coordinates. The authors introduce an "integer mass" variant of the auction algorithm that treats overlapping points as a single "multi-bidder" with a specific mass. This prevents redundant calculations and significantly improves performance when average point multiplicity is high.

Experimental Setup

The algorithms were evaluated on two distinct types of persistence diagrams: synthetic "normal" instances and "real" instances derived from spherical point clouds.

Comparison of (a) a synthetic 'normal' persistence diagram and (b) a 'real' diagram from spherical point cloud data.

Key Results and Insights

The geometric approach yields massive improvements in both speed and efficiency:

  • Speedups: For diagrams with 25,000 points, the geometric Hopcroft-Karp is 10x faster than its combinatorial version. Compared to the Dionysus library, the geometric implementation is over 400x faster for diagrams of just 2,800 points. Similar 400x speedups were observed for Wasserstein distance on larger instances.
  • Memory Efficiency: The geometric auction algorithm maintains linear space complexity. Unlike non-geometric versions that may require quadratic space for competitive speeds, this approach significantly reduces RAM consumption, often using kilobytes instead of gigabytes.
  • The Diagonal is Special: In TDA, points can be matched to the diagonal for "free." The authors prove that "skew edges" (matching a point to a non-orthogonal projection on the diagonal) can be ignored, effectively halving the search space.

Conclusion

This work demonstrates that theoretical geometric improvements for matching problems translate into substantial real-world performance gains for TDA. While the bottleneck algorithm is exact, the Wasserstein implementation currently provides a relative approximation. Future work will focus on parallelization and exploring further spatial data structures to handle even larger datasets.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kerber2016geometry,
  author = {Michael Kerber and Dmitriy Morozov and Arnur Nigmetov},
  title = {{Geometry Helps to Compare Persistence Diagrams}},
  booktitle = {ALENEX},
  year = {2016},
  doi = {10.1137/1.9781611974317.9},
}
Figure