🤖 machine learning

Topology-Driven Clustering: Enhancing Performance with Betti Number Filtration

This paper introduces BFTC, a novel topological clustering algorithm that leverages multiscale Betti sequences derived from local Vietoris-Rips filtrations to construct topology-aware similarity structures, thereby effectively clustering complex, nonconvex, and intertwined data structures while outperforming existing state-of-the-art methods.

Original authors: Arghya Pratihar, Kushal Bose, Swagatam Das

Published 2026-07-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Arghya Pratihar, Kushal Bose, Swagatam Das

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Shape of Things to Come

Imagine you are trying to sort a giant pile of mixed-up toys. Some are red blocks, some are blue balls, and some are green snakes. If you just look at how close they are to each other on the floor, you might group the red blocks with the blue balls simply because they happened to land next to each other. This is how many traditional computer programs try to sort data: they measure the straight-line distance between points. But what if the "snakes" are actually long, winding loops that wrap around the "balls"? Distance alone can't tell you that the snake is a single, connected shape; it just sees a bunch of scattered points.

To solve this, scientists use a field called Topological Data Analysis (TDA). Think of TDA as a way to look at data not just as a scatter of dots, but as a landscape with hills, valleys, and tunnels. A key tool in this field is "persistent homology," which acts like a camera that takes photos of the data at different zoom levels. As you zoom out, you can see which features (like a hole in a donut or a loop in a snake) stay visible and which ones are just random noise. Another key concept is the "Betti number," which is simply a count of these features: how many separate islands are there? How many tunnels? How many hollow bubbles? By counting these shapes, computers can understand the true structure of the data, even when it's twisted, tangled, or non-convex (meaning it doesn't look like a simple ball or box).

The Paper's Big Idea: BFTC

In this paper, the authors introduce a new method called Betti Number Filtration-based Topological Clustering, or BFTC for short. They argue that while previous methods tried to use these topological ideas, they often missed the mark by looking at the whole dataset at once or only counting the simplest features (like just counting islands). BFTC suggests a smarter approach: look at the data locally, like a detective examining a specific neighborhood, and count the complex shapes at every scale.

Here is how the magic happens, step-by-step:

The Neighborhood Watch: First, the algorithm picks a point and looks at its immediate neighbors (either the closest $k$ friends or everyone within a certain radius).
The Zoom Lens (Filtration): Instead of just looking at that neighborhood once, BFTC creates a "filtration." Imagine slowly inflating a balloon around your neighborhood. As the balloon grows, it connects points that were far apart. At every stage of this inflation, the algorithm builds a temporary shape (called a Vietoris–Rips complex) and counts the holes and loops.
The Topological Fingerprint: As the balloon inflates from small to large, the number of holes changes. A small balloon might see 10 separate islands. A medium one might see them merge into 2 islands with 1 tunnel. A big one might see everything become 1 giant island. This sequence of numbers is called a Betti sequence. It's like a unique fingerprint for that specific neighborhood, describing how its shape evolves.
Matching Fingerprints: The algorithm then compares the Betti sequences of neighboring points. If two points have similar sequences (meaning their neighborhoods evolve in the same way as you zoom out), they are considered "topologically similar," even if they aren't physically closest.
Cleaning Up: The algorithm uses these similarities to clean up the map. It removes "outliers" or neighbors that don't fit the topological pattern, creating a cleaner, more accurate map of the data's true structure.
The Final Sort: Finally, it uses a standard math technique (spectral clustering) on this new, topology-aware map to group the data into clusters.

What They Found

The authors tested BFTC on a variety of tricky datasets, including synthetic ones designed to fool other algorithms. These included:

Linked Tori: Two donuts (tori) that are interlocked like a chain.
Twisted Shapes: Data that forms spirals, circles, and spheres mixed together.
Real-World Data: Datasets like the "Zoo" (classifying animals), "Ecoli" (bacteria), and "MNIST" (handwritten digits).

The results were quite promising. In the simulations, BFTC consistently outperformed other state-of-the-art methods, including older topological approaches like ToMATo, TPCC, and TKM. For example, on the "Linked Tori" dataset (where two donuts are tangled), BFTC achieved near-perfect scores (ARI of 1.00 and NMI of 1.00), while other methods struggled to separate the two interlocked shapes. Even when the researchers added noise (random static) to the data, BFTC remained robust, suggesting it can handle messy, real-world information well.

