Spectral clustering in high-dimensional Gaussian mixture block models

The Gaussian mixture block model is a simple generative model for networks: to generate a sample, we associate each node with a latent feature vector sampled from a mixture of Gaussians, and we add an edge between nodes if and only if their feature vectors are sufficiently similar. The different components of the Gaussian mixture represent the fact that there may be several types of nodes with different distributions over features — for example, in a social network each component represents the different attributes of a distinct community. In this talk I will discuss recent results on the performance of spectral clustering algorithms on networks sampled from high-dimensional Gaussian mixture block models, where the dimension of the latent feature vectors grows as the size of the network goes to infinity. Our results merely begin to sketch out the information-computation landscape for clustering in these models, and I will make an effort to emphasize open questions.
Based on joint work with Shuangping Li.