Timezone: »

 
Poster
Clustering from Labels and Time-Varying Graphs
Shiau Hong Lim · Yudong Chen · Huan Xu

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session »

We present a general framework for graph clustering where a label is observed to each pair of nodes. This allows a very rich encoding of various types of pairwise interactions between nodes. We propose a new tractable approach to this problem based on maximum likelihood estimator and convex optimization. We analyze our algorithm under a general generative model, and provide both necessary and sufficient conditions for successful recovery of the underlying clusters. Our theoretical results cover and subsume a wide range of existing graph clustering results including planted partition, weighted clustering and partially observed graphs. Furthermore, the result is applicable to novel settings including time-varying graphs such that new insights can be gained on solving these problems. Our theoretical findings are further supported by empirical results on both synthetic and real data.

[ PDF] 

Author Information

Shiau Hong Lim (National University of Singapore)
Yudong Chen (University of Wisconsin - Madison)
Huan Xu (National University of Singapore)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors