Timezone: »

Graph Clustering With Missing Data: Convex Algorithms and Analysis
Ramya Korlakai Vinayak · Samet Oymak · Babak Hassibi

Mon Dec 08 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D

We consider the problem of finding clusters in an unweighted graph, when the graph is partially observed. We analyze two programs, one which works for dense graphs and one which works for both sparse and dense graphs, but requires some a priori knowledge of the total cluster size, that are based on the convex optimization approach for low-rank matrix recovery using nuclear norm minimization. For the commonly used Stochastic Block Model, we obtain \emph{explicit} bounds on the parameters of the problem (size and sparsity of clusters, the amount of observed data) and the regularization parameter characterize the success and failure of the programs. We corroborate our theoretical findings through extensive simulations. We also run our algorithm on a real data set obtained from crowdsourcing an image classification task on the Amazon Mechanical Turk, and observe significant performance improvement over traditional methods such as k-means.

Author Information

Ramya Korlakai Vinayak (University of Wisconsin-Madison)
Samet Oymak (Caltech)
Babak Hassibi (Caltech)

More from the Same Authors