Persistence-based topological optimization: a survey

This survey provides a comprehensive overview of the theoretical foundations, algorithmic techniques, and practical applications of using gradient-based optimization to minimize persistence-based loss functions in topological data analysis, accompanied by an open-source library to facilitate research and accessibility for newcomers.

The Gist

Imagine you are a sculptor working with a block of clay. Your goal isn't just to make a pretty shape, but to ensure the sculpture has specific "holes" or "loops" in it—like the hole in a donut or the tunnel through a pretzel.

In the world of data science, Topological Data Analysis (TDA) is the tool we use to count these holes, loops, and voids in complex data (like a cloud of points, a network of friends, or a digital image). It turns messy data into a simple "scorecard" called a Persistence Diagram. This diagram is a map that tells us: "Here is a loop that appeared at this moment and disappeared at that moment."

The Problem:
For a long time, these "scorecards" were great for analyzing data, but terrible for creating or fixing it. Why? Because the math behind these diagrams is jagged and broken. If you try to use standard computer optimization (like gradient descent, which is how AI learns) to change the data to get a better scorecard, the math "breaks." It's like trying to roll a ball down a staircase; the ball gets stuck on the edges and doesn't know which way to go.

The Solution (This Paper):
This survey paper is a "cookbook" for a new generation of mathematicians and data scientists. It explains how to smooth out those jagged edges so we can use AI to design data with specific shapes.

Here is the breakdown using everyday analogies:

1. The "Scorecard" (Persistence Diagrams)

Think of a Persistence Diagram as a receipt for a party.

• Birth: When a guest arrives (a feature appears).
• Death: When a guest leaves (a feature disappears).
• Persistence: How long they stayed.
  If a guest stays for the whole party, that's a "real" feature (like a solid loop). If they arrive and leave immediately, they are just "noise" (like a tiny, accidental bump).

2. The "Jagged Staircase" Problem

Imagine you want to rearrange the guests at the party so that the "VIPs" (the real features) stay longer.

• Old Way (Vanilla Gradient): You try to move the guests one by one. But because the rules of the party are so strict (mathematically "non-smooth"), moving one guest might suddenly change the entire guest list's status. The computer gets confused, takes a step, hits a wall, and stops. It's inefficient and slow.
• The Paper's Insight: The authors realized that while the staircase looks jagged, it's actually made of smooth flat sections (called Strata). If you know which flat section you are on, you can walk smoothly.

3. The New Tools (The "How-To")

The paper introduces several clever tricks to navigate this staircase:

• Stratified Gradient Descent (The "Map Reader"):
  Instead of just guessing which way to move, this method looks at the "map" of the staircase. It checks the surrounding flat areas, calculates the best average direction, and moves there. It guarantees you won't get stuck on a tiny edge.

  • Analogy: Instead of blindly pushing a boulder, you send out scouts to check the terrain, then push the boulder in the direction that works for the whole neighborhood.

• Big-Step Gradient Descent (The "Teleporter"):
  The old way moves one guest at a time. This method realizes that to change the "VIP status" of a loop, you might need to move many guests at once. It calculates a massive, coordinated move that jumps over the jagged edges entirely.

  • Analogy: Instead of walking up the stairs one step at a time, you find a hidden elevator that takes you straight to the next floor.

• Diffeomorphic Interpolation (The "Smooth Paintbrush"):
  Sometimes, the computer only calculates how to move a few specific points (the "critical" ones). This leaves the rest of the data frozen. This method takes those few instructions and "paints" a smooth path for every point in the data to follow.

  • Analogy: If you only tell the captain of a ship how to steer, the whole ship turns. This method ensures the entire ship (the data) turns smoothly, not just the captain.

4. Why Does This Matter? (Real-World Uses)

Once we can smoothly optimize these diagrams, we can do amazing things:

