CS Paper Radar

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

Alisina Bayati, Srinivasa Salapaka, Shahriar Talebi

cs.LG ·submitted 2026-11-16 23:31 UTC · v1
unusual

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Tightness and Error Exponents of SDP with Logarithmically Many Communities

cs.IT math.ST ·2026-10-07 ·Shengtao Guo, Ethan X. Fang, Junwei Lu
theory similarity 0.56
Abstract · 36 pages, 8 figures

We study a semidefinite programming (SDP) relaxation for community recovery when the number of communities grows logarithmically. In the balanced stochastic block model with $n=km$ vertices, we consider the regime $k/\log m\toγ>0$, with edge probabilities $α\log m/m$ within communities and $β\log m/m$ across them, for fixed $α>β>0$. We derive the sharp asymptotic tightness boundary away from critical cases. When rare vertices cause tightness to fail while the bulk remains spectrally stable, the normalized matrix error of every near-optimal solution still vanishes. We prove matching high-probability exponents for this error and the normalized optimal objective gain, governed by the same local correction that determines tightness. Throughout this spectrally stable region, a single SDP solve followed by explicit rounding and refinement achieves exact community recovery above the information-theoretic threshold. This guarantee holds even when the planted community matrix is not an optimal solution to the SDP.

0.31

Exact Sum-of-Radii Clustering under Any Constant Stability

cs.DS ·2026-11-02 ·Shyam Ravichandran, Lev Reyzin
similarity 0.55
Abstract · 27 pages

We establish a separation between the stability thresholds of Minimum Sum-of-Radii (MSR) clustering and two closely related objectives. Known hardness results show that, on general metrics, exact recovery for Minimum Sum-of-Diameters and symmetric $k$-center is hard for every fixed $1<γ<2$, unless NP=RP. We show that MSR admits deterministic polynomial-time exact recovery for every fixed $γ>1$, extending Gao and Reyzin's result for $γ\ge2$. All three results use the same Bilu--Linial stability model: the optimal partition remains uniquely optimal when each pairwise distance is multiplied by any factor in $[1,γ]$, without requiring the perturbed distances to satisfy the triangle inequality. The number of clusters is part of the input. For $1<γ<2$, our algorithm runs in $n^{O((γ-1)^{-5})}$ time. The main structural insight is that a cheap merge in one part of the instance would allow a profitable split elsewhere under a suitable perturbation, contradicting stability. The resulting exchange inequality controls local cluster density, which gives linear growth and hence bounded treewidth in local interaction graphs. We use random partitions to obtain these regions, solve them by dynamic programming, and then derandomize the construction. For rational input and fixed rational $γ>1$, recognizing stability in this model is coNP-complete. Verifying that a supplied partition remains uniquely optimal under all allowed perturbations is coNP-complete for both arbitrary symmetric and metric perturbations.

0.30

Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems

cs.DS ·2026-09-28 ·David García-Soriano, Atsushi Miyauchi
similarity 0.54
Abstract

The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most $k$ clusters using $k$ independent Gaussian vectors. Its analysis hinges on the collision probability $P_k(ρ)$ that two nodes whose SDP vectors have inner product $ρ$ are assigned to the same cluster. No tractable closed form for $P_k$ is known for $k\geq 4$, making it difficult to certify approximation guarantees and hindering the systematic search for better algorithms. We develop a Hermite-coefficient certification framework to derive accurate and tractable bounds on $P_k$. Using the Hermite expansion of Gaussian noise stability, we express $P_k$ as a power series with nonnegative coefficients, reduce these coefficients to one-dimensional Gaussian integrals, and certify finitely many of them, yielding rigorous bounds on $P_k$ over the entire correlation range. Our framework yields strengthened polynomial-time approximations for several clustering problems. For MaxAgree Correlation Clustering, we derive a $0.7818$-approximation, the first improvement in two decades over the $0.7666$ ratio of Swamy (2004). We also improve the best known ratios for the variant with at most $K$ clusters, MaxAgree$[K]$ (e.g., from $0.77$ to $0.8151$ for $K=3$). For Max $K$-Cut we resolve, via a structural property of the Hermite expansion, a conjecture of de Klerk et al. (2004) characterizing the Frieze--Jerrum approximation ratio for every $K\ge3$; we show that this ratio is tight, and determine it to within $10^{-6}$ accuracy for $K\le16$. Finally, we reduce the additive approximation error for modularity maximization from $0.42084$ (Kawase et al., 2021) to $0.3790$. On the hardness side, we show that approximating Maxagree within $0.802+ε$ is Unique Games-hard via a construction in Gaussian space analyzed by Borell's inequality.

0.40

Calibrating Ambiguity Set via Diagnostic Transport for Distributionally Robust Optimization

cs.LG stat.MLmath.OC ·2026-10-07 ·Wenbin Zhou, Elizabeth Cucuzzella, Shixiang Zhu
similarity 0.54
Abstract

Distributionally robust optimization (DRO) protects decisions against distributional uncertainty by optimizing over an ambiguity set, but poorly aligned set geometry can require large radii and yield overly conservative decisions. We introduce diagnostic-transport DRO (DT-DRO), which uses held-out calibration data to adapt the ambiguity-set geometry to observed predictive errors. DT-DRO uses the conditional probability integral transform cumulative distribution function to diagnose systematic probability misallocation and translates this information into an outcome-level transport that jointly adjusts the ambiguity-set center and ground cost. The resulting formulation admits a computationally tractable dual reformulation. Theoretically, we derive valid ambiguity radii and decision-risk guarantees that tighten as estimation and approximation errors vanish, and show that DT-DRO can eliminate the nonvanishing robustness floor caused by model misspecification. Synthetic experiments and a power-outage application demonstrate improved decision quality, particularly under structural and tail misspecification.

0.22

Optimal Approximation for Constrained Correlation Clustering via Repulsion

cs.DS ·2026-11-03 ·Yixin Cao, Ying Xu
similarity 0.54
Abstract · Superseding arXiv:2608.04883

The best-known approximation factor for constrained correlation clustering stood at three for nearly two decades, until a recent improvement to below $16/7$. We give a randomized polynomial-time $(2+\varepsilon)$-approximation using \emph{Repulsion}, a recursive operation that separates a metric ball from its complement. Repulsion naturally respects hard constraints and admits a short potential-based analysis; as a warm-up, radius-$2/3$ Repulsion rounds the standard metric LP into a feasible partition of cost at most three times its objective. The $(2+\varepsilon)$-approximation takes a two-stage approach, first removing must-links with arbitrarily small loss in the approximation ratio. The second stage combines lossless, constraint-aware preclustering with the bounded sub-cluster LP framework of Cao, Cohen-Addad, Lee, Li, Newman, and Vogl (STOC 2024). Repeated positive conditioning and sampling produce candidate sets, which radius-one Repulsion partitions into feasible clusters at controlled cost. We also give an approximation-preserving reduction from vertex cover to cluster deletion, a special case with only cannot-links. Apart from establishing a matching factor-two hardness threshold under the Unique Games Conjecture, it motivates our two-stage approach and Repulsion.

0.15

Coresets for Capacitated Clustering via Dual Concentration

cs.DS cs.CGcs.LG ·2026-11-06 ·Milind Prabhu, Chris Schwiegelshohn, Sudarshan Shyam, Erik Waingarten
similarity 0.54
Abstract

We study coresets for clustering problems, focusing on the classical $k$-median and $k$-means objectives. A coreset is a small weighted summary of the input data that approximately preserves the clustering cost for every choice of centers. Such summaries are a central tool for scaling clustering algorithms to large datasets. In this work, we consider the capacitated setting, where the clustering is subject not only to choosing centers but also to respecting prescribed cluster-size constraints. This model is a natural generalization of standard clustering and has been widely studied, but its coreset complexity is less well understood. For finite metric spaces, we obtain optimal-size coresets; surprisingly, these match the best-known bounds for unconstrained clustering. We also give improved coreset bounds in Euclidean space, notably the first coresets with near-linear dependence in $k$ while being independent of the dimension and input size. The main new technical ingredients are concentration bounds for the dual solutions of min-cost flow problems, which allow for both significantly simpler and tighter analyses of the underlying sampling distribution used in the coreset construction.

0.12

Pseudometric-Weighted Correlation Clustering via Spectral Preclustering

cs.DS ·2026-09-15 ·Chenglin Fan, Dahoon Lee, Euiwoong Lee
similarity 0.53
Abstract · 37 pages, 2 figures, in submission

We study \emph{pseudometric-weighted correlation clustering}, in which pairs have arbitrary positive or negative labels and nonnegative disagreement weights satisfying the triangle inequality. For every fixed $\varepsilon>0$, we give a randomized polynomial-time $(2+\varepsilon)$-approximation, improving the previous factor of $10/3$. The algorithm constructs an explicit feasible solution to the cluster LP with polynomial support and value at most $(1+\varepsilon)\mathrm{OPT}$, where $\mathrm{OPT}$ is the minimum integral clustering cost. Our main contribution is a weighted preclustering construction that witnesses a near-optimal clustering while bounding the total weight of admissible edges by $\operatorname{poly}(1/\varepsilon)\mathrm{OPT}$. We obtain admissibility certificates from random walks, where the factor-two Ptolemy's inequality for pseudometrics reduces the required length of walks from $O(\log n)$ to a constant. We then bound the rounding error separately at each vertex and use the triangle inequality to control its weighted cost. Sampling and coverage corrections produce an exactly feasible solution, and the factor-two rounding completes the approximation algorithm.

0.37

Streaming algorithms for computing coresets and $k$-median clustering in the Hamming space

cs.DS ·2026-08-25 ·Taha El Ghazi, Jonas Ellert, Chien-Chung Huang, Tatiana Starikovskaya
published similarity 0.53
Abstract · Accepted to WAOA 2026

Clustering is one of the most fundamental tools in data analysis, allowing large datasets to be summarized by a small number of representative points. Given a metric space $(\mathcal{X}, \mathbb{d})$ and a set $S$ of $n$ points in this space, the continuous $k$-median clustering problem asks to find a set $C$ of $k$ points that minimizes the objective function $\sum_{s\in S} \mathbb{d}(s,C)$. When $\mathcal{X} = Σ^\ell$ is the set of strings of length $\ell$ and $\mathbb{d}$ is the Hamming distance, the continuous $k$-median clustering problem is known to be W[1]-hard when parameterized by $k$. In this work, we present the first $(1+\varepsilon)$-approximation algorithm for this problem with FPT runtime $2^{\mathrm{poly}(\varepsilon^{-1},k)} \cdot n\ell \mathrm{polylog} \; n$. An additional feature of the algorithm is that it can be implemented in streaming, requiring only $\tilde{O}_\varepsilon(\ell k + k^2)$ space. As an auxiliary tool of independent interest, we show the first streaming algorithm for computing an $\varepsilon$-coreset for continuous $k$-median clustering under the Hamming

0.42