Multi-Community Spectral Clustering for Geometric Graphs

In this paper, we consider the soft geometric block model (SGBM) with a fixed number k ≥ 2 of homogeneous communities in the dense regime, and we introduce a spectral clustering algorithm for community recovery on graphs generated by this model. Given such a graph, the algorithm produces an embedding into ℝk-1 using the eigenvectors associated with the k-1 eigenvalues of the adjacency matrix of the graph that are closest to a value determined by the parameters of the model. It then applies k-means clustering to the embedding. We prove weak consistency and show that a simple local refinement step ensures strong consistency. A key ingredient is an application of a non-standard version of Davis-Kahan theorem to control eigenspace perturbations when eigenvalues are not simple. We also analyze the limiting spectrum of the adjacency matrix, using a combination of combinatorial and matrix techniques.