• Fixing Noisy Images: Imagine a photo of a face where the nose is missing because of a glitch. We can use this math to "teach" the AI to fill in the nose by ensuring the topological "loop" of the face is preserved.
• Designing New Materials: Scientists can design new metal alloys or 3D-printed structures that must have specific internal tunnels to be strong or flexible. The AI designs the shape to guarantee those tunnels exist.
• Better AI Models: We can force AI models to be simpler. If an AI is learning to recognize cats, we can tell it, "Don't make the decision boundary too complicated." This stops the AI from "memorizing" the training data (overfitting) and helps it generalize better.

Summary

This paper is the bridge between Abstract Math (Topology) and Practical AI (Optimization).

Before, Topology was a microscope to look at data.
Now, thanks to these new "smooth gradient" techniques, Topology is a chisel. We can use it to actively carve, shape, and improve data, ensuring that the digital worlds we build have the right holes, loops, and structures to function correctly.

The authors also provide a free software library (a "playground") so anyone can try these tools without needing a PhD in mathematics to start.

Technical Summary

1. Problem Statement

Topological Data Analysis (TDA) utilizes Persistent Homology (PH) to extract quantitative descriptors (Persistence Diagrams, or PDs) from structured data like point clouds, graphs, and images. While PDs provide robust topological features (connected components, loops, voids), integrating them into modern machine learning pipelines is challenging because:

• Non-linearity and Non-smoothness: The space of persistence diagrams ($\mathcal{D}$) is not a linear vector space; it is a metric space with a complex stratified structure.
• Optimization Difficulty: Standard gradient-based optimization (the backbone of deep learning) requires differentiable loss functions. Since PDs are discrete and depend on the ordering of filtration values, the map from data parameters to PDs is generally non-differentiable everywhere, making it difficult to define gradients for minimizing topological losses.
• Sparsity: Naive gradient approaches often result in extremely sparse updates, where only a tiny fraction of data points are modified at each step, leading to slow and erratic convergence.

The paper addresses the question: How can we rigorously define and efficiently compute gradients for objective functions that depend on persistence diagrams to enable topological optimization?

2. Methodology and Theoretical Framework

The survey structures the solution into a differential framework and various optimization algorithms.

A. Differential Framework for Persistence Diagrams

The authors rely on the theoretical work of Leygonie, Oudot, and Tillman to establish differentiability:

• Local Lifts: They define differentiability of a map $PH: M \to \mathcal{D}$ (where $M$ is a parameter manifold) by identifying PDs with their lifts in a Euclidean space $\mathbb{R}^{2m} \times \mathbb{R}^n$. This involves fixing an ordering of the persistence pairs (birth/death times) and unpaired simplices.
• Stratification: The space of filtrations is partitioned into strata based on the ordering of simplex values. Within each stratum, the persistence pairing is constant, making the map locally smooth (differentiable).
• Chain Rule: A key theoretical result (Proposition 3.9) states that even though the lift depends on the specific stratum, the gradient of a composite loss function $L = \ell \circ PH$ is independent of the choice of lift, provided the loss is differentiable. This justifies treating PDs as vectors for backpropagation.

B. Optimization Algorithms

The paper categorizes optimization methods into three main families and two extensions:

1. Vanilla Gradient Descent:

   • Computes the gradient based on the current persistence pairing (local lift).
   • Limitation: Highly sparse; updates only the specific simplices involved in the critical pairs, leading to slow convergence.

2. Stratified Gradient Descent:

   • Inspired by the Gradient Sampling method.
   • Samples points in the $\epsilon$-neighborhood of the current iterate, specifically targeting neighboring strata.
   • Computes the convex hull of gradients from these samples and selects the vector with the smallest norm (Goldstein subgradient).
   • Benefit: Provides stronger theoretical convergence guarantees (convergence to an $\epsilon$-stationary point) and smoother descent.

