# A Graph-Partitioning Based Continuous Optimization Approach to Semi-supervised Clustering Problems

arXiv: https://arxiv.org/abs/2503.04447 · HTML: https://mlsanity.com/paper/2503.04447/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 49 references that are in the map.
- First posted on arXiv 6 Mar 2025.

## Builds on (most cited first, 3 of 3)

- [Semi-supervised clustering methods](https://mlsanity.com/paper/1307.0252/) (2013)
- [Spectral Clustering Based on Local PCA](https://mlsanity.com/paper/1301.2007/) (2013)
- [Run-and-Inspect Method for Nonconvex Optimization and Global Optimality Bounds for R-Local Minimizers](https://mlsanity.com/paper/1711.08172/) (2017)

## Abstract (arXiv)

Semi-supervised clustering is a basic problem in various applications. Most existing methods require knowledge of the ideal cluster number, which is often difficult to obtain in practice. Besides, satisfying the must-link constraints is another major challenge for these methods. In this work, we view the semi-supervised clustering task as a partitioning problem on a graph associated with the given dataset, where the similarity matrix includes a scaling parameter to reflect the must-link constraints. Utilizing a relaxation technique, we formulate the graph partitioning problem into a continuous optimization model that does not require the exact cluster number, but only an overestimate of it. We then propose a block coordinate descent algorithm to efficiently solve this model, and establish its convergence result. Based on the obtained solution, we can construct the clusters that theoretically meet the must-link constraints under mild assumptions. Furthermore, we verify the effectiveness and efficiency of our proposed method through comprehensive numerical experiments.