Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering

Yordan P. Raykov; Max A. Little

math.STSep 24, 2026

Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering

Authors: Yordan P. Raykov, Max A. Little

Organizations: School of Mathematical Sciences, University of Nottingham · School of Computer Science, University of Birmingham

Abstract

Exact Euclidean $K$ -means partitions $n$ observations into $K$ 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- $K$ 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 $K$ and dimension, under compact ball support and density bounds, retaining $q=O(\log n)$ nearest neighbours per observation preserves an empirical SSE optimum with probability tending to one, using an $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.

Figures & tables

Figure 1: Fixed-

K

comparison across the six Gaussian designs. Points are means over 20 independently generated data sets. VI error bars are pointwise 95% Monte Carlo intervals; oracle-hit error bars are normal-approximation intervals for the observed proportions. The left panel compares partitions with the generating labels by variation of information; the right panel gives the frequency of attaining the complete-graph SSE optimum. The panels evaluate different targets and need not rank methods identically.

Scaffold	Coverage	Edges	Connected blocks	Reached sets	Transitions
$2$ -NN-MST	97.500	19.980	4.020	12.810	0.242
Gabriel	100.000	17.670	4.900	11.060	0.298
Delaunay	100.000	33.690	53.970	66.360	9.442
Complete	100.000	100.000	100.000	100.000	100.000

Table 1: Optimum coverage and computational support for the fixed-

K

experiment. Coverage is the percentage of the 120 data sets for which the scaffold recurrence equals the complete-graph SSE optimum. All remaining entries are percentages of the corresponding complete-graph quantity.

Figure 2: Scaffold restriction on two moons, with

n=60

, noise SD

0.020

, and the first prespecified seed. Colours show generating groups in (a) and fitted blocks in (b), (c), and (d). Grey segments are scaffold edges. In (c), the dashed MST edge separates the blocks selected by SSE but remains part of the scaffold; any tree edge could have been cut. In (d), the dashed longest edge is removed from the scaffold before optimization, forcing its two components. Displayed scores are for this realization, not averages.

Data set	Method	SSE	SSE/TSS	ARI	NMI
Iris ( $n=150$ )	Lloyd, random start	140.902	0.235	0.645	0.661
$d=4,\ K=3$	$k$ -means++, 1 start	139.820	0.233	0.620	0.659
	$k$ -means++, 20 starts	139.820	0.233	0.620	0.659
	Ward	148.876	0.248	0.615	0.675
	DP, MST	142.030	0.237	0.594	0.647
	DP, $H_{2}$	139.985	0.233	0.601	0.647

Table 2: Full-data UCI clustering comparison: every method uses all

n

observations, with no subsampling. Starts count initializations, not data samples. Smaller SSE and SSE/TSS indicate lower centroid loss; larger ARI and NMI indicate stronger agreement with the reference classes.

H_{q}

is union

q

-NN plus a common MST. Time limits mark unfinished exact searches, not fitted partitions. All numerical DP entries are exact on the stated scaffold. Computational settings and work counts for these runs are reported in Appendix \thechapter.E.5 .

Figure 3: Posterior accuracy and proposal acceptance on one shared

n=300

data set. Panels (a) to (c) show off-diagonal PSM RMSE against independent reference chains, using four evaluation chains at matched retained-sweep counts; lower is better. The NGGP panel uses a finer vertical scale. Panel (d) reports accepted split-merge moves as a percentage of attempts over the 2,500-sweep prefixes, excluding warm-up. Gibbs has no split-merge attempts. The nested prefixes are not independent replicates; lines join observed values and do not represent fitted convergence rates.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Objective	Method	Oracle hits	Matched gap	Mean $\widehat{K}$	Mean VI
Penalized SSE	DP-means	$37/120$	$9.101\%$	3.600	0.883
	$2$ -NN-MST DP	$117/120$	$0.025\%$	3.817	0.750
	Gabriel DP	$120/120$	$0\%$	3.833	0.751
	Complete DP	$120/120$	$0\%$	3.833	0.751
