A Fast and Robust Method for Global Topological Functional Optimization

Paul Bendich, Yitzchak Solomon, Alexander WagnerOpenReview 2023 · OpenReview

TL;DR

This paper introduces STUMP, a novel method for optimizing topological functionals that significantly improves speed and robustness compared to existing backpropagation techniques. By "smearing" the topological loss over downsampled versions of the input data, STUMP produces more stable and intuitive results, making topological optimization practical for a wider range of applications.

What Problem Does This Paper Address?

Topological Data Analysis (TDA) uses persistence diagrams to capture global shape information. These diagrams are almost everywhere differentiable, allowing for "topological gradients" to be backpropagated to optimize functions involving them. However, this traditional backpropagation method is computationally expensive, unstable, and leads to fragile optima. This means that small changes in the input can drastically alter the optimized result, making it unreliable. The paper addresses the need for a faster, more stable, and robust method for optimizing these topological functionals, especially when they are combined with traditional machine learning losses.

Methods

The core of the paper's contribution is a new approach called "smearing" the topological loss. Instead of directly computing gradients on the original, high-resolution data, STUMP works by:

  • Downsampling: Creating multiple lower-resolution "approximates" of the input data. This is done by considering open covers of the data's underlying structure (e.g., a simplicial complex) and creating functions on the resulting smaller Čech complex.
  • Smearing the Loss: The topological loss is then computed on these downsampled versions and averaged. This effectively "smears" the topological information over a set of approximations, making the overall loss function more stable.
  • STUMP Pipeline: The authors combine this smearing technique with momentum-based optimization (specifically, Adam optimizer) to create their STUMP (Stochastic Topological Updates via Momentum and Pooling) pipeline. This allows for efficient computation of gradients by processing downsampled data and mixing gradients over time.
  • Critical Smearing: An extension is proposed to directly address the fragility of traditional topological backpropagation. This involves transferring gradients from the persistence diagram of the original function to approximate diagrams, then pulling them back to the original data space.

Datasets

The paper evaluates its method on several synthetic datasets designed to test specific topological optimization goals:

  • Double Well: To increase H0 persistence and separate wells.
  • Sampled Circle: To increase H1 persistence and fill in a circle.
  • Blobs: To decrease H0 persistence and connect blobs.

Additionally, they apply their method to the ISBI12 cell image dataset for unsupervised image segmentation, comparing it to prior work.

Key Insights and Ideas

  • Smearing for Stability: The key insight is that by averaging topological information over multiple downsampled versions of the data, the resulting loss function becomes much more stable to small perturbations. This directly combats the instability of traditional topological backpropagation.
  • Speedup through Downsampling: Computing persistence diagrams on smaller, downsampled representations of the data is significantly faster. This, combined with efficient gradient updates, leads to substantial speed improvements.
  • Robustness of Optima: The "smeared" optima are shown to be more robust to changes in input data, as demonstrated by random walker segmentation results. This means the optimized shapes are less likely to break apart or change drastically under minor variations.
  • Intuitive Results: The paper highlights that STUMP produces results that align more closely with human intuition for the desired topological transformations.

Key Results

  • Speed: STUMP significantly outperforms vanilla topological optimization in terms of speed. For example, in the "blobs" experiment, STUMP reduced the loss by about 90% in four minutes, while vanilla methods only achieved about 25% reduction in ten minutes. Specific timings show STUMP taking 106 seconds compared to 2169 seconds for vanilla optimization on a circle dataset.
  • Robustness: Qualitative results, particularly from the random walker segmentation on the "blobs" optima, show that STUMP-generated images maintain connectivity across different thresholding parameters better than vanilla optima.
  • Loss Reduction: STUMP achieves much faster and more substantial loss reduction, especially on images with homogeneous regions or where topological features are critical.

Limitations and Future Work

  • Approximation of Integral: The smearing process involves integrating over a set of approximates, which is approximated by sampling. While efficient, this is an approximation.
  • Generalizability: While the framework is presented as general for simplicial complexes, the experiments focus on image data.
  • Future Work: The authors suggest that the methodology of smearing and STUMP can be applied to other settings, including point cloud data and more complex topological functionals. The "critical smearing" extension also opens avenues for more direct topological gradient computation.

Summary updated

Abstract

Topological statistics, in the form of persis- tence diagrams, are a class of shape descrip- tors that capture global structural informa- tion in data. The mapping from data struc- tures to persistence diagrams is almost every- where differentiable, allowing for topological gradients to be backpropagated to ordinary gradients. However, as a method for optimiz- ing a topological functional, this backprop- agation method is expensive, unstable, and produces very fragile optima. Our contribu- tion is to introduce a novel backpropagation scheme that is significantly faster, more sta- ble, and produces more robust optima. More- over, this scheme can also be used to produce a stable visualization of dots in a persistence diagram as a distribution over critical, and near-critical, simplices in the data structure.
BibTeX
@misc{bendich2023fast,
  author = {Paul Bendich and Yitzchak Solomon and Alexander Wagner},
  title = {{A Fast and Robust Method for Global Topological Functional Optimization}},
  year = {2023},
  url = {https://openreview.net/forum?id=mNG1M4ggpph},
  howpublished = {OpenReview},
}

Loading related content...

Figure