A Caltech Library Service

Sharp performance bounds for graph clustering via convex optimization

Korlakai Vinayak, Ramya and Oymak, Samet and Hassibi, Babak (2014) Sharp performance bounds for graph clustering via convex optimization. In: 2014 IEEE International Conference on Acoustics, Speech and Signal Processing. IEEE , Piscataway, NJ, pp. 8297-8301. ISBN 978-1-4799-2892-7.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The problem of finding clusters in a graph arises in several applications such as social networks, data mining and computer networks. A typical, convex optimization-approach, that is often adopted is to identify a sparse plus low-rank decomposition of the adjacency matrix of the graph, with the (dense) low-rank component representing the clusters. In this paper, we sharply characterize the conditions for successfully identifying clusters using this approach. In particular, we introduce the “effective density” of a cluster that measures its significance and we find explicit upper and lower bounds on the minimum effective density that demarcates regions of success or failure of this technique. Our conditions are in terms of (a) the size of the clusters, (b) the denseness of the graph, and (c) regularization parameter of the convex program. We also present extensive simulations that corroborate our theoretical findings.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle
Korlakai Vinayak, Ramya0000-0003-0248-9551
Additional Information:© 2014 IEEE. The authors contributed equally. 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 (ONRN00014-08-1-0747
Schlumberger FoundationUNSPECIFIED
Subject Keywords:Graph clustering; low rank plus sparse; convex optimization; thresholds
Record Number:CaltechAUTHORS:20150106-133535671
Persistent URL:
Official Citation:Vinayak, R.K.; Oymak, S.; Hassibi, B., "Sharp performance bounds for graph clustering via convex optimization," Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference on , vol., no., pp.8297,8301, 4-9 May 2014 doi: 10.1109/ICASSP.2014.6855219 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:53217
Deposited By: Tony Diaz
Deposited On:07 Jan 2015 17:23
Last Modified:03 Oct 2019 07:48

Repository Staff Only: item control page