Skip to yearly menu bar Skip to main content


Graph Clustering: Block-models and model free results

Yali Wan · Marina Meila

Area 5+6+7+8 #31

Keywords: [ Graphical Models ] [ Graph-based Learning ] [ (Application) Social Networks ] [ Learning Theory ] [ Spectral Methods ] [ Clustering ]


Clustering graphs under the Stochastic Block Model (SBM) and extensions are well studied. Guarantees of correctness exist under the assumption that the data is sampled from a model. In this paper, we propose a framework, in which we obtain "correctness" guarantees without assuming the data comes from a model. The guarantees we obtain depend instead on the statistics of the data that can be checked. We also show that this framework ties in with the existing model-based framework, and that we can exploit results in model-based recovery, as well as strengthen the results existing in that area of research.

Live content is unavailable. Log in and register to view live content