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

Yuxuan Ren; Shijie Deng

cs.LGMar 28, 2026

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

Authors: Yuxuan Ren, Shijie Deng

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

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Kempe Chains between clusters $C_{i}$ and $C_{j}$ .

	Initialization		Assignment		Solution Mutation and Crossover
	Greedy Method	GCP	Greedy Method	GCP	Centroid Perturbation	Centroid Reposition	Centroid Crossover
KSKM	DSATUR-based	No	Kempe Swaps	No	Yes	Yes	No
KSKM_E	DSATUR-based	Yes	Kempe Swaps	Yes	Yes	Yes	No
PCCC	No	Yes	No	Yes	No	Yes	No
BLPKMCC	No	Yes	No	Yes	No	No	No
S_MDEClust	Yes	Yes	By order of data	Yes	No	Optional	Yes

Table 1: State-of-the-art Methods for Semi-Supervised Clustering

	Method	KSKM	KSKM_E	PCCC	BLPKMCC	COPKM_P	COPKM
Dataset	Constraint Level
COL1	0.05	1.00	1.00	1.00	1.00	1.00	0.47
	0.1	1.00	1.00	1.00	1.00	1.00	0.40
	0.15	1.00	1.00	1.00	1.00	1.00	0.63
	0.2	1.00	1.00	1.00	1.00	1.00	0.64
COL2	0.05	1.00	1.00	1.00	1.00	1.00	1.00

Table 2: Algorithm successful rate throughout test.

	Method	KSKM	KSKM_E	PCCC	BLPKMCC	COPKM_P	COPKM
Dataset	Constraints Level
banana	0.005	1.00	1.00	1.00	1.00	1.00	0.00
	0.01	1.00	1.00	1.00	1.00	1.00	0.00
	0.05	1.00	1.00	1.00	1.00	1.00	1.00
cifar10	0.005	1.00	1.00	1.00	1.00	1.00	1.00
	0.01	1.00	1.00	1.00	1.00	1.00	0.00

Table 3: Algorithm success rate among dataset collection 4

	Method	KSKM	KSKM_E	PCCC	BLPKMCC	COPKM_P	COPKM
Dataset	Constraint Level
COL1	0.05	1.00	1.00	1.01	1.04	1.03	1.05
	0.1	1.00	1.00	1.00	1.03	1.02	1.04
	0.15	1.00	1.00	1.00	1.02	1.01	1.02
	0.2	1.00	1.00	1.00	1.01	1.00	1.00
COL2	0.05	1.00	1.00	1.04	1.31	1.10	1.11

Table 4: Comparison of clustering inertia, reported as multiples of the baseline method (KSKM) across datasets among success runs. Lower inertia multiples indicate better performance.

	Method	KSKM	KSKM_E	PCCC	BLPKMCC	COPKM_P	COPKM
Dataset	Constraints Level
banana	0.005	6482.97	6482.97	6486.67	6482.98	6519.10	-
	0.01	7566.29	7566.29	7567.65	7566.29	7707.22	-
	0.05	10556.11	10556.11	10556.11	10556.11	10556.11	10556.11
cifar10	0.005	126770854.91	126492578.88	126612825.71	126519249.09	127530232.16	127579490.59
	0.01	147887573.71	147457869.95	157005767.08	160655672.87	147220022.93	-

Table 5: Algorithm clustering inertia among dataset collection 4

	Method	KSKM	KSKM_E	PCCC	BLPKMCC	COPKM_P	COPKM
Dataset	Constraint Level
COL1	0.05	1.00	2.69	10.49	4.35	0.41	2.45
	0.1	1.00	3.31	10.23	10.28	0.73	0.44
	0.15	1.00	3.51	10.17	24.46	0.62	0.69
	0.2	1.00	3.52	11.79	42.85	0.69	0.87
COL2	0.05	1.00	8.24	11.72	5.65	0.46	0.79

Table 6: Comparison of CPU time, reported as multiples of the baseline method (KSKM) across datasets among success runs. Smaller time multiples indicate faster performance.

	Method	KSKM	KSKM_E	PCCC	BLPKMCC	COPKM_P	COPKM
Dataset	Constraints Level
banana	0.005	0.10	0.11	4.73	1.94	0.37	-
	0.01	0.20	0.31	5.22	2.50	0.18	-
	0.05	0.01	0.01	0.08	1.55	0.03	0.03
cifar10	0.005	322.69	645.73	1224.33	1881.88	55.18	16.07
	0.01	118.05	3602.63	3633.96	3624.14	26.65	-

Table 7: Algorithm clustering CPU time among dataset collection 4

	Stats	Inertia			CPU Time
	Method	KSKM	KSKM_E	PCCC	KSKM	KSKM_E	PCCC
Dataset	Constraint Level
COL1	0.05	1.00	1.00	1.00	1.00	4.09	25.84
	0.1	1.00	1.00	1.00	1.00	5.84	27.47
	0.15	1.00	1.00	0.99	1.00	6.74	25.80
	0.2	1.00	1.00	1.00	1.00	7.96	37.80

Table 8: Comparison of clustering inertia (left) and CPU time (right) among KSKM, KSKM_E, and PCCC with no step of centroid mutation, reported as multiples of the baseline method (KSKM) across datasets. Lower inertia and smaller time multiples indicate better performance.

	Method	KSKM	KSKM_repo	KSKM_E	KSKM_E_repo
Dataset	Constraint Level
COL1	0.05	1.000	1.001	1.000	1.002
	0.1	1.000	1.003	0.998	1.001
	0.15	1.000	1.005	0.999	1.001
	0.2	1.000	1.002	0.998	1.000
COL2	0.05	1.000	1.019	0.999	1.017

Table 9: Comparison of clustering inertia for KSKM variants with and without centroid perturbation, reported as multiples of the baseline KSKM across datasets for successful runs.

		Method	KSKM	KSKM_E	PCCC	BLPKMCC	COPKM_P	COPKM
Dataset	Constraints Level
hayes-roth	0.2	Inertia	601.79	535.76	536.08	546.98	608.25	-
		rate_success	0.50	1.00	1.00	1.00	0.50	0.00
		time	0.01	0.24	0.73	0.28	0.00	-
tae	0.2	Inertia	719.54	681.81	678.54	683.70	731.36	-
		rate_success	0.10	1.00	1.00	1.00	0.10	0.00

Table 10: Clustering inertia and success rate among dataset collection 1 without ML constraints

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

	Method	KSKM	KSKM_E	PCCC	BLPKMCC	COPKM_P	COPKM	S_MDEClust
Dataset	Constraint Level
COL1	0.05	1.00	1.00	1.00	1.01	1.01	1.02	1.00
	0.1	1.00	1.00	1.00	1.00	1.01	1.01	1.00
	0.15	1.00	1.00	1.00	1.00	1.00	1.01	1.00
	0.2	1.00	1.00	1.00	1.00	1.00	1.00	1.00
COL2	0.05	1.00	1.00	1.02	1.08	1.04	1.03	1.01

Appendix

Table 11: Comparison of minimum clustering inertia over 10, reported as multiples of the baseline method (KSKM) across datasets among success runs. Lower inertia multiples indicate better performance.

	Method	KSKM	KSKM_E	PCCC	BLPKMCC	COPKM_P	COPKM	S_MDEClust
Dataset	Constraint Level
COL1	0.05	1.00	2.62	10.43	4.19	0.40	0.85	13.82
	0.1	1.00	3.35	10.15	10.03	0.68	0.14	23.79
	0.15	1.00	3.49	9.98	23.87	0.60	0.45	36.18
	0.2	1.00	3.51	11.69	41.31	0.66	0.56	58.43
COL2	0.05	1.00	10.87	16.10	7.70	0.17	0.39	93.98

Appendix

Table 12: Comparison of total CPU time over 10, reported as multiples of the baseline method (KSKM) across datasets among success runs. Smaller time multiples indicate faster performance.

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

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
CavMerge: Merging K-means Based on Local Log-Concavity
Apr 5, 2026Zhili Qiao, Wangqian Ju, Peng LiuClustering Unsupervised Clustering
Department of Statistics, Iowa State University
Data-Native Global Optimization for Big Data K-means Clustering
Jul 17, 2026Ravil Mussabayev, Rustam Mussabayev, Zukhra Yerdaliyeva +1Clustering Unsupervised Clustering
AI Research Lab, Satbayev University, Almaty, 050000, Kazakhstan · Laboratory for Analysis and Modeling of Information Processes, Institute of Information and Computational Technologies, Almaty, 050010, Kazakhstan

Oct 10, 2026J/K move · Enter open · S save

An Algebraic Approach to Constrained K-means Clustering

Hiroki Oohori, Kentaro Fukushima, Michio Yamamoto

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

Clustering

Open paper AskPDF arXiv

Clustering is typically performed using only object features, although additional information about relationships between objects may be available and can be incorporated through constraints. Among these, pairwise constraints require two objects to belong to the same cluster or to different clusters. Several extensions of the k-means algorithm accommodate such constraints, but they sometimes fail to find a feasible assignment or incur high computational cost. Motivated by these limitations, we propose an algebraic approach to k-means clustering with pairwise constraints. The algorithm simplifies the constraints using Gröbner bases before optimization, improving the efficiency of cluster assignment. It can also detect whether the constraint set has a feasible assignment before optimization. Comparative experiments with existing algorithms showed that the proposed algorithm achieved comparable or better clustering quality at a lower computational cost, particularly when the numbers of constraints and clusters were small.

Abstract

Clustering

Explore similar work

An Algebraic Approach to Constrained K-means Clustering

CavMerge: Merging K-means Based on Local Log-Concavity

Data-Native Global Optimization for Big Data K-means Clustering