Hierarchical topological clustering

This paper proposes a hierarchical topological clustering algorithm that can be applied with any distance metric to identify clusters of arbitrary shapes and persistent outliers across diverse datasets, including images, medical, and economic data.

The Gist

The "Social Network of Shapes": Understanding Hierarchical Topological Clustering

Imagine you are looking at a massive, messy crowd of people in a city square. Some people are standing in tight-knit families, some are walking in small groups of friends, and a few are lone wanderers standing far away from everyone else.

If you wanted to organize this crowd into groups, how would you do it?

• Do you group them by how many people are in a circle?
• Do you group them by how close they are standing?
• What do you do with the lone wanderer? Are they just "noise" to be ignored, or are they important individuals we should study?

This paper introduces a new way to solve this problem, called Hierarchical Topological Clustering (HTC).

---

The Core Idea: The "Expanding Bubble" Method

Most traditional clustering methods are like a rigid manager. They might say, "Everyone must belong to one of exactly five groups," or "If you aren't in a dense crowd, you don't count." This often fails when groups have weird, curvy shapes (like a long snake of people) or when the "loners" are actually the most interesting people in the room.

The authors' new method works differently. Instead of forcing people into boxes, imagine every single person in that crowd starts blowing a bubble around themselves.

1. The Tiny Bubble Stage: At first, the bubbles are tiny. Everyone is in their own "cluster" of one.
2. The Growing Bubble Stage: As the bubbles grow larger, they start to touch. When two bubbles touch, those two people (and their groups) merge into one larger group.
3. The Big Merge: Eventually, the bubbles get so big that they all touch, and the entire crowd becomes one single, giant group.

The "Magic" of this approach: By watching when these bubbles touch, we can learn the "topology" (the shape and structure) of the crowd.

• The "Mainstream" Groups: If a group of people merges very quickly, they were already standing close together. They are a stable, dense community.
• The "Outliers" (The Interesting Loners): If a person’s bubble has to grow massive before it finally touches anyone else, that person is an outlier. In many datasets, these aren't just "errors"—they are the most important pieces of information!

---

Real-World Applications: Why does this matter?

The researchers tested this "bubble" method on three very different "crowds":

1. The Medical Detective (Cancer Cells)

Imagine a battlefield where healthy cells are fighting off invading cancer cells. The cancer cells don't just form one neat circle; they spread out in "islands" and "fingers" into the healthy territory.

• Old methods often got confused by the weird shapes and couldn't tell the difference between the main battle line and the small, dangerous "scout" groups of cancer cells.
• HTC easily identified the main boundary and, more importantly, spotted the "islands" of cancer cells that had broken away. These are the "outliers" that doctors need to watch most closely.

2. The Quality Control Inspector (Digital Images)

Think of a photo being compressed (like a low-quality JPEG). As you compress it more, it gets blurrier.

• HTC can look at a collection of images and automatically say: "These 20 images are high quality; these 5 are a bit blurry; and these 2 are totally broken because someone accidentally drew a black line across them." It treats the "broken" images as outliers, helping computers automatically spot defects.

3. The Economic Trendspotter (Global Trade)

Imagine looking at all the countries in Europe and how much they trade with Spain.

• Most countries trade in similar amounts, forming a "main crowd."
• But some countries—like France or Germany—are "super-traders." In the HTC model, their "bubbles" stay separate for a very long time because they are so much bigger and more significant than the others. HTC identifies these "power players" as the most important outliers in the economy.

---

Summary: The Big Takeaway

Traditional clustering is like trying to fit different-sized objects into standard square boxes. Hierarchical Topological Clustering is more like watching how things naturally connect as they grow.

By focusing on the shape of the data and the timing of how groups merge, this method doesn't just tell you what the "average" looks like—it tells you where the weird, the rare, and the most important pieces of the puzzle are hiding.

Technical Summary

Technical Summary: Hierarchical Topological Clustering (HTC)