The paper also explored how different settings affect the results. They found that using cosine similarity (comparing the direction of the Betti sequences rather than just their size) worked better than standard distance measures. They also discovered that the "neighborhood" size matters: if the neighborhood is too small, it misses the big picture; if it's too big, it connects unrelated shapes. However, by tuning these settings, BFTC successfully identified complex structures that other algorithms missed.

What It Doesn't Do (Yet)

It is important to note what the paper does not claim. The authors do not say this method is a magic bullet for every problem. They explicitly point out that their method relies on computing Betti numbers, which can get computationally expensive if you try to count very high-dimensional holes (like 4D or 5D holes) in massive datasets. They suggest that for very high dimensions, it's best to stick to lower dimensions (like 0, 1, or 2) where the math is manageable.

Furthermore, while the paper proves mathematically that the algorithm is stable (meaning small changes in the data don't cause the results to crash and burn), these are theoretical proofs based on assumptions. The actual "wins" shown in the paper are based on simulations and experiments on specific datasets, not on a universal guarantee for all possible data in the universe. The authors suggest that future work could focus on making the method faster for huge-scale datasets and exploring how to automatically choose the best settings without human help.

In short, BFTC suggests that by listening to the "shape" of the data through its evolving holes and loops, we can sort complex, tangled information much better than by just measuring how close points are to each other.

Technical Summary: Betti Number Filtration-based Topological Clustering (BFTC)

1. Problem Statement

Traditional clustering algorithms (e.g., k-Means, DBSCAN, Spectral Clustering) rely heavily on Euclidean or kernel-based similarity measures. While effective for many applications, these methods often struggle with datasets exhibiting complex geometric structures, such as nonconvex shapes, multiple scales, or intertwined manifolds. They frequently fail to capture intrinsic topological features like loops, voids, and higher-dimensional connectivity.

Existing Topological Data Analysis (TDA) approaches attempt to bridge this gap but face specific limitations:

ToMATo: Relies on 0-dimensional homology (connected components) and density landscapes, limiting its ability to incorporate higher-dimensional topological information.
TPCC: Uses simplicial complexes and Hodge Laplacians but may struggle to distinguish regions where topological features emerge at different filtration scales.
Topological k-Means (TKM): Embeds persistence diagrams into Reproducing Kernel Hilbert Spaces (RKHS) but focuses on global topological summaries rather than localized, multiscale topology.

The core challenge addressed by this work is the need for a clustering algorithm that can simultaneously capture local geometric proximity and higher-dimensional topological structures in a multiscale manner without relying solely on global persistence summaries or fixed topological scales.

2. Methodology: BFTC Algorithm

The proposed method, Betti Number Filtration-based Topological Clustering (BFTC), constructs a topology-aware similarity structure through the following steps:

A. Neighborhood Graph Construction

The algorithm begins by constructing a local neighborhood graph for the dataset $X$ . It supports two variants:

k-NN BFTC: Uses a k-nearest-neighbor graph to ensure uniform cardinality and controlled sparsity.
$\epsilon$ -BFTC: Uses an $\epsilon$ -neighborhood graph based on a fixed geometric radius, aligning naturally with metric-threshold constructions.

B. Local Vietoris-Rips Filtration and Betti Sequences

For each data point $x_i$ , the algorithm constructs a series of nested Vietoris-Rips (VR) complexes over its local neighborhood $N(x_i) \cup \{x_i\}$ .

A filtration scale is defined by a sequence of thresholds $\epsilon_1, \epsilon_2, \dots, \epsilon_L$ .
For each scale, the VR complex $VR(x_i, \epsilon_l)$ is formed.
Betti Numbers: The algorithm computes Betti numbers $\beta_m$ up to a user-specified maximum dimension $M$ (where $M$ reflects intrinsic topological complexity, not necessarily the ambient feature dimension).
Betti Sequences: For each dimension $m \in [0, M]$ , the sequence of Betti numbers across the filtration scales forms a Betti sequence $\beta^{(i)}_m = (\beta^{(i)}_{1m}, \dots, \beta^{(i)}_{Lm})$ . These sequences serve as multiscale topological signatures of the local neighborhood.

C. Topology-Aware Similarity and Graph Refinement

The algorithm quantifies the topological similarity between neighboring points by comparing their Betti sequences.

Similarity Metric: Cosine similarity is computed between the Betti sequences of adjacent points $x_i$ and $x_j$ for each dimension $m$ :
$(d_{ij})_m = \frac{\langle \beta^{(i)}_m, \beta^{(j)}_m \rangle}{\|\beta^{(i)}_m\| \|\beta^{(j)}_m\|}$
Outlier Removal: A set of thresholds $\alpha_0, \dots, \alpha_M$ is applied. A neighbor $x_j$ is retained in the refined neighborhood $N'(x_i)$ only if $(d_{ij})_m \geq \alpha_m$ for all dimensions $m$ . This step eliminates topologically dissimilar neighbors and outliers, resulting in a sparser, more informative graph.

D. Spectral Clustering

A symmetric weighted adjacency matrix $A'$ is constructed from the refined graph using a Gaussian kernel. The Laplacian matrix $L' = D' - A'$ is computed, and spectral clustering (via k-Means on the eigenvectors of the smallest $p$ eigenvalues) is applied to obtain the final clusters.

3. Key Contributions

The paper outlines three primary contributions:

Novel Algorithm (BFTC): An efficient clustering algorithm that constructs Vietoris-Rips complexes over local neighborhoods and evaluates Betti numbers up to a prescribed dimension. It utilizes Betti sequences to measure topological similarity, moving beyond simple connectivity ( $\beta_0$ ) to capture higher-dimensional features.
Effectiveness on Complex Structures: The method is specifically designed to handle datasets with complex, intertwined shapes and structures by harnessing underlying topological characteristics across multiple scales.
Theoretical Analysis: The paper provides extensive theoretical underpinnings regarding the convergence and stability of BFTC. It establishes that under reasonable geometric and spectral separation conditions, the algorithm is structurally stable; small perturbations in the input data do not alter the resulting clustering (up to label permutation).

4. Experimental Results

The authors evaluated BFTC (both k-NN and $\epsilon$ variants) against state-of-the-art baselines (k-Means, Spectral, DBSCAN, ToMATo, TPCC, TKM, etc.) on synthetic and real-world datasets.

Synthetic Datasets: On datasets with nonconvex and intertwined structures (e.g., Linked Tori, 3MC, Smile1, Torus Sphere Line), BFTC consistently achieved superior Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI) scores. For instance, on the Linked Tori dataset with noise ( $\rho=0.3$ ), k-NN BFTC achieved an ARI of 0.49 and NMI of 0.56, significantly outperforming competitors like DBSCAN (0.01 ARI) and ToMATo (0.17 ARI).
Real-World Datasets: Experiments on UCI datasets (Zoo, Ecoli, Wisconsin B.C., Glass, ORHD, MNIST, Phishing URL) demonstrated that BFTC outperformed almost all contenders.
Robustness: The method showed stability against Gaussian noise perturbations.
Ablation Studies:
- Neighborhood Construction: Both k-NN and $\epsilon$ -neighborhoods proved effective, though k-NN offered smoother spectral behavior for highly intertwined manifolds.
- Distance Metrics: Cosine similarity between Betti sequences was found to be significantly more effective than Euclidean distance for capturing topological relationships.
- Kernel Functions: The inclusion of a Gaussian kernel in the adjacency matrix improved performance compared to unweighted graphs.

5. Significance and Claims

The paper claims that BFTC represents a significant advancement by integrating multiscale topological information directly into the clustering process. Unlike previous methods that rely on global persistence summaries or fixed scales, BFTC captures localized multiscale topology through Betti sequences.

The authors assert that this approach allows the algorithm to:

Distinguish regions of a manifold where topological features emerge at different filtration scales.
Simultaneously capture geometric proximity and higher-dimensional topological structures (loops, voids).
Provide a robust solution for datasets with complex, nonconvex, and intertwined structures where traditional Euclidean-based methods fail.

The theoretical analysis further supports the empirical results, claiming that BFTC is not only computationally finite but also structurally stable, ensuring that the clustering pipeline is locally invariant to small perturbations in the input data. The work concludes that exploring topological aspects for large-scale datasets with complex overlapping structures remains a promising direction for future research.