- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper considers the classic k-means clustering problem. A classic heuristic is Lloyd's heuristic that unfortunately can get stuck in less good local optimals. To overcome this, the paper considers the possiblity to additionally reassign a point/sample to a different cluster center to decrease the cost and then continue with Lloyd's. Actually optimality with respect to a single point was done in a recent paper by Li et al in 2025.
The main contribution of the current paper is to propose local optimality with respect to multiple point/sample reassignments, and, with a focus on 2-optimality, they show structural properties that allow them to speed up the search for improving swaps in certain situations.
The paper presents experiments showing that this leads to better results than e.g. 1 optimality without increasing the comptuational cost too much.
Critical strengths
The paper addresses an important problem and makes a clean heuristic work better and identifies structural properties which allow them to speed up the search.
Critical weaknesses
Going from 1-optimality to 2- and more generally any swap optimality is not an original contribution or interesting. This is standard in local search.
The structural properties are nice but not striking by themselves.
The computational experiments are not very concluding. Why is it not used together with, e.g., k-means++ initialization or k-means++ greedy initialization that is implemented in scipy?
Questions for authors
7 comments
W2: The structural properties are nice but not striking by themselves.
A2: We agree that the connectedness property of the cluster-transfer graph, viewed in isolation, is not the main contribution of this work. Its significance lies in how it enables an exact characterization of the complete two-point search neighborhood and, in turn, the design of exact search and safe screening algorithms.
Specifically, we use the cluster-wise decomposition of the k-means WCSS objective to show that gains associated with distinct weakly connected components are additive. Therefore, at a D-local state, a two-point move consisting of disconnected components cannot improve WCSS. It follows that every improving two-point move must have a weakly connected cluster-transfer graph.
For , this property has a direct algorithmic consequence: a connected transfer graph formed by two moves involves at most three clusters, allowing us to enumerate the complete improving neighborhood exactly through six configurations (Theorem 4.4 and Table 1). We then use closed-form WCSS gain expressions and Top-3 insertion-score lists to replace exhaustive destination optimization with efficient queries. Given the sample-pair distances, this reduces the destination-search complexity from to .
More importantly, the same structural characterization underpins our safe screening mechanism. We construct reusable upper-envelope certificates for the six configurations, providing an upper bound on the gains of all relevant connected two-point moves involving each sample. Samples with non-positive certificates can therefore be safely discarded without missing any improving move. Furthermore, Theorem 7.2 establishes that, under the stated distributional assumptions and nonvanishing occupancy condition, the retained candidate count satisfies , giving screening-and-search complexity per round for fixed .
We also clarify that connectedness alone does not reduce the worst-case search complexity for general . As shown in Appendix B, the number of connected moves can still be as large as in the worst case. Accordingly, our main algorithmic contributions focus on the special structure for and the exact search and safe screening mechanisms it enables.
Changes in the paper: We added an explanatory paragraph after Theorem 4.4 to clarify the theorem's role in reducing the complete two-point neighborhood and supporting the algorithms in Sections 5 and 6.
W3: The computational experiments are not very concluding. Why is it not used together with, e.g., k-means++ initialization or k-means++ greedy initialization that is implemented in scipy?
We first clarify that the original experiments already use standard k-means++ initialization. Specifically, for each dataset, we independently generate ten k-means++ initial center sets and share each set across all comparison methods to ensure a fair comparison. This protocol is described in the Initialization paragraph of Appendix F. We recognized that it was not sufficiently clear in the main text and made it explicit in the revised Section 8.1.
Following the reviewer's suggestion, we also evaluated the methods with greedy k-means++ initialization. We conducted additional experiments on seven datasets, generating ten independent greedy k-means++ initial center sets per dataset and sharing each set across all comparison methods. The results are reported in Table 19 of Appendix G.9.
With greedy k-means++ initialization, BPS-2PLS achieves the lowest mean WCSS on five of the seven datasets. On the other two datasets, its results remain close to the best: its mean WCSS is approximately 0.029% higher than Hartigan on MNIST-2000 and 0.001% higher than D-LO on 20News. BPS-2PLS also achieves lower mean WCSS than Min-D-LO on all seven datasets.
These results show that, on the seven evaluated datasets, BPS-2PLS retains its WCSS advantage over Min-D-LO under both standard and greedy k-means++ initialization.
Changes in the paper: Section 8.1 and the Initialization paragraph in Appendix F now explicitly describe the shared standard k-means++ initialization protocol. Appendix G.9 and Table 19 report the additional results with greedy k-means++ initialization.
We thank the reviewer for this comment. We agree that extending a local-search neighborhood from one-point moves to multi-point exchanges is a common idea in combinatorial optimization. We do not claim the abstract concept of r-point local optimality itself as an independent contribution. Rather, our contribution is an exact characterization of the complete improving two-point neighborhood for the standard k-means WCSS objective, together with efficient search and optimality-certification mechanisms built on this characterization.
The key difficulty is that simultaneously reassigning two samples requires recomputing the centroids of their shared clusters, which introduces interactions between the two moves. Consequently, two one-point moves that are individually non-improving may jointly reduce WCSS. Direct enumeration over all sample pairs and destination clusters would require O(n2k2) search.
Our technical contributions address this difficulty in three ways:
We also acknowledge prior work on two-sample reassignments, including Tarsitano (2003), which studies a different clustering criterion. Our contribution is the exact structural characterization, safe optimality certification, and candidate-set size guarantee for the standard WCSS objective.
Changes in the paper: In the Introduction, we revised the first contribution statement to avoid presenting the general local-optimality hierarchy as the main novelty. It now reads: “We characterize the complete improving two-point neighborhood at a D-local state through weakly connected cluster-transfer graphs. For r=2, this characterization yields six configurations and enables exact destination optimization.”