We consider the following problem: suppose a graph is made up of a few dense, disjoint clusters, connected by a relatively sparse inter-cluster connections. Given the unlabeled (i.e. where clusters are not identified) graph, can we recover the underlying clustering ? We approach this problem via convex optimization; specifically, we first develop a semidefinite relaxation of a natural objective function: 
min (number of deviations) + \gamma (number of clusters)
For any clustering, any missing edge between nodes of the same cluster, or any edge that goes across clusters, is a deviation. 

We show that if the graph satisfies certain assumptions, then there exists a range of gamma for which our convex program recovers the true underlying clustering. Exactly equivalent to our problem is the problem of "correlation clustering"; existing results there are approximation algorithms to minimize number of deviations. Our results thus provide a new algorithm for correlation clustering, as well as a philosophically different performance guarantee.