Persistence Bag-of-Words for Topological Data Analysis

Bartosz Zielinski, Michal Lipinski, Mateusz Juda, Matthias Zeppelzauer, Pawel Dlotko

Abstract

Persistence Bag-of-Words (PBoW) bridges the gap between Topological Data Analysis (TDA) and machine learning by transforming complex, variable-sized persistence diagrams into fixed-length feature vectors. By using an adaptive clustering approach rather than a rigid grid, PBoW achieves state-of-the-art accuracy while being orders of magnitude faster and more computationally efficient than existing kernel-based or vectorized methods. This representation is spatially adaptive, stable, and enables TDA to be applied to large-scale datasets previously considered computationally prohibitive.

1. Introduction

Topological Data Analysis (TDA) is a powerful tool for capturing the "shape" of data, often summarized via Persistent Homology (PH). The output of PH is a Persistence Diagram (PD)—essentially a multiset of points representing the birth and death of topological features such as holes or voids.

While PDs are robust descriptors, they are notoriously difficult to use in standard machine learning pipelines because each diagram can have a different number of points. Previous research addressed this using kernels, which are computationally expensive ($O(n^2)$ complexity relative to the number of samples), or fixed-grid vectorizations like Persistence Images. However, because PDs are often sparse and unevenly populated, fixed grids can be imprecise or waste memory on empty space. The authors propose PBoW to create a representation that is spatially adaptive, stable, and computationally efficient.

2. Methodology

The Persistence Bag-of-Words (PBoW) approach adapts the classic "Bag-of-Words" model from computer vision and natural language processing to the topological domain.

The PBoW pipeline: from training data to consolidated diagrams, codebook generation, and final codeword histograms.

2.1 Codebook Generation and Quantization

The process begins by consolidating PDs from the training set. Clustering algorithms, such as k-means or Gaussian Mixture Models (GMM), are applied to find "codewords"—representative points in the birth-persistence plane. This creates an adaptive "vocabulary" of topological features. Each individual PD is then converted into a histogram (quantization) where each point in the PD is assigned to the nearest codeword (hard assignment) or distributed among them (soft assignment).

2.2 Stability and Weighting (sPBoW)

To ensure the method is stable—meaning small changes in input data do not cause large fluctuations in the output vector—the authors introduce Stable PBoW (sPBoW). This version utilizes soft assignment via GMM likelihoods and a persistence weighting function. The weighting function prioritizes points with higher persistence (longer-lived features), effectively filtering out topological noise. The paper includes a theoretical proof showing that sPBoW is stable with respect to the 1-Wasserstein distance.

3. Experimental Results

The authors evaluated PBoW and sPBoW on a diverse set of benchmarks, including synthetic shapes, material recognition (GeoMat), social network graphs (Reddit-5K/12K), and high-resolution 3D reconstructions (PetroSurf3D).

Comparative performance of PBoW and sPBoW against state-of-the-art methods across multiple datasets, highlighting accuracy (Score) and computational efficiency (Time).

3.1 Accuracy and Efficiency

PBoW matched or outperformed state-of-the-art methods, such as Persistence Images (PI) and Sliced Wasserstein Kernels, across nearly all datasets. A key advantage is the massive runtime improvement. For example, on the PetroSurf3D dataset (EXP-B), PBoW required approximately 28.5 seconds to construct representations, while the popular Persistence Image (PI) method took over 12,137 seconds (more than 3 hours). Furthermore, high performance was achieved with very small codebooks (often 20 to 50 codewords), resulting in compact, low-dimensional feature vectors.

4. Conclusion and Future Work

PBoW demonstrates that adaptive bins are superior to fixed grids for sparse topological data. By moving "bins" to where the data lives, it captures fine-grained spatial differences that fixed resolutions might blur. While the codebook size remains a hyperparameter to be tuned, the extreme efficiency of PBoW enables TDA to be integrated into deep learning architectures as a standard layer for large-scale data analysis.

Summary updated

BibTeX
@inproceedings{zielinski2019persistence,
  author = {Bartosz Zielinski and Michal Lipinski and Mateusz Juda and Matthias Zeppelzauer and Pawel Dlotko},
  title = {{Persistence Bag-of-Words for Topological Data Analysis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/624},
}
Figure