Learning Representations of Persistence Barcodes

Christoph D. Hofer, Roland Kwitt, Marc NiethammerJMLR 2019 · OpenReview

TL;DR

This paper introduces a novel method for learning task-specific representations of topological data (barcodes) using deep neural networks. By defining "structure elements" that transform barcodes into a vector space, the approach allows neural networks to leverage topological information effectively, achieving competitive performance across diverse tasks like shape recognition and graph classification.

What Problem Does This Paper Address?

Topological Data Analysis (TDA) uses tools like persistent homology to extract meaningful structural information from data, often represented as "barcodes" or "persistence diagrams." These representations are powerful but challenging to use directly with standard machine learning techniques due to their unusual "multi-set" format and computationally expensive metrics. Previous methods either relied on fixed, task-agnostic vectorizations or kernel-based approaches that can be computationally demanding. This paper addresses the gap of learning task-specific, stable, and computationally efficient representations of barcodes for deep neural networks.

Methods

The core contribution is a framework for creating learnable vectorizations of barcodes. This is achieved by:

  • Structure Elements: Defining parametrized functionals called "structure elements" that map points in a barcode (which live in a 2D space) to a real number. These functionals are designed to be zero on the diagonal of the barcode space, a crucial property for stability.
  • Transformation Pipeline: A sequence of transformations (birth-lifetime coordinate transform, rational stretch) is applied to the barcode space to simplify the construction of structure elements.
  • Induced Mapping: Each structure element defines a mapping from a barcode to a single real number. By using multiple structure elements, a barcode is transformed into a vector in $\mathbb{R}^N$, suitable for neural network input.
  • Theoretical Analysis: The paper provides theoretical guarantees on the Lipschitz continuity (a form of stability) of the induced mapping with respect to common barcode metrics (Wasserstein distances). They show that stability stronger than 1-Wasserstein is not achievable with their approach, but continuity with respect to $w_p$ for $p>1$ is.
  • Neural Network Integration: The learned vectorization is implemented as a neural network input layer, allowing for end-to-end training via backpropagation.

Datasets

The proposed method was evaluated on several benchmark datasets:

  • MPEG-7 and Animal: For 2D shape recognition.
  • Reddit-5k and Reddit-12k: For social network graph classification.
  • SHREC14: For 3D object recognition.
  • EEG signals: For activity recognition.
  • Pokec social network graph: For predicting normalized graph Laplacian eigenvalues.

No new datasets were introduced.

Key Insights and Ideas

  • Task-Specific Representations are Key: The paper strongly advocates for learning representations tailored to the specific task, drawing parallels to the success of deep learning in other domains. This contrasts with previous, more general approaches to barcode vectorization.
  • Structure Elements as Building Blocks: The concept of "structure elements" provides a flexible and theoretically grounded way to transform barcodes. Their design is crucial for ensuring stability and enabling efficient learning.
  • Stability vs. Continuity Trade-off: The theoretical analysis reveals a nuanced understanding of stability. While strong stability (e.g., $w_p$ for $p>1$) is not achievable, the method guarantees continuity, which is still highly valuable for learning.
  • Geometric Intuition for Structure Elements: The paper demonstrates how different functional forms (exponential, rational, rational hat) for structure elements impact performance and ease of optimization, highlighting the importance of practical considerations in theoretical design.

Key Results

  • Competitive Performance: The proposed method achieved competitive results across various tasks, often outperforming existing TDA-based methods and sometimes rivaling specialized approaches.
  • 2D Shape Recognition (MPEG-7/Animal): Achieved up to 74.6% accuracy (learned) on Animal, outperforming many TDA-based baselines.
  • 3D Shape Recognition (SHREC14): Achieved 72.2% accuracy (learned), outperforming several other methods.
  • Social Network Classification (Reddit-5k/12k): Achieved up to 54.8% accuracy (learned, with essential features), significantly outperforming graph kernels and other TDA methods.
  • EEG Activity Recognition: Achieved 37.4% accuracy, outperforming baselines.
  • Learning Improves Performance: Experiments consistently showed that learning the parametrization of structure elements (task-specific vectorization) leads to better performance than using fixed or randomly initialized elements.
  • Generalization: The approach demonstrated good generalization ability, with testing loss closely tracking training loss in experiments.

Limitations and Future Work

  • Choice of N (Number of Structure Elements): The paper acknowledges that determining the optimal number of structure elements ($N$) is an open problem. While empirical results show stable performance with a reasonable $N$, a more informed decision-making process is desired.
  • Filtration Learning: The authors suggest that learning the filtration function itself, especially for fixed simplicial complexes like graphs, is a promising research direction.
  • Structure Element Improvement: While current structure elements are effective, further improvements or simplifications are possible, potentially leading to even better parameter gradients and optimization.
  • Stability for $p>1$: The theoretical analysis shows that achieving stability stronger than 1-Wasserstein ($w_1$) is not possible with this framework.
  • Computational Cost: While the approach is generally efficient, some kernel-based methods (like PSS kernel) struggled with computational time on certain datasets, highlighting the advantage of the proposed method in this regard.

Summary updated

Abstract

We consider the problem of supervised learning with summary representations of topological features in data. In particular, we focus on persistent homology, the prevalent tool used in topological data analysis. As the summary representations, referred to as barcodes or persistence diagrams, come in the unusual format of multi sets, equipped with computationally expensive metrics, they can not readily be processed with conventional learning techniques. While different approaches to address this problem have been proposed, either in the context of kernel-based learning, or via carefully designed vectorization techniques, it remains an open problem how to leverage advances in representation learning via deep neural networks. Appropriately handling topological summaries as input to neural networks would address the disadvantage of previous strategies which handle this type of data in a task-agnostic manner. In particular, we propose an approach that is designed to learn a task-specific representation of barcodes. In other words, we aim to learn a representation that adapts to the learning problem while, at the same time, preserving theoretical properties (such as stability). This is done by projecting barcodes into a finite dimensional vector space using a collection of parametrized functionals, so called structure elements, for which we provide a generic construction scheme. A theoretical analysis of this approach reveals sufficient conditions to preserve stability, and also shows that different choices of structure elements lead to great differences with respect to their suitability for numerical optimization. When implemented as a neural network input layer, our approach demonstrates compelling performance on various types of problems, including graph classification and eigenvalue prediction, the classification of 2D/3D object shapes and recognizing activities from EEG signals.
BibTeX
@article{hofer2019learning,
  author = {Christoph D. Hofer and Roland Kwitt and Marc Niethammer},
  title = {{Learning Representations of Persistence Barcodes}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=rI5O37NR1eq},
}
Figure