We look at the following problem: given an unweighted graph, organize the nodes nto disjoint clusters so that there is (relatively) dense connectivity within clusters, and sparse across clusters. This problem arises in fields as diverse as bio-informatics, VLSI layout optimization and social network analysis. Often, an added complication is that we do not observe the entire graph - i.e. for some pairs of nodes we do not know if there is an edge or not.

We formulate the problem as one of finding the clustering that has the minimum number of observed "disagreements" - edges between clusters, or missing edges within clusters. This has the advantage of not requiring any extraneous a-priori inputs (e.g. the number of clusters). We show that this problem can be reduced to (partially observed) sparse and low-rank matrix decomposition; however, the special structure of this problem allows us to prove much tighter guarantees on when convex optimization can achieve the optimal clustering.