Timezone: »

 
Poster
Graph Clustering: Block-models and model free results
Yali Wan · Marina Meila

Mon Dec 05 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #31
in Monday Posters »

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.

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

Author Information

Yali Wan (University of Washington)
Marina Meila (University of Washington)

More from the Same Authors