Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding

In many problems arising in the natural sciences, technology, business and politics, it is crucial to understand the specific connections among the objects under study: for example, the interactions between members of a political party; the firing of synapses in a neuronal network; or citation patterns in reference literature. Mathematically, these objects and their connections are modeled as graphs, and a common goal is to find clusters of similar vertices within a graph. Both model-based and heuristic-based techniques have been proposed for clustering the vertices in a graphs [14, 2, 5, 19]. In this paper we focus on probabilistic performance guarantees for spectral-based techniques which 1 have elements of both model-and heuristic-based methods [18, 20]. We study the consistency of mean squared error clustering via the adjacency spectral embedding for three nested classes of models, each an examples of latent position models [7]: - the stochastic blockmodel where vertices in the same cluster are stochastically equivalent [8], - the degree-corrected stochastic blockmodel where stochastic equivalence holds up to a scaling factor [9], - and the random dot product graph where a natural vertex clustering may not exist [27].