Header logo is

A PAC-Bayesian Analysis of Co-clustering, Graph Clustering, and Pairwise Clustering

2010

Conference Paper

ei


We review briefly the PAC-Bayesian analysis of co-clustering (Seldin and Tishby, 2008, 2009, 2010), which provided generalization guarantees and regularization terms absent in the preceding formulations of this problem and achieved state-of-the-art prediction results in MovieLens collaborative filtering task. Inspired by this analysis we formulate weighted graph clustering1 as a prediction problem: given a subset of edge weights we analyze the ability of graph clustering to predict the remaining edge weights. This formulation enables practical and theoretical comparison of different approaches to graph clustering as well as comparison of graph clustering with other possible ways to model the graph. Following the lines of (Seldin and Tishby, 2010) we derive PAC-Bayesian generalization bounds for graph clustering. The bounds show that graph clustering should optimize a trade-off between empirical data fit and the mutual information that clusters preserve on the graph nodes. A similar trade-off derived from information-theoretic considerations was already shown to produce state-of-the-art results in practice (Slonim et al., 2005; Yom-Tov and Slonim, 2009). This paper supports the empirical evidence by providing a better theoretical foundation, suggesting formal generalization guarantees, and offering a more accurate way to deal with finite sample issues.

Author(s): Seldin, Y.
Journal: ICML 2010 Workshop on Social Analytics: Learning from human interactions
Pages: 1-5
Year: 2010
Month: June
Day: 0

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Event Name: ICML 2010 Workshop on Social Analytics: Learning from human interactions
Event Place: Haifa, Israel

Digital: 0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{6556,
  title = {A PAC-Bayesian Analysis of Co-clustering, Graph Clustering, and Pairwise Clustering},
  author = {Seldin, Y.},
  journal = {ICML 2010 Workshop on Social Analytics: Learning from human interactions},
  pages = {1-5},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  month = jun,
  year = {2010},
  doi = {},
  month_numeric = {6}
}