3. Big-Step Gradient Descent:

   • Designed specifically for singleton losses (pushing a specific PD point to a target).
   • Instead of updating only the critical pair, it identifies a set of simplices ($X_\sigma$) that must move jointly to preserve the pairing structure while moving the target point.
   • Benefit: Allows "jumping" over multiple strata in a single step, significantly accelerating convergence for specific tasks.

4. Gradient Extensions (to mitigate sparsity):

   • Downsampling (Distributed Gradients): Computes gradients on multiple smaller subcomplexes (subsamples or nerve complexes) and averages them. This creates denser gradients and reduces computational cost.
   • Diffeomorphic Interpolation: Uses kernel methods (e.g., Gaussian kernels) to interpolate the sparse gradient vector field defined only on critical points to the entire data space. This allows updating all points in a dataset, not just the critical ones, and enables reusing gradients for new data points.

3. Key Contributions

• Unified Framework: The paper provides the first comprehensive survey unifying the theoretical foundations (differential structure of PDs) with practical algorithmic implementations for topological optimization.
• Algorithmic Catalog: It details and compares specific gradient schemes (Vanilla, Stratified, Big-Step) and extensions (Downsampling, Diffeomorphic), analyzing their computational complexity and convergence properties.
• Open-Source Library: The authors provide a Python library (git-westriver/benchmark_ph_optimization) that implements all discussed methods, serving as a benchmark and playground for researchers.
• Application Survey: It systematically reviews applications in Filtration Learning (learning optimal filtration functions for images, graphs, and point clouds) and Topological Regularization (penalizing model complexity or enforcing topological priors in generative models, dimensionality reduction, and segmentation).

4. Results and Numerical Illustrations

The authors present numerical experiments to validate the methods:

• Gradient Behavior: Visualizations show that Vanilla and Stratified gradients are sparse (moving few points), whereas Diffeomorphic and Big-Step gradients move a significant portion of the data, leading to smoother and faster optimization trajectories.
• Convergence Speed:
  • Big-Step achieves the fastest loss decrease (reaching near-global optima in <10 iterations) but has the highest computational cost per step due to complex pairing updates.
  • Diffeomorphic gradients offer a strong balance, providing fast convergence with moderate computational overhead, especially when combined with subsampling for large datasets.
  • Stratified gradients provide theoretical guarantees but are computationally expensive due to the need to sample neighboring strata.
• Scalability: Experiments on large point clouds (e.g., the Stanford Bunny with ~36k points) demonstrate that vanilla gradients fail to produce perceptible changes due to sparsity. In contrast, Diffeomorphic and Distributed gradients successfully optimize the topology of large datasets by leveraging subsampling and interpolation.
• Topological Autoencoder: In a dimensionality reduction task, methods using topological gradients (specifically Diffeomorphic and Big-Step) successfully preserved the topological structure (loops) of the data in the latent space, outperforming standard autoencoders and naive gradient approaches.

5. Significance and Future Directions

• Bridging TDA and Deep Learning: This work is pivotal for integrating TDA into deep learning, moving from static feature extraction to dynamic, learnable topological descriptors.
• Regularization: It offers a rigorous way to regularize models against overfitting by penalizing topological complexity (e.g., decision boundary loops) or enforcing specific topological priors (e.g., in material design or image generation).
• Open Challenges: The survey identifies critical open questions:
  • Creating Topology: Current methods are better at destroying or simplifying topology (regularization) than creating new topological features from scratch (generative tasks), as creating a new point in a PD is a non-generic event.
  • Non-Gradient Methods: The non-smoothness of the problem suggests exploring non-gradient-based optimization (e.g., genetic algorithms).
  • Multiparameter Persistence: Extending these optimization techniques to multiparameter persistence (filtrations valued in $\mathbb{R}^d$) remains a significant theoretical and computational challenge.

In summary, the paper establishes that while topological optimization is theoretically complex due to the discrete nature of persistence, it is practically feasible through stratified differential frameworks and specialized gradient algorithms, opening new avenues for topology-aware machine learning.