Collapsed NIW-CRP MAP	MAP-DP coordinate ascent	$92/120$	$0.186$	2.683	1.046
	$2$ -NN-MST DP	$107/120$	$0.047$	2.608	1.011

Appendix

Table 3: Unknown-

K

objective-matched comparisons over 120 data sets. For penalized SSE, the reported gap is the mean relative objective gap. For collapsed MAP, it is the mean loss in log posterior, in nats. VI is measured against the generating labels and is not part of either optimized objective.

Scaffold	Stored state pairs (%)	Inspected block candidates (%)	Component-cache masks	Convolution relaxations
MST	55.800	23.800	111.000	70.000
RNG	75.400	26.900	237.000	198.500
Gabriel	83.900	28.800	536.000	432.500
$2$ -NN-MST	70.100	20.300	476.250	361.500
$3$ -NN-MST	95.800	44.500	1179.000	1072.000
Delaunay	102.200	67.800	1658.750	1342.500

Appendix

Table 4: Component-factorized evaluation relative to basic subset-DP evaluation on the same

n=12

sample and scaffold. The first two numerical columns are mean paired ratios, expressed as percentages; the last two are mean additional bookkeeping counts. Each row averages four geometry cells. The

q=1

row duplicates MST and is omitted. These are operation and storage counts, not total-memory or runtime speedups.

Figure 4: The objective-mismatch chain control (top) and the local-search offset-column control (bottom). Grey segments are scaffold edges.

Figure 5: Candidate connectivity at $n=60$ over 20 data sets per separation level (left), with edges per observation shown only as graph density (right).

Noise SD	Method	SSE	ARI	VI (bits)
0.020	Lloyd	24.095	0.224	1.642
	$k$ -means++, 1 start	24.093	0.224	1.642
	$k$ -means++, 20 starts	24.080	0.211	1.663
	DP, intact MST	28.762	0.445	0.989
	DP, pruned MST	37.293	1.000	0.000
	DP, $2$ -NN-MST	28.762	0.445	0.989

Appendix

Table 5: Two-moons results at

n=60

K=2

. Entries are means over five paired realizations at each noise level; every displayed fit completed. The pruned-MST fit is identical to single linkage and is shown only once. SSE is the optimized loss for the DP fits; ARI and VI assess generating-label agreement. Variability is illustrated in Figure 6 .

Figure 6: Noise sensitivity of the two-moons comparison. Small translucent points are individual realizations, slightly displaced horizontally for visibility; larger joined points are means over five realizations. Lower SSE/TSS and higher ARI measure different properties. Pruning the MST improves label recovery at low noise but becomes unreliable as noise increases.

Data set	$q$	Outcome	Memo	Calls	Blocks	Nodes	Seconds
Iris	0	Exact	78	23,234	11,103	22,394	0.215
	2	Exact	5,325	9,624,602	5,056,399	14,132,817	504.050
Wine	0	Exact	75	36,243	15,650	31,529	0.389
	2	Time limit	87,906	142,109,069	50,016,325	138,449,989	6480.018
Breast cancer	0	Exact	1	569	568	1,137	0.052
	2	Time limit	0	11,187,579	11,187,578	28,531,351	6480.000

Appendix

Table 6: Computational work for the final full-data scaffold-DP runs reported in Table 2 . Memo counts retained completed state-count pairs; Calls includes repeated and boundary evaluations. Blocks counts emitted candidate blocks across subproblems, not globally distinct sets, and Nodes counts generator search nodes, including unsuccessful branches. For stopped searches these are work observed before termination, not final support sizes. Seconds measure the solver, excluding graph construction and worker startup.

Data set	Lloyd	KM++ (1)	KM++ (20)	Ward	MST cuts
Iris	0.010	0.000	0.003	0.021	0.517
Wine	0.010	0.000	0.003	0.022	0.848
Breast cancer	0.010	0.001	0.004	0.023	0.091
Soybean	0.009	0.000	0.003	0.020	0.426
Vehicle	0.036	0.001	0.008	0.035	Not run

