Breaking the Small Cluster Barrier of Graph Clustering


Nir Ailon, Yudong Chen, Huan Xu ;
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):995-1003, 2013.


This paper investigates graph clustering in the planted cluster model in the presence of \em small clusters. Traditional results dictate that for an algorithm to provably correctly recover the clusters, \em all clusters must be sufficiently large (in particular, \tildeΩ(\sqrtn) where n is the number of nodes of the graph). We show that this is not really a restriction: by a more refined analysis of the trace-norm based matrix recovery approach proposed in (Jalali et al. 2011) and (Chen et al. 2012), we prove that small clusters, under certain mild assuptions, do not hinder recovery of large ones. Based on this result, we further devise an iterative algorithm to recover \em almost all clusters via a “peeling strategy”, i.e., recover large clusters first, leading to a reduced problem, and repeat this procedure. These results are extended to the \em partial observation setting, in which only a (chosen) part of the graph is observed. The peeling strategy gives rise to an active learning algorithm, in which edges adjacent to smaller clusters are queried more often as large clusters are learned (and removed). Our findings are supported by experiments. From a high level, this paper sheds novel insights on high-dimesional statistics and learning structured data, by presenting a structured matrix learning problem for which a one shot convex relaxation approach necessarily fails, but a carefully constructed sequence of convex relaxations does the job.

Related Material