Semi-supervised clustering algorithms aim to improve clustering results using limited supervision. The supervision is generally given as pairwise constraints; such constraints are natural for graphs, yet most of the semi-supervised clustering algorithms are designed for data represented as vectors. In this paper, we unify vector-based and graph-based approaches. We show that a recently-proposed objective function for semi-supervised clustering based on Hidden Markov Random Fields, with squared Euclidean distance and a certain class of constraint penalty functions, can be expressed as a special case of the weighted kernel k-means objective. A recent theoretical connection between kernel k-means and several graph clustering objectives enables us to perform semi-supervised clustering of data given either as vectors or as a graph. For vector data, the kernel approach also enables us to find clusters with non-linear boundaries in the input data space. Furthermore, we show that recent work on spectral learning may be viewed as a special case of our formulation. We empirically show that our algorithm is able to outperform current state-of-the-art semi-supervised algorithms on both vector-based and graph-based data sets.

PDF, PS

In Proceedings of the 22nd International Conference on Machine Learning, pp. 457--464, Bonn, Germany, August 2005. (Distinguished Student Paper Award).

@InProceedings{Kulis:icml05, title={Semi-supervised Graph Clustering: A Kernel Approach}, author={B. Kulis and S. Basu and I. Dhillon and Raymond J. Mooney}, booktitle={Proceedings of the 22nd International Conference on Machine Learning}, month={August}, address={Bonn, Germany}, pages={457--464}, note={(Distinguished Student Paper Award)}, url="http://www.cs.utexas.edu/users/ai-lab?Kulis:icml05", year={2005} }