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

Tue Dec 9th 07:00 -- 11:59 PM @ Level 2, room 210D #None

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.

Author Information

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

More from the Same Authors