• Topics:
• Graph Clustering
• Kernel Methods

Download: pdf

Citation

• Semi-supervised Graph Clustering: A Kernel Approach (pdf, software)
  B. Kulis, S. Basu, I. Dhillon, R. Mooney.
  In International Conference on Machine Learning (ICML), pp. 457-464, July 2005.
  
  Bibtex:
  
  @inproceedings{kulis2005semisuper, author = "Brian J. Kulis AND Sugato Basu AND Inderjit S. Dhillon AND Raymond Mooney", title = "Semi-supervised Graph Clustering: A Kernel Approach", booktitle = "International Conference on Machine Learning (ICML)", page = "457–464", year = "2005", month = "jul", 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 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." }