Hierarchical topological clustering

AI summary

Overview

Research area: Topological data analysis (persistent homology) applied to unsupervised machine learning, specifically cluster analysis.

Technical level: Intermediate. The paper is written in readable mathematical prose and the core algorithm relies only on the zero-dimensional homology level (H₀), but the reader needs comfort with simplicial complexes, filtrations, and distance metrics to follow the derivations and comparisons.

Scope (1 sentence): The paper introduces a hierarchical clustering algorithm built on Vietoris–Rips filtrations of point clouds that detects arbitrarily shaped clusters and persistent outliers automatically, and demonstrates it on a fragmented cell interface, a series of compressed images, Spanish 2019 trade data, and breast cancer mRNA gene expression data.

What This Paper Is About

Most clustering methods force a choice about cluster shape or require the user to guess sensitive parameters: K-means assumes convex clusters around centroids, and DBSCAN requires a density threshold ε and a minimum-points count that are hard to pick meaningfully. The authors' goal is a clustering procedure that makes no assumption about the geometry of clusters, lets the persistence of clusters and outliers be read off from the resulting hierarchy, and works with any user-selected distance function. They achieve this by tracking only the connected components (the H₀ level) of a Vietoris–Rips filtration as the distance threshold grows, while keeping records of which individual points belong to each component at every threshold value.

Key Contributions

1. A new hierarchical topological clustering (HTC) algorithm. The method constructs a grid of filtration values from the minimum to the maximum inter-point distance, builds cluster-link matrices at each level, and recursively merges linked clusters. It outputs the full hierarchy of clusters together with the list of individual elements in each cluster at each filtration value — information that persistence barcodes alone do not provide.

2. Automatic identification of persistent outliers. Points or groups of points that merge last with the dominant cluster are flagged as natural outlier candidates, both single outliers and "collective outliers" (detached islands). No blind hyperparameter tuning is needed to find them.

3. A distance-agnostic formulation. Because the algorithm only requires a distance matrix, it is demonstrated with Euclidean distance (cell fronts, trade data), Wasserstein W^{1,2} distance (images), and Fermat distance (gene expression), showing the same pipeline applies across very different data types.

4. Comparative evidence against standard baselines. The paper systematically contrasts HTC with K-means, agglomerative hierarchical clustering using the linkage with the highest cophenetic correlation coefficient, and DBSCAN on the same datasets, showing where the standard methods lose the geometric or semantic interpretation of clusters.

Main Findings

• Fragmented cell fronts. Applied to a point cloud extracted from an image of epithelial tissue representing the interface between malignant and healthy cells, HTC separates the main interface (green in the figures) from detached islands of invading malignant cells across filtration values r = 5.2, 8.8, 9.6, 11, 14.7 and 16.9. The filtration level at which each island merges with the dominant cluster indicates how deeply malignant cells have penetrated the healthy layer. K-means, hierarchical clustering with average linkage (the highest cophenetic correlation coefficient for this data), and DBSCAN with M_p = 10 and ε = 5 lose this interpretation. The persistence barcode indicates how many clusters are achievable and over what range of r.

• Image quality assessment. A series of 32 images was compared: image 1 is the original, image 32 adds a black line to the original, images 2–30 are compressed versions with k = 10 + 5q singular values kept for q = 0, 1, …, 28, and image 31 adds a black line to image 30. Using the Wasserstein W^{1,2} distance, HTC with a suitable filtration value finds 9 groups: the two images containing black lines (31 and 32) and the highly compressed images 2–6 appear as outliers, while the remaining images form a cluster of recognizable, acceptably compressed images. Hierarchical clustering with complete linkage (the highest cophenetic correlation coefficient for this dataset) places images 1, 31 and 32 in the same cluster, thereby missing the defect distinction. HTC also separates uncompressed image 32 with image 1 and compressed image 31 with the compressed set, showing that compression distortion weighs more in the distance than the added line does.

• Outliers in trade data. Using 2019 exports and imports between Spain and 43 European countries across roughly 100 product categories, with values normalized by (g − μ)/(3σ), HTC reveals a large cluster of low-interaction partners plus a small number of persistent dominant outliers. For exports, a cluster of countries receiving almost no Spanish exports forms at low r ~ 10⁻¹, containing 18 countries (Albania, Armenia, Bosnia, Georgia, Iceland, Kazakhstan, Macedonia, Moldova, Montenegro, Cyprus, Estonia, Latvia, Lithuania, Malta, Serbia, Slovenia, Luxembourg, Ukraine); at r = 3.8 this low-importer cluster contains 30 countries. France emerges as the main importer, Italy and Portugal essentially tied second, Germany third. For imports, the near-zero cluster starts with 14 countries at low r ~ 10⁻¹ (Albania, Andorra, Bosnia, Montenegro, Macedonia, Croatia, Cyprus, Georgia, Estonia, Latvia, Malta, Moldova, Serbia, Slovenia) and grows to 24 countries at r = 3.2, with Germany and France dominant, followed by Italy. Under hierarchical clustering with average linkage, Italy is the last to merge for imports — an ordering the authors describe as obscure to interpret, unlike separate connected components.

• Gene expression outliers. From the cBio Cancer Genomics Portal's Breast invasive carcinoma TGCA Pancancer Atlas dataset, containing mRNA expression for 20,531 genes across 1,082 cancer samples and 114 healthy samples, the authors normalize cancer expression using means and standard deviations from the 114 healthy samples, then restrict to M = 71 genes in the cell cycle gene/protein interaction network. Using Euclidean and Fermat distances, HTC singles out persistent outliers CCNE1, SMC1B, CDKN2A, CDC6, PKMYT1 and CDK1 — all previously linked to breast cancer prognosis or identified as anti-cancer therapeutic targets. Hierarchical clustering with weighted linkage (the highest cophenetic correlation coefficient here) produces intermediate subclusters of unclear meaning and dilutes the dominant outlier signal.

