A PAC-Bayesian Analysis of Graph Clustering and Pairwise Clustering

Yevgeny Seldin

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. Thi…