%0 Conference Paper %1 Kulis:EtAl:05 %A Kulis, Brian %A Basu, Sugato %A Dhillon, Inderjit %A Mooney, Raymond %B 22nd International Conference on Machine Learning %D 2005 %K clustering cobweb master toVerify %T Semi-supervised Graph Clustering: A Kernel Approach %U http://www.cs.utexas.edu/users/ml/papers/kernel-kdd-05.pdf %X 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 semisupervised 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 kmeans 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 nonlinear boundaries in the input data space. Furthermore, we show that recent work on spectral learning (Kamvar et al., 2003) 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.

@inproceedings{Kulis:EtAl:05, abstract = {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 semisupervised 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 kmeans 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 nonlinear boundaries in the input data space. Furthermore, we show that recent work on spectral learning (Kamvar et al., 2003) 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.}, added-at = {2010-05-10T21:37:16.000+0200}, author = {Kulis, Brian and Basu, Sugato and Dhillon, Inderjit and Mooney, Raymond}, biburl = {https://www.bibsonomy.org/bibtex/2bcedccdcff8179a1d10f0ec37747644b/ans}, booktitle = {22nd International Conference on Machine Learning}, interhash = {ed4c71bd2595e5acdfd4a0cd3504ce67}, intrahash = {bcedccdcff8179a1d10f0ec37747644b}, keywords = {clustering cobweb master toVerify}, timestamp = {2011-03-22T23:02:16.000+0100}, title = {Semi-supervised Graph Clustering: A Kernel Approach}, url = {http://www.cs.utexas.edu/users/ml/papers/kernel-kdd-05.pdf}, year = 2005 }