• Algorithmic complexity. The cost is at most MN², with a lower bound of order Π_{m=1}^{M} N_m², where N_m is the number of clusters at filtration value r_m. No operations are performed when the cluster-link matrix does not change, nor once a single cluster remains. The authors state the method is efficient for small and moderate datasets and note density-based algorithms may become an option as dataset size grows.

Methodology in Plain English

The starting point is a point cloud and a chosen distance function — anything from ordinary Euclidean distance to Wasserstein distance between images or a Fermat distance between gene expression profiles. The authors compute the full matrix of pairwise distances, then sweep a threshold r from the smallest inter-point distance up to the largest one (the diameter of the cloud) on a uniform grid of M steps, where M is the ratio of the diameter to the minimum distance.

At each threshold, two points within distance r are linked. Clusters are simply connected components of the resulting graph: a cluster is any group of points that can be reached from one another through a chain of links shorter than r. At r = 0 every point is its own cluster; as r grows, clusters merge; when r reaches the diameter, a single cluster remains. Crucially, the implementation does not restart from scratch at each step — it reuses the cluster-link matrix from the previous level and only performs merges when that matrix changes, walking through unvisited clusters and merging everything transitively linked to them.

This produces a hierarchy analogous to a dendrogram, but with an important extra output: for every threshold value, the algorithm records exactly which original data points belong to each cluster. Points or groups that join the dominant cluster only at very large r are isolated for a long stretch of the filtration and are therefore natural outlier candidates. The authors visualize this with persistence barcodes (as in standard persistent homology) and with maps and ordered lists showing the merge order of individual elements.

For validation, they compare against K-means, agglomerative hierarchical clustering (picking the linkage with the highest cophenetic correlation coefficient on each dataset — average, complete, or weighted depending on the case), and DBSCAN. The implementations of these baselines and of the non-Euclidean distances are gathered in the appendix; codes are implemented in Matlab and available upon reasonable request.

Why This Matters

Impact on research. The work reframes topological clustering: instead of computing persistence diagrams for many point clouds and then clustering those diagrams with standard tools, it uses the H₀ homology of the filtration directly to cluster the individual data points, while retaining point-level membership at every scale. This links persistent homology to interpretable, geometrically meaningful cluster assignments and offers a parameter-light alternative to density-based clustering.

Real-world applications (as demonstrated or proposed in the paper):

• Oncology imaging: separating the main interface between healthy and malignant cell populations from detached islands of invading cells, and quantifying penetration depth from the hierarchy level at which islands merge.
• Image quality control: automatically separating compressed from uncompressed images, and detecting images corrupted by a sudden local defect such as an added line.
• Economic and trade analysis: building a hierarchy of trading partners that isolates dominant importers/exporters (for Spain in 2019: France, Italy, Portugal, Germany) from a large mass of low-interaction countries.
• Cancer genomics and hiring/selection-style social science problems: flagging persistent outlier genes such as CCNE1 and CDK1 that merit follow-up, and, as the authors suggest, detecting the best candidates for a job.

Industry relevance. Quality monitoring pipelines in imaging, trade and market intelligence dashboards, and bioinformatics workflows for target discovery all benefit from a method that requires no arbitrary cluster count and no density threshold, and that reports outliers as a byproduct rather than as a nuisance. The authors note the algorithm suits small to moderate datasets and that density-based variants may be preferable at large scale.

Future Directions

• Scaling to large datasets. The complexity bound MN² and the N_m × N_m link matrices suggest the method is best for small and moderate point clouds; the authors explicitly suggest density-based approaches as an alternative as data size grows, leaving a scalable version as an open problem.
• Choosing and generating distances. Because results depend on the chosen metric, extending the pipeline to other Wasserstein, Fermat, or learned distances — and understanding how the hierarchy changes with the metric — is a natural next step.
• Systematic comparison against a wider benchmark suite. The paper compares against K-means, three linkage-based hierarchies, and DBSCAN on four problem settings; broader benchmarking on standard clustering datasets, and quantification of outlier-detection performance, is not reported.
• From detection to biological and economic interpretation. The gene outliers identified (CCNE1, SMC1B, CDKN2A, CDC6, PKMYT1, CDK1) are proposed as deserving specific study, and the trade hierarchies could be extended across years and country pairs to track structural change.

Target Audience

Researchers and practitioners in topological data analysis, unsupervised machine learning, and applied data science who need shape-agnostic clustering with built-in outlier detection. It is particularly relevant to specialists in medical image analysis, cancer genomics, and economic or trade statistics who want an interpretable hierarchy rather than a fixed partition. Graduate students with some background in linear algebra, metrics, and basic topology will find the algorithm portion accessible, while the comparison sections make the paper useful to methodologists evaluating clustering alternatives.

Authors’ abstract

Topological methods have the potential of exploring data clouds without making assumptions on their the structure. Here we propose a hierarchical topological clustering algorithm that can be implemented with any distance choice. The persistence of outliers and clusters of arbitrary shape is inferred from the resulting hierarchy. We demonstrate the potential of the algorithm on selected datasets in which outliers play relevant roles, consisting of images, medical and economic data. These methods can provide meaningful clusters in situations in which other techniques fail to do so.