Authors: Ana Carpio and Gema Duro
Date: January 6, 2026 (Preprint)

---

1. Problem Statement

Traditional clustering algorithms often struggle with datasets characterized by non-convex geometries, varying densities, or the presence of meaningful outliers.

• Partition-based methods (e.g., K-means, K-medoids) assume spherical/convex cluster shapes and fail when clusters are elongated or irregular.
• Hierarchical methods (agglomerative) can be sensitive to arbitrary linkage choices and may produce suboptimal solutions.
• Density-based methods (e.g., DBSCAN) can identify arbitrary shapes but require the non-trivial selection of hyperparameters ($\epsilon$ and $MinPts$), which can lead to "blind" parameter tuning.
• The Outlier Dilemma: Most algorithms treat outliers as noise to be discarded, whereas in many fields (medicine, economics, biology), outliers represent critical, meaningful phenomena (e.g., rare disease markers or economic anomalies).

2. Methodology

The authors propose Hierarchical Topological Clustering (HTC), an algorithm rooted in Topological Data Analysis (TDA), specifically utilizing $H_0$ persistent homology.

Key Algorithmic Steps:

1. Metric Selection: The user chooses any distance metric $d$ (Euclidean, Wasserstein, Fermat, etc.) to define the similarity between points.
2. Filtration Construction: The algorithm constructs a Vietoris-Rips filtration. This involves a nested sequence of simplicial complexes where edges are added between points as a scale parameter $r$ increases from $0$ to the diameter of the point cloud.
3. Topological Tracking: Instead of just calculating a persistence diagram (which shows that features exist), the HTC algorithm tracks which specific elements belong to which connected components (clusters) at every scale $r$.
4. Hierarchy Generation: As $r$ grows, clusters merge. The algorithm outputs a complete hierarchy (dendrogram) and a list of elements for each cluster at every filtration step.
5. Complexity: The algorithm has a complexity of at most $MN^2$, making it efficient for small to moderate datasets.

3. Key Contributions

• Shape Agnosticism: Unlike K-means, HTC identifies clusters of arbitrary geometry because it relies on connectivity rather than distance to a centroid.
• Automatic Outlier Identification: Outliers are not "noise" to be filtered; they are identified as points or groups that persist as isolated components for a long range of the filtration parameter $r$.
• Parameter Robustness: By providing a full hierarchy (via a persistence barcode), the algorithm allows researchers to observe how clusters evolve, reducing the need for "blind" threshold selection.
• Integration of TDA with Clustering: It bridges the gap between persistent homology (which identifies topological features) and traditional clustering (which assigns data points to groups).

4. Results and Applications

The authors validated the HTC algorithm across four diverse domains:

• Biological Geometry (Cellular Interfaces): In a dataset representing the interface between healthy and malignant cells, HTC successfully distinguished the main interface from "detached islands" of cancer cells. Standard methods like K-means and DBSCAN failed to capture this geometric meaning.
• Image Processing (Quality Control): Using Wasserstein distance, HTC was applied to a series of compressed images. It successfully separated images with "line defects" and highly compressed images from the original/high-quality images, whereas standard hierarchical clustering grouped them incorrectly.
• Economics (International Trade): Using normalized trade data, HTC identified "dominant partners" (major importers/exporters) as persistent outliers and categorized countries with low interaction levels into distinct clusters.
• Genomics (Cancer Research): Using Fermat distance on mRNA expression data, HTC identified specific genes (e.g., CCNE1, CDKN2A) as persistent outliers. These genes were subsequently confirmed to be clinically relevant to breast cancer prognosis.

5. Significance

The HTC algorithm provides a mathematically rigorous framework for discovering structure in complex data. Its primary significance lies in its ability to preserve the identity of outliers and respect the natural shape of data. By transforming the clustering problem into a study of topological persistence, it offers a more intuitive and automated way to interpret data where the "exceptions" (outliers) are just as important as the "rules" (clusters).