The Mergegram of a Dendrogram and Its Stability

Yury Elkin, Vitaliy Kurlin

Abstract

This paper introduces the "mergegram," a novel topological summary for single-linkage clustering dendrograms. While 0-dimensional persistence diagrams are stable but lose structural information, and dendrograms are informative but unstable, the mergegram provides a middle ground. It captures more geometric information than standard persistence while remaining mathematically stable against noise. With near-linear computation time, the mergegram serves as an effective feature for machine learning on point cloud data.

Introduction

In Topological Data Analysis (TDA), researchers often use persistence diagrams to understand the "shape" of data across different scales. In 0-dimensional TDA, this process is equivalent to single-linkage clustering or building a Minimum Spanning Tree (MST). However, a fundamental trade-off exists between existing methods:

  1. 0D Persistence Diagrams (PD): Highly stable against noise but throw away structural information by only recording when a cluster is born and absorbed, ignoring the specific hierarchy of merges.
  2. Dendrograms and MSTs: Retain the full hierarchical structure but are notoriously unstable; tiny perturbations in data can completely alter the tree structure.

This paper introduces the mergegram (MG), an invariant that sits between these two extremes: it retains more structural information than a standard persistence diagram while preserving the noise stability required for real-world data analysis.

The Mergegram: Definition and Computation

Instead of just tracking the birth and death of a single connected component, the mergegram tracks the life intervals of merge sets. If two clusters merge at a specific scale $s$, the mergegram records a 2D point $(b, s)$, where $b$ is the scale at which the cluster was originally formed. Consequently, every arc in a clustering dendrogram contributes a point to the mergegram, preserving the memory of intermediate cluster formations.

Overview of the mergegram construction: from a point set (top) to a dendrogram (left) and the resulting topological summaries (right).

To formalize this, the authors define a "merge module" (a type of persistence module) and prove it decomposes into interval modules, allowing it to be represented as a 2D diagram.

Formalization of the merge module through partitions and maps across scales.

The computation of the mergegram is efficient, working by first computing the Minimum Spanning Tree (MST) of the point cloud, sorting the edges by length, and using a Union-Find data structure to track component merges. This results in a near-linear time complexity of $O(n \log n \alpha(n))$.

Key Theoretical Insights

  • Informational Strength: The mergegram is strictly more informative than the standard 0D persistence diagram. The authors demonstrate that different point clouds can yield identical 0D persistence diagrams but distinct mergegrams.
  • Provable Stability: A core contribution is Theorem 7.4, which establishes that the mergegram is stable. Small perturbations in the initial point cloud (measured in Hausdorff distance) result in proportionally small changes in the mergegram (measured in bottleneck distance).

Empirical Results

The authors evaluated the mergegram on synthetic datasets designed for isometry classification (recognizing shapes regardless of rotation or translation). Using 10 classes of 100-point clouds across various dimensions ($m = 2, 3, 4, 5$), they tested robustness by adding random rotations, uniform shifts (noise), and outliers.

When fed into PersLay (a neural network layer for topological diagrams), the mergegram consistently outperformed standard 0D persistence diagrams and raw point clouds. For instance, in 2D datasets with high noise, the mergegram maintained approximately 60% classification accuracy, while standard 0D persistence dropped to 50%.

Conclusion and Future Work

The mergegram successfully bridges the gap between the stability of persistence diagrams and the richness of dendrograms. While currently focused on 0-dimensional features, future work aims to combine mergegrams with 1D persistence (tracking loops and holes) to classify rigid shapes in real-world computer vision tasks, such as data skeletonization.

Summary updated

Abstract

This paper extends the key concept of persistence within Topological Data Analysis (TDA) in a new direction. TDA quantifies topological shapes hidden in unorganized data such as clouds of unordered points. In the 0-dimensional case the distance-based persistence is determined by a single-linkage (SL) clustering of a finite set in a metric space. Equivalently, the 0D persistence captures only edge-lengths of a Minimum Spanning Tree (MST). Both SL dendrogram and MST are unstable under perturbations of points. We define the new stable-under-noise mergegram, which outperforms previous isometry invariants on a classification of point clouds by PersLay.
BibTeX
@inproceedings{elkin2020mergegram,
  author = {Yury Elkin and Vitaliy Kurlin},
  title = {{The Mergegram of a Dendrogram and Its Stability}},
  booktitle = {MFCS},
  year = {2020},
  url = {https://openreview.net/forum?id=vSgI9xpZaB},
}
Figure