T-ARC: Topology-Aware Randomized Clustering via Distributionally Robust Stochastic Block Models

Serena Grazia De Benedictis; Andersen Ang; Nicoletta Del Buono; Flavia Esposito; Laura Selicato

cs.LGSep 30, 2026

T-ARC: Topology-Aware Randomized Clustering via Distributionally Robust Stochastic Block Models

Authors: Serena Grazia De Benedictis, Andersen Ang, Nicoletta Del Buono, Flavia Esposito, Laura Selicato

Organizations: Department of Mathematics, University of Bari Aldo Moro, Italy

Abstract

In this work, we introduce a new clustering method, namely T-ARC (Topology-Aware Randomized Clustering), that corrects the geometric bias of K-means by embedding topological information directly into the optimization objective. Building on the assumption that the data admits an underlying hidden structure modeled via a latent graph, the idea is to uncover this information through the interplay between the standard K-means data-fidelity term and a graph-cut penalty, which discourages cluster assignments inconsistent with the connectivity structure of the data. To render this coupling tractable, the latent graph is modeled as a random realization from a Stochastic Block Model (SBM), whose scalar parameter is optimized within a Distributionally Robust Optimization (DRO) framework, yielding a closed-form proximal update. Both SBM and DRO are informed by a persistence-based similarity matrix derived from zero-dimensional persistent homology ( $H_0$ ), which translates the multiscale connectivity structure of the data into a pairwise topological prior. The overall optimization proceeds via Block Coordinate Descent; convergence is established through a global Lyapunov functional: the deterministic blocks satisfy monotonic descent, while the stochastic graph update satisfies descent in expectation, so that the expected energy converges. Experiments on synthetic datasets with non-convex geometries and on random subsets of Fashion-MNIST show that T-ARC recovers latent topological structures where K-means fails, achieving the highest accuracy on curved and interleaved clusters while remaining competitive, and markedly more stable than K-means, on real data.

Figures & tables

Figure 1 : Persistence-based similarity matrices for the five experimental settings.

Figure 2 : Two sets dataset obtained increasing isotropic Gaussian noise $\sigma$ , creating well separated sets (left), closer sets (center) and overlapping sets (right)

Figure 3 : Three-panel illustration of the two separated sets dataset obtained using $\sigma=0.05$ . Left: the original data points, colored by ground-truth labels. Center: random initialization with $k=2$ clusters. Right: final assignment obtained by T-ARC using the persistence-based similarity matrix.

Panel of Figure 4 — Figure 4 : (a) Objective function value during iterations and (b) Frobenius norm error of $\bm{C}$ , $\bm{\mu}$ , and $\bm{L}$ during iterations for T-ARC with persistence-based similarity matrix on Example 1.

Figure 5 : Three-panel illustration of the Two-Moons dataset. Left: the original data points, colored by ground-truth labels. Center: random initialization with $k=4$ clusters. Right: final assignment obtained by T-ARC using the persistence-based similarity matrix.

Panel of Figure 6 — Figure 6 : (a) Objective function value during iterations and (b) Frobenius norm error of $\bm{C}$ , $\bm{\mu}$ , and $\bm{L}$ during iterations for T-ARC with persistence-based similarity matrix on Example 2.

Figure 7 : Three-panel illustration of the Two-Spirals dataset. Left: the original data points, colored by ground-truth labels. Center: random initialization with $k=2$ clusters. Right: final assignment obtained by T-ARC using the persistence-based similarity matrix.

Panel of Figure 8 — Figure 8 : (a) Objective function value during iterations and (b) Frobenius norm error of $\bm{C}$ , $\bm{\mu}$ , and $\bm{L}$ during iterations for T-ARC with persistence-based similarity matrix on the Two-Spirals dataset.

Figure 9 : Three-panel illustration of the Two-Eights dataset. Left: the original data points, colored by ground-truth labels. Center: random initialization with $k=4$ clusters. Right: final assignment obtained by T-ARC using the persistence-based similarity matrix; the algorithm collapses the four initial clusters into two macro-clusters, each corresponding to one of the two figure-eight shapes.

Panel of Figure 10 — Figure 10 : (a) Objective function value during iterations and (b) Frobenius norm error of $\bm{C}$ , $\bm{\mu}$ , and $\bm{L}$ during iterations for T-ARC with persistence-based similarity matrix on Example 4.

