Timezone: »

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

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.

Author Information

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

More from the Same Authors