2005 SemiSupervisedGraphClusteringaK

• (Kulis et al., 2005) ⇒ Brian Kulis, Sugato Basu, Inderjit Dhillon, and Raymond Mooney. (2005). “Semi-supervised Graph Clustering: A Kernel Approach.” In: Proceedings of the 22nd International Conference on Machine learning (ICML-2005). doi:10.1145/1102351.1102409

Subject Headings: Semi-Supervised Graph Clustering; Semi-Supervised Graph Clustering Algorithm

Notes

• Paper Presentation http://videolectures.net/icml05_kulis_aa/

Cited By

• http://scholar.google.com/scholar?q=%22Semi-supervised+graph+clustering%3A+a+kernel+approach%22+2005
• http://dl.acm.org/citation.cfm?id=1102351.1102409&preflayout=flat#citedby

Quotes

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 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 (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.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2005 SemiSupervisedGraphClusteringaK	Sugato Basu Raymond J. Mooney Inderjit S. Dhillon Brian Kulis			Semi-supervised Graph Clustering: A Kernel Approach				10.1145/1102351.1102409		2005