Source-linked AI summary
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
TL;DR
K-means’ geometric assumptions limit its ability to recover curved, elongated, and interconnected clusters. T-ARC combines its data-fidelity objective with a graph-cut penalty over a learned latent graph, using a persistent-homology prior. It recovers structures missed by K-means on synthetic examples and is competitive on Fashion-MNIST, with greater stability than K-means.
Problem
Method
T-ARC couples K-means data fidelity with a graph-cut penalty over a latent graph, using a zero-dimensional persistent-homology similarity matrix as a structural prior.
Source: §1 · p. 2Results
T-ARC recovers topological structures missed by K-means on Two-Moons and Two-Spirals, and on Fashion-MNIST is more stable than K-means while Spherical K-means has the strongest label agreement.
Source: §7 · pp. 16–17Takeaways & Limitations
The persistence-based similarity matrix matches or outperforms its Euclidean counterpart when topological structure dominates geometry, while the Euclidean variant is more robust for overlapping or intersecting clusters.
Source: §7 · p. 17The stochastic graph-parameter update is guaranteed to decrease energy in expectation, not monotonically along every update path.
Source: §4 · p. 7
Abstract
from arXiv · showhide
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.
1 Introduction
T-ARC addresses K-means’ difficulty with elongated, curved, or interleaved clusters by incorporating graph connectivity into its objective. It jointly models a latent graph and cluster assignments, uses persistent-homology information as a structural prior, and establishes convergence in expectation.
1 Introduction
- T-ARC combines K-means data fidelity with a graph-cut penalty so cluster assignments can respect latent connectivity rather than only geometric arrangement.The graph-cut term is intended to correct K-means’ bias toward convex, roughly spherical clusters.Source: §1 · p. 2
- The method treats the latent graph as a random variable and jointly optimizes its distribution and cluster assignments under a distributionally robust criterion.Modeling the graph through an SBM and optimizing its parameters with DRO yields closed-form updates via a proximal point method.Source: §1 · pp. 2–3
- A zero-dimensional persistent-homology similarity matrix supplies a multiscale connectivity prior for both SBM edge probabilities and the DRO ambiguity set.The matrix feeds this structural information through the graph-cut term into the clustering objective.Source: §1 · pp. 2–3
- Each block update decreases the global Lyapunov functional in expectation, whose expected value converges under the proposed block coordinate descent.The blocks update cluster assignments, centroids, and graph parameters.Source: §1 · p. 2
- The paper validates T-ARC on synthetic datasets with complex geometric and topological structure and random Fashion-MNIST subsets, comparing it with established baselines.The introduction states the evaluation scope but does not report detailed benchmark outcomes here.Source: §1 · p. 3
2 Mathematical Problem Formulation
The formulation augments geometric K-means with a graph-cut term over a latent graph, balancing compactness in feature space against connectivity in the graph. The graph itself is treated as a variable to be discovered alongside the clustering.
2 Mathematical Problem Formulation
- K-means relies on geometric distances and can miss elongated, curved, or interconnected clusters because it does not capture global connectivity.The formulation identifies this limitation as motivation for adding a topological perspective.Source: §2 · p. 3
- The latent structure is represented by an undirected, unweighted graph whose nodes are data points and whose edges encode adjacency or similarity; the graph is optimized with the clustering.The graph is chosen from possible configurations on the data points to support the clustering objective.Source: §2 · p. 3
- The graph-cut term penalizes assignments that cross graph connectivity, while the K-means term preserves feature-space compactness and guards against fragmented partitions.Their balance sets a trade-off between topological coherence and geometric fidelity.Source: §2 · pp. 3–4
3 Optimization Strategy
The optimization uses block coordinate descent because the full problem is jointly non-convex but block-wise convex. It combines NNLS updates for cluster assignments and centroids with a stochastic SBM graph update optimized under distributional uncertainty.
3 Optimization Strategy
- Although jointly non-convex, the objective is block-wise convex, motivating sequential block coordinate descent updates.The graph-cut term is convex in C, while the K-means term is block-convex in C and µ separately.Source: §3 · p. 4
3.1 Update of C and µ
- For fixed µ and L, C is updated by projected gradient for a regularized NNLS problem; with C fixed, µ is also updated by projected-gradient NNLS.Both updates use nonnegative-orthant projection and prescribed stopping rules.Source: §3.1 · p. 4
3.2 Update of L
- Searching all graph Laplacians is computationally infeasible, so the graph update restricts the latent graph to a similarity-modulated stochastic block model.The edge probability depends on whether two nodes are in the same cluster and on their similarity S_ij.Source: §3.2 · p. 5
- DRO restricts plausible SBM edge-probability matrices to those near S, reducing the worst-case graph objective to a scalar parameter optimized with a proximal update.The proximal term prevents the linear objective from forcing a degenerate boundary solution and keeps updates within the admissible interval.Source: §3.2 · pp. 5–6
4 Convergence Analysis
The analysis uses a global Lyapunov functional to track data fit and graph regularization across block updates. Deterministic blocks descend monotonically, while the stochastic graph update descends in expectation, yielding convergence of expected energy and vanishing successive block differences.
4 Convergence Analysis
- The Lyapunov functional combines data fidelity with graph Dirichlet energy, the Laplacian contribution to cluster-assignment smoothness.The functional is bounded below, so the algorithm's energy sequence cannot diverge to negative infinity.Source: §4 · pp. 6–7
- The cluster-assignment and centroid updates have deterministic descent, but the random graph update is guaranteed to decrease energy only in expectation.The expected graph-update decrease is at least quadratic in the step size.Source: §4 · p. 7
- Combining the blockwise descent results makes expected Lyapunov energy nonincreasing and convergent, while successive differences of all blocks vanish as k → ∞.The energy is bounded below by zero.Source: §4 · pp. 7–8
5 Persistence-based Similarity Matrix
The section constructs a persistence-based similarity matrix from zero-dimensional persistent homology to provide the framework's topological prior. Pairwise component-merger scales encode multiscale connectivity, and the resulting similarity is stable to small input perturbations.
5 Persistence-based Similarity Matrix
- S serves both as the SBM edge-probability prior and as the center of the DRO ambiguity set, anchoring graph learning and robustness to multiscale connectivity.The framework uses S in both roles.Source: §5 · p. 8
- For each pair of data points, ε_ij is the H0 barcode death time at which their connected components merge; the matrix S is then constructed from these pairwise values.A finite filtration threshold ensures every pair eventually merges, making ε_ij finite.Source: §5 · p. 8
- Large S_ij indicates that two points merge at an early filtration scale, reflecting global multiscale connectivity rather than proximity at one fixed scale; S inherits stability to small data perturbations.The stated stability follows from the stability of the H0 barcode.Source: §5 · p. 8
6 Numerical Experiments
Across synthetic datasets and Fashion-MNIST subsets, T-ARC’s performance depends on data geometry: persistence-based similarity excels on curved and interleaved structures, while Euclidean similarity can be stronger when structures intersect.
Experimental design
- Experiments covered five synthetic datasets and random Fashion-MNIST subsets, comparing T-ARC with K-means, Spherical K-means, Spectral clustering, and its Euclidean-based variant.Evaluation used Accuracy, F1-score, and Silhouette coefficient.Source: §6 · pp. 9–10
Example 1: Two Sets Dataset
- For Two Sets, T-ARC (persistence) matched K-means and Spectral clustering at 0.99 when σ = 0.12, but fell to 0.83 Accuracy under overlap (σ = 0.20).At σ = 0.20, K-means reached 0.93 Accuracy, Spectral clustering 0.95, and T-ARC (Euclidean) 0.92; persistence is most informative when the persistence gap between intra- and inter-cluster merges is preserved.Source: §6 · p. 11
Example 2: Two-Moons Dataset
- On Two-Moons, T-ARC (persistence) and Spectral clustering achieved perfect Accuracy and F1-score (1.00), versus 0.89 for K-means and 0.87 for T-ARC (Euclidean).T-ARC (persistence) followed the curved structure despite a lower Silhouette score (0.61) than K-means (0.67).Source: §6 · p. 12, Figure 5 · p. 12
Example 3: Two-Spirals Dataset
- 0.96 Accuracy and F1-score: T-ARC (persistence) led on Two-Spirals, ahead of K-means and Spherical K-means (both 0.84) and Spectral clustering (0.78 and 0.76).Its Silhouette score was 0.58, below 0.68 for K-means, Spherical K-means, and T-ARC (Euclidean), because that metric favors Euclidean compactness.Source: §6 · p. 13, Figure 7 · p. 13
Example 4: Two-Eights Dataset
- With k = 4 initialization, T-ARC (persistence) grouped the four Two-Eights circles into two figure-eight clusters, matching the connected components at the relevant scale.Its Silhouette score was 0.64 versus 0.56 for K-means and 0.57 for Spectral clustering, though these different cluster counts are not directly comparable.Source: §6 · p. 14, Figure 9 · p. 14
Example 5: Chain-link Dataset
- On Chain-link, T-ARC (Euclidean) achieved the best external indices, with 0.91 Accuracy and F1-score, while the persistence prior merged the rings at their contact point.T-ARC (persistence) and K-means each scored 0.83 Accuracy and F1-score.Source: §6 · p. 15
Example 6: Fashion-MNIST Subset
- On Fashion-MNIST, T-ARC (persistence) achieved 0.91 ± 0.02 Accuracy and 0.91 ± 0.02 F1-score, and was markedly more stable than K-means.Its persistence prior matched or outperformed the Euclidean variant in 9 of 10 subsets; K-means reached 0.53 Accuracy on one subset.Source: §6 · p. 16
7 Conclusion and Future Work
T-ARC combines a K-means data-fidelity term with graph-cut regularization, jointly optimizing cluster assignments and a random SBM graph informed by persistent homology. Experiments report recovery of non-convex synthetic structures and competitive Fashion-MNIST performance, alongside convergence of the expected Lyapunov functional.
7 Conclusion and Future Work
- T-ARC adds graph-cut regularization to K-means and jointly learns assignments with a latent graph modeled as a random Stochastic Block Model.Its SBM parameters are optimized within a Distributionally Robust Optimization framework, yielding closed-form updates solved via a proximal point method.Source: §7 · p. 16
- The persistence-based similarity matrix supplies a fixed topological prior, and the expected Lyapunov functional is nonincreasing and convergent under the block-coordinate updates.The convergence analysis also establishes vanishing successive differences of all blocks, including stochastic graph updates.Source: §7 · p. 16
- On Two-Moons and Two-Spirals, T-ARC recovers underlying topological structure where K-means fails; on two-eights, k = 4 identifies two higher-level clusters corresponding to the two eights.The table caption notes that T-ARC (persistence) converges to k = 2 macro-clusters, one per eight, while external indices use the k = 4 ground truth.Source: §7 · p. 16, Table 2 · p. 17
- On Fashion-MNIST, T-ARC outperforms K-means and Spectral clustering on average, is more stable than K-means, and attains the highest average Silhouette score.Table 2 reports Fashion-MNIST means ± standard deviations over 10 subsets; each subset contains 50 images per class.Source: §7 · p. 17, Table 2 · p. 17, Table 1 · p. 17
A Derivation of Feasibility Constraints on b
The feasibility derivation constrains the smoothed representation B(a,b) by row-stochasticity, positivity, nonnegativity, and a Frobenius-distance bound. Substituting the row-stochasticity relation reduces the constraints to bounds on b.
A Derivation of Feasibility Constraints on b
- The representation B(a,b) = aS + b(1_n1_n^T − S) is constrained by the ambiguity set, and row-stochasticity gives a = 1 + b(1 − n).The derivation substitutes this relation so the remaining constraints are expressed solely in b.Source: A Derivation of Feasibility… · p. 19
- Nonnegativity imposes a bound using M = max_i,j S_ij, but that constraint is always dominated by the row-stochasticity bound.The passage gives 1/n ≤ M ≤ 1 for row-normalized S and concludes constraint (12) is dominated by (11).Source: A Derivation of Feasibility… · p. 19
- The Frobenius-distance condition ∥B(a,b) − S∥_F ≤ r yields an upper bound on b, which is combined with the remaining bound to form the final feasibility bounds.The final bounds discard the dominated nonnegativity constraint.Source: A Derivation of Feasibility… · p. 19