Figure 11 : Three-panel illustration of the Chain-link dataset. Left: the original data points, colored by ground-truth labels. Center: random initialization with $k=4$ clusters. Right: final assignment obtained by T-ARC using the euclidean-based similarity matrix.

Panel of Figure 12 — Figure 12 : (a) Objective function value during iterations and (b) Frobenius norm error of $\bm{C}$ , $\bm{\mu}$ , and $\bm{L}$ during iterations for T-ARC with euclidean-based similarity matrix on Example 5.

Explore similar work

May 14, 2026cs.LG

ToMAToMP: Robust and Multi-Parameter Topological Clustering

Topological clustering, and its main algorithm ToMATo, is a clustering method from Topological Data Analysis (TDA) which has been applied successfully in several applications during the last few years. This is due to its high versatility, as clusters are detected from the persistent components in the sublevel sets of any user-defined function (gene expression, pixel values, etc), and efficiency, as topological clustering enjoys robustness guarantees. However, ToMATo is also limited in several ways. First, a graph on the data points needs to be provided as a hyper-parameter of the method (whose fine-tuning is left to the user). Second, ToMATo is known to be very sensitive to outlier values in the function range. Finally, and most importantly, ToMATo can only handle one function at a time, whereas it is critical to use several functions in various applications. In this article, we introduce ToMAToMP: the first topological clustering method able to handle several functions at the same time with theoretical guarantees. More specifically, we leverage a recent tool from multi-parameter persistent homology, called MMA decomposition, to design our clustering algorithm, and prove that it enjoys robustness properties. As corollaries, we show that it can be used to make ToMATo independent of graph tuning, and robust to outliers. Finally, we provide a set of numerical experiments showcasing the efficiency and quality of the clusterings produced by ToMAToMP, by showing strong improvement over non-topological and topological baselines for various datasets.

Ludo Andrianirina, Mathieu Carrière

DataShape, Centre Inria d’Université Côte d’Azur, Sophia-Antipolis, France

Clustering Persistent Homology

Ask PDF

Sep 28, 2026cs.LG

Riemannian Difference-of-Convex Optimization for K-Means Clustering

K-means is a widely adopted clustering approach in signal processing and machine learning. In this paper, we study K-means clustering through a cardinality-constrained formulation on a compact embedded submanifold. We replace the cardinality constraint with a difference-of-convex (DC) penalty and establish a global error bound to prove that the penalized and constrained formulations share the same global minimizers whenever the penalty parameter exceeds a finite threshold. To solve the resulting nonsmooth Riemannian DC problem, we reformulate it as a minimax problem and propose RADA-DC, a Riemannian alternating descent ascent method combining dual regularization with DC linearization. Under standard assumptions and suitable parameter choices, RADA-DC finds an

ε

-Riemannian critical point within

O(ε^{-3})

iterations. We conduct experiments on synthetic and real-world datasets to demonstrate that the proposed method outperforms the tested baselines, including K-means++, in solution quality at competitive computational cost when the number of clusters is large.

Meng Xu, Bo Jiang, Hanfu Zhang +2

AMSS, Chinese Academy of Sciences, and University of Chinese Academy of Sciences, Beijing, China · Ministry of Education Key Laboratory of NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing, China · Ministry of Education Key Laboratory of Mathematics and Information Networks, School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing, China +1

K-Means Nonconvex Stochastic Convex Optimization Cardinality Regularization

Ask PDF

Jul 9, 2026cs.LG

An interpretable Good--Turing restart criterion for k-means++

The k-means++ algorithm is commonly restarted multiple times to avoid poor local optima, yet the number of restarts is almost always chosen arbitrarily and applied uniformly regardless of data set difficulty. This undermines any comparison relying on such a choice and wastes computation on easy data sets while potentially under-serving hard ones. We introduce GTRC, a restart criterion combining a Good-Turing estimate, a proven unconditional bound, and a confidence-based bound on the probability that a further restart would improve on the current result, stopping once this probability falls below a user-specified tolerance

\varepsilon

. Across 36 data sets, GTRC reached clustering quality competitive with well-chosen fixed restart counts, while the number of restarts used varied considerably and appropriately with data set difficulty, governed by an interpretable, data-dependent signal rather than a fixed rule. GTRC offers a principled and reportable alternative to fixing the number of

k

-means++ restarts in advance. Software:https://github.com/RCdeAmorim/Good-Turing-Restart-Criterion.

Renato Cordeiro de Amorim

School of Computer Science and Electronic Engineering, University of Essex, Colchester, UK.

K-Means Top-K

Ask PDF