A Caltech Library Service

Graph Clustering With Missing Data: Convex Algorithms and Analysis

Korlakai Vinayak, Ramya and Oymak, Samet and Hassibi, Babak (2014) Graph Clustering With Missing Data: Convex Algorithms and Analysis. In: Advances in Neural Information Processing Systems 27 (NIPS 2014). Advances in Neural Information Processing Systems. No.27. Neural Information Processing Systems , La Jolla, CA.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Korlakai Vinayak, Ramya0000-0003-0248-9551
Additional Information:© 2014 Neural Information Processing Systems. The authors thank the anonymous reviewers for their insightful comments. This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CIF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747, and by a grant from Qualcomm Inc. The first author is also supported by the Schlumberger Foundation Faculty for the Future Program Grant.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0747
Schlumberger FoundationUNSPECIFIED
Series Name:Advances in Neural Information Processing Systems
Issue or Number:27
Record Number:CaltechAUTHORS:20160401-170949281
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65864
Deposited By: Kristin Buxton
Deposited On:04 Apr 2016 23:11
Last Modified:03 Oct 2019 09:51

Repository Staff Only: item control page