ATOL: Automatic Topologically-Oriented Learning

Martin Royer, Frédéric Chazal, Yuichi Ike, Yuhei UmedaarXiv 2019 · OpenReview

Abstract

ATOL (Automatic Topologically-Oriented Learning) is a fast, unsupervised method that transforms complex topological signatures into simple vectors for machine learning. By using optimal quantization and adaptive "sensors," it achieves state-of-the-art performance on graph classification benchmarks while remaining computationally efficient and easy to use.

Introduction

Topological Data Analysis (TDA) is a powerful tool for capturing the "shape" of data—identifying features like loops, voids, and connected components that standard methods might miss. The standard output of TDA is a persistence diagram: a collection of points in a 2D plane representing the birth and death of these topological features.

A persistence diagram representing topological features of a shape.

However, persistence diagrams are notoriously difficult to use in machine learning. They are unordered sets of points with varying cardinalities, whereas most ML algorithms (like Random Forests or Neural Networks) expect fixed-length vectors. Previous solutions to this "vectorization" problem often involved complex kernels that scale poorly or deep learning layers that require heavy supervision and tuning. The authors of ATOL sought a method that is fast, unsupervised, and theoretically sound.

Methods

The ATOL framework treats persistence diagrams as measures and vectorizes them in three main steps:

  1. Quantization: The algorithm takes a sample of diagrams from the training set and uses an adaptation of Lloyd’s algorithm ($k$-means) to find a "codebook" of $b$ representative points. These points represent the "average" locations where topological features tend to appear in the diagram space.
  2. Contrast Functions: For each point in the codebook, ATOL defines a "sensor" (a contrast function). These functions (typically Laplacian or Gaussian) are centered at the codebook points. Crucially, the bandwidth (scale) of each sensor is set adaptively based on the distance to its nearest neighbor in the codebook, ensuring the sensors cover the space effectively without too much overlap.
  3. Vectorization: To vectorize a new diagram, the algorithm sums the "activations" of all its points across these $b$ sensors. The result is a fixed-length vector of size $b$, which can be plugged directly into any standard ML pipeline.
Visual overview of the topological filtration process leading to a persistence diagram.

This approach is entirely unsupervised and data-dependent, meaning it learns the most relevant regions of the topological space for a specific dataset without needing labels during the vectorization phase.

Key Results and Insights

The authors evaluated ATOL across several domains, including social networks (REDDIT, COLLAB), bio/chemoinformatics (MUTAG, PROTEINS), and synthetic dynamics (ORBIT5K).

  • State-of-the-Art Performance: ATOL achieved impressive results, particularly on large social network graphs. On REDDIT-5K, it reached 67.1% accuracy, a significant jump over the previous best of ~59.5%. On COLLAB, it achieved 88.3% accuracy.
  • Scalability: Unlike kernel-based methods, ATOL’s complexity is linear with respect to the number of diagrams and features. For a dataset of 5,000 observations, calibration and vectorization take less than 5 seconds on a standard laptop.
  • Theoretical Soundness: ATOL is the first measure vectorization method proven to be able to separate clusters of persistence diagrams under certain margin conditions.

Conclusion

ATOL bridges the gap between topology and machine learning by providing a simple, scalable, and theoretically grounded vectorization method. While its unsupervised nature might overlook rare discriminative features, its efficiency and performance on large-scale benchmarks make it a significant advancement in the field of TDA.

Summary updated

Abstract

Robust topological information commonly comes in the form of a set of persistence diagrams, finite measures that are in nature uneasy to affix to generic machine learning frameworks. We introduce a fast, learnt, unsupervised vectorization method for measures in Euclidean spaces and use it for reflecting underlying changes in topological behaviour in machine learning contexts. The algorithm is simple and efficiently discriminates important space regions where meaningful differences to the mean measure arise. It is proven to be able to separate clusters of persistence diagrams. We showcase the strength and robustness of our approach on a number of applications, from emulous and modern graph collections where the method reaches state-of-the-art performance to a geometric synthetic dynamical orbits problem. The proposed methodology comes with a single high level tuning parameter: the total measure encoding budget. We provide a completely open access software.
BibTeX
@misc{royer2019atol,
  author = {Martin Royer and Frédéric Chazal and Yuichi Ike and Yuhei Umeda},
  title = {{ATOL: Automatic Topologically-Oriented Learning}},
  year = {2019},
  eprint = {1909.13472},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.13472},
}
Figure