A PAC-Bayesian Analysis of Graph Clustering and Pairwise Clustering

Details A PAC-Bayesian Analysis of Graph Clustering and Pairwise Clustering A PAC-Bayesian Analysis of Graph Clustering and Pairwise Clustering

2010-09-02

arxiv.org/abs/1009.0499v1

Computer Science

Learning

Scientific paper

We formulate weighted graph clustering 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. We adapt the PAC-Bayesian analysis of co-clustering (Seldin and Tishby, 2008; Seldin, 2009) to derive a PAC-Bayesian generalization bound for graph clustering. The bound shows 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. We derive a bound minimization algorithm and show that it provides good results in real-life problems and that the derived PAC-Bayesian bound is reasonably tight.

Affiliated with

Also associated with

No associations

Rating

A PAC-Bayesian Analysis of Graph Clustering and Pairwise Clustering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A PAC-Bayesian Analysis of Graph Clustering and Pairwise Clustering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A PAC-Bayesian Analysis of Graph Clustering and Pairwise Clustering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-376778