Appendix

Table 7: Fitting times in seconds for the full-data comparators and independent MST-cut checks used in the reported evaluation. KM++ (1) and KM++ (20) use one and twenty initializations, respectively. Times exclude data preprocessing and worker startup; the cut times also exclude graph construction. These single-run, hardware-dependent measurements are computational diagnostics, not replicated speed comparisons.

Dataset	$K$	MST	Union $2$ -NN	Union $5$ -NN
Iris	3	85	95	100
Wine	3	55	90	100
Breast Cancer	2	65	95	100
Soybean	4	95	100	100
Vehicle	4	75	90	100

Appendix

Table 8: Optimum-coverage rates (percent) on 20 full-dimensional, stratified

n=15

samples.

Target	Sampler	$\max\widehat{R}$	Min. ESS	Accept. (%)	PSM RMSE	TV for $K$
Finite	Gibbs	1.008	808	n/a	2.029e-03	1.495e-02
	Generic	1.002	1218	1.950	2.045e-03	3.450e-03
	Guided $q=2$	1.007	948	2.290	1.771e-03	1.600e-03
	Guided $q=3$	1.004	1274	2.540	5.798e-03	9.700e-03
	Permuted $q=3$	1.006	665	1.560	3.906e-03	1.410e-02
DP	Gibbs	1.010	1759	n/a	1.092e-03	1.215e-02

Appendix

Table 9: The

n=300

comparison at 2,500 retained sweeps per chain. Acceptance pools 10,000 attempted split-merge moves across four chains. PSM RMSE and total variation for

K

compare with the independent Monte Carlo reference; smaller is better. All three references pass their diagnostic checks. The NGGP rows use the log-scale slice update throughout. Gibbs has no split-merge acceptance rate.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 342 papers

Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering
Mar 28, 2026Yuxuan Ren, Shijie DengClustering Semi-Supervised Learning
School of Industrial and Systems Engineering Georgia Institute of Technology, USA
Why does Greedy Search produce Optimal Clustering Outcomes? A Fixed-Core Assignment Theory
Jul 27, 2026Kaifeng Zhang, Kai Ming Ting, Sanjay ChawlaClustering Unsupervised Clustering
School of Artificial Intelligence Nanjing University, China · Qatar Computing Research Institute, HBKU
An Algebraic Approach to Constrained K-means Clustering
Oct 10, 2026Hiroki Oohori, Kentaro Fukushima, Michio YamamotoClustering
Graduate School of Human Sciences, The University of Osaka, Osaka, Japan · Graduate School of Education, The University of Tokyo, Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan +1

Mar 28, 2026J/K move · Enter open · S save

Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering

Yuxuan Ren, Shijie Deng

School of Industrial and Systems Engineering Georgia Institute of Technology, USA

Clustering Semi-Supervised Learning

Open paper AskPDF arXiv

This paper presents a novel centroid-based heuristic algorithm, termed Kempe Swap K-Means, for constrained clustering under rigid must-link (ML) and cannot-link (CL) constraints. The algorithm employs a dual-phase iterative process: an assignment step that utilizes Kempe chain swaps to refine current clustering in the constrained solution space and a centroid update step that computes optimal cluster centroids. To enhance global search capabilities and avoid local optima, the framework incorporates controlled perturbations during the update phase. Empirical evaluations demonstrate that the proposed method achieves near-optimal partitions while maintaining high computational efficiency and scalability. The results indicate that Kempe Swap K-Means consistently outperforms state-of-the-art benchmarks in both clustering accuracy and algorithmic efficiency for large-scale datasets.

Abstract

Clustering

Explore similar work

Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering

Why does Greedy Search produce Optimal Clustering Outcomes? A Fixed-Core Assignment Theory

An Algebraic Approach to Constrained K-means Clustering