Clustering is the most commonly used unsupervised learning method. In many recent
applications, datasets have a graph structure, e.g., social networks,
proteien-protein interaction networks etc. In most practical scenarios, it
is too expensive to observe the entire graph. We consider the problem of
finding clusters in graphs that are partially observed. We analyze two convex
programs based on regularized nuclear norm minimization, with a goal to recover
the low-rank part of the adjacency matrix. For the commonly used Stochastic
Block Model, we provide explicit conditions in terms of the size and sparsity
of the clusters, amount of observed data, and the regularization parameter of
the convex program that guarantees successful recovery of the clusters. 

We apply the setting of graph clustering with missing data to the problem of
crowdsourced clustering. Consider the task of clustering unlabeled items using
answers from non-expert crowd workers, for example, clustering a database of
images of birds into different species with the collective help of workers who
are not experts in bird classification. In such cases, the workers are often
not able to label the images directly, however, it is reasonable to assume that
they can compare items and judge whether they are of same species or not. As the
workers are not experts, the answers obtained are noisy. Since it is far too
expensive to make all possible queries, we need to work with partial
observations subject to a fixed query budget constraint. It is crucial to
design queries that can reduce the noise levels in the responses, and to design
algorithms to reliably cluster the noisy data. We compare two types of random
queries: edge queries, where a pair of items is revealed, and triangles, where
a triple is. Under natural modeling assumptions, we show that triangle queries
provide more reliable answers than edge queries. We also provide sufficient
conditions required for the exact recovery of the true adjacency matrix via
triangle queries using convex algorithm. We complement our theoretical results
with experiments on real datasets on Amazon Mechanical Turk. Our experiments
suggest that the triangle queries not only provide more reliable edges but also
reveal many more of them for a fixed budget and using convex algorithms to
denoise the observed data substantially reduces the number of errors in
clustering.