cs.LGNov 16, 2026

How Much Distribution Shift Can a Clustering Withstand? Exact Split and Merge Certificates for Structured Transports

Authors: Alisina Bayati, Srinivasa Salapaka, Shahriar Talebi

Organizations: Department of Mechanical Science and Engineering and Coordinated Science Laboratory, University of Illinois Urbana-Champaign, Urbana, IL, USA · Department of Mechanical and Aerospace Engineering, University of California, Los Angeles, Los Angeles, CA, USA

Abstract

In clustering, the distribution of the population being clustered is often uncertain or changes over time, so the true distribution may shift away from the nominal distribution used to form the clustering. Once the clustering is committed and each member is assigned to a cluster, such shifts may change the distribution of each cluster. They can make a cluster too spread out for one representative at a given resolution, motivating a split, or bring distinct clusters close enough to share a representative at that resolution, motivating a merge. We make these split and merge events precise using a local stability criterion built on the phase-transition analysis in deterministic annealing. This notion of stability enables us to quantify how robust a clustering is against such events. Furthermore, motivated by applications in which uncertainty and population change are structured, we study shifts whose displacements are restricted to a prescribed subspace. The smallest structured shifts that reach the respective thresholds define the split and merge radii, for which we obtain exact semidefinite programming (SDP) reformulations. The split SDP has only two scalar decision variables. These convex reformulations enable us to combine the radii into a robustness certificate for the full clustering that gives the size of the smallest structured shift that reaches any monitored split or merge threshold.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Apr 13, 2026

Distributionally Robust K-Means Clustering

K-means clustering is a workhorse of unsupervised learning, but it is notoriously brittle to outliers, distribution shifts, and limited sample sizes. Viewing k-means as Lloyd--Max quantization of the empirical distribution, we develop a distributionally robust variant that protects against such pathologies. We posit that the unknown population distribution lies within a Wasserstein-2 ball around the empirical distribution. In this setting, one seeks cluster centers that minimize the worst-case expected squared distance over this ambiguity set, leading to a minimax formulation. A tractable dual yields a soft-clustering scheme that replaces hard assignments with smoothly weighted ones. We propose an efficient block coordinate descent algorithm with provable monotonic decrease and local linear convergence. Experiments on standard benchmarks and large-scale synthetic data demonstrate substantial gains in outlier detection and robustness to noise.
Jan 16, 2024

Semidefinite programming relaxations and debiasing for MAXCUT-based clustering

In this paper, we consider the problem of partitioning a small data sample of size nn drawn from a mixture of 22 sub-gaussian distributions in Rp\mathbb{R}^p. We consider semidefinite programming relaxations of an integer quadratic program that is formulated essentially as finding the maximum cut on a graph, where edge weights in the cut represent dissimilarity scores between two nodes based on their pp features. We define the signal-to-noise ratio (SNR) as s2:=min⁡{npγ2,Δ2}s^2 := \min\{n p γ^2, Δ^2\}, where Δ2:=pγΔ^2 := p γ denotes the ℓ22\ell_2^2 distance between the two cluster centers. Our contributions are twofold. First, we provide a unified framework for analyzing three computationally efficient algorithms: SDP1, BalancedSDP, and Spectral clustering, yielding universal polynomial-rate misclassification guarantees for all three algorithms. Moreover, our theory allows for partial recovery (success rate <100%< 100\%) as long as s2s^2 is lower bounded by a constant. Second, we prove that the misclassification errors for SDP1 and BalancedSDP decay exponentially with respect to the SNR s2s^2 and the BalancedSDP requires no explicit debiasing when the two clusters have equal sizes. To our knowledge, this is the first time such results are obtained for semidefinite relaxations of MAX CUT in population clustering. We provide simulation evidence illuminating the theoretical predictions.
Sep 24, 2026

Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering

Exact Euclidean KK-means partitions nn observations into KK unlabelled clusters, but the unrestricted search is generally exponential. We use data-derived geometric graphs to precondition an exact subset dynamic program: as a result only connected vertex subsets are admitted as clusters, while sum-of-squared-errors (SSE) loss is unchanged. A remaining-set recurrence minimises fixed-KK or penalised SSE, with exact factorisation over the connected components of each remaining set. The central question we study is how much computational support can be removed while preserving an unrestricted optimum. Graph inclusion gives monotone coverage and support relations, and a bottleneck threshold identifies the first covering graph in a nested hierarchy. For fixed KK and dimension, under compact ball support and density bounds, retaining q=O(log⁡n)q=O(\log n) nearest neighbours per observation preserves an empirical SSE optimum with probability tending to one, using an O(log⁡n/n)O(\log n/n) fraction of complete-graph edges. Truncated Gaussian mixtures with unequal weights and covariances satisfy these conditions. The rate we provide is a sufficient upper bound rather than a result implying polynomial optimisation complexity. Objective-matched synthetic and full-data comparisons assess coverage, compression, and reference-label agreement. As a secondary application, we illustrate how the proposed scaffold preconditioning can be utilized to improve the efficiency of split-merge proposals that preserve unrestricted mixture posteriors.