Sparsification of the Generalized Persistence Diagrams for Scalability Through Gradient Descent

Mathieu Carrière, Seunghyun Kim, Woojin Kim

TL;DR

This paper introduces a method to make Generalized Persistence Diagrams (GPDs)—a powerful but computationally heavy tool in Topological Data Analysis (TDA)—scalable for large datasets. By using gradient descent to "sparsify" the domain of these diagrams, the authors achieve a 5x to 15x speedup in computation time while maintaining, and sometimes even improving, classification accuracy on time-series benchmarks.

What Problem Does This Paper Address?

In TDA, we use "persistence" to track how topological features (like holes or loops) appear and disappear as we look at data at different scales. While this works well for one parameter (e.g., distance), many real-world datasets require multi-parameter persistence (e.g., looking at distance and density simultaneously).

The Generalized Persistence Diagram (GPD) is the gold standard for capturing this rich information. However, it has a massive "scalability wall." To compute a GPD, you must evaluate it over a set of "intervals." The number of possible intervals is astronomical, making the full GPD computationally prohibitive for large-scale machine learning. Researchers usually settle for a fixed, "sparse" grid of intervals, but choosing these intervals manually is guesswork and often leads to a loss of critical information.

Methods

The authors propose a way to automatically optimize the selection of intervals using gradient descent. Their approach involves several key innovations:

  1. Sparse Erosion Distance: They adapt the "erosion distance" (a standard metric for GPDs) into a new version that works even when comparing GPDs defined on different sets of intervals.
  2. Domain-Only Optimization: Crucially, they prove that when comparing GPDs of the same data over different domains, the distance depends only on the domains themselves, not the underlying data. This means they can optimize the interval set once without recomputing the expensive GPDs at every single step of the gradient descent.
  3. Vectorization ($\mathbb{R}^6$ Embedding): They represent each interval as a point in 6D space (capturing coordinates and lengths). This allows them to treat the interval selection problem as a continuous optimization task in Euclidean space.
  4. Differentiable Loss: They derive a closed-form formula for their loss function and prove it is Lipschitz stable and differentiable almost everywhere, making it "friendly" for standard gradient descent solvers like PyTorch.

Datasets

The method was evaluated on 18 time-series datasets from the well-known UCR (University of California, Riverside) repository. These include:

  • Medical/Biological: ECG200, MedicalImages, DistalPhalanxOutline.
  • Motion/Sensor: GunPoint, SwedishLeaf, Plane.
  • Power/Control: PowerCons, ItalyPowerDemand, SyntheticControl.

The time-series data were converted into point clouds using time-delay embedding before TDA features were extracted.

Key Insights and Ideas

  • The "Independence" Breakthrough: The most significant insight is that the loss function used to optimize the intervals is independent of the input persistence modules. This bypasses the need for "differentiating through the TDA pipeline," which is usually the slowest part of TDA-based optimization.
  • Quality over Quantity: The results show that a small, "smart" set of 400 optimized intervals often captures more relevant topological information than a massive, "dumb" grid of 1,600 intervals.
  • Geometric Stability: By proving the loss function is Lipschitz stable, the authors ensure that small changes in the interval parameters won't lead to wild, erratic jumps during optimization, allowing for smooth convergence.

Key Results

  • Efficiency: The optimized sparse GPDs were computed 5.4x to 15.7x faster than the full GPDs.
  • Accuracy: Despite using significantly fewer intervals, the optimized GPDs achieved classification accuracies comparable to—and in several cases (like the MI, GPA, and GPM datasets) better than—the full GPDs.
  • Optimization Success: In almost all cases, the "Optimized Sparse" version outperformed the "Initial Sparse" version (random/grid start), proving that the gradient descent successfully found more discriminative topological features.

Limitations and Future Work

  • Interval Complexity: The current work limits intervals to those with at most two minimal points and one maximal point to keep the $\mathbb{R}^6$ embedding simple. The authors note that allowing more complex interval shapes could capture even richer information but would complicate the optimization.
  • Dataset Dependency: While the loss function itself is independent of the data, the optimal set of intervals for one type of data (e.g., heartbeats) might not be the best for another (e.g., leaf shapes). The authors suggest exploring dataset-dependent terms in the loss function.
  • Heuristics for Stopping: There is currently no formal "stopping criterion" to decide when a sparse GPD is "good enough," which remains an open area for heuristic development.

Summary updated

BibTeX
@inproceedings{carriere2025sparsification,
  author = {Mathieu Carrière and Seunghyun Kim and Woojin Kim},
  title = {{Sparsification of the Generalized Persistence Diagrams for Scalability Through Gradient Descent}},
  booktitle = {SoCG},
  year = {2025},
  doi = {10.4230/lipics.socg.2025.29},
}
Figure