Clustering fully and partially observable graphs via nonconvex optimization

The problem of clustering unweighted graphs either in the case of fully or partially observable adjacency matrices is considered in this paper. Both these subproblems have been recently considered in the literature and have been tackled based on convex optimization techniques related to the problems of matrix completion and robust principal component analysis that fall into the general compressive sensing framework. We revisit these approaches and extend them by proposing ways to obtain more accurate clustering results based on better approximations for the l0-norm of a matrix than the l1-norm. The current state-of-art methods correspond to special instances of the proposed extensions. Although nonconvex, the proposed methods can be approximately decomposed into sequences of l1-norm minimization problems, thus pertaining the efficiency of convex formulations. The methods are compared using graphs that are built upon the classical stochastic blockmodel. These comparisons provide a good indication that the proposed methods can improve the accuracy of state-of-art clustering methods applied to currently popular applications such as that of community detection in social networks.