Model selection and latent substructure inference in spectral graph clustering

Abstract

Spectral clustering is a popular method for community detection in networks. The nodes are clustered on a low dimensional representation of the graph, called spectral embedding, resulting from a truncated spectral decomposition of the adjacency matrix or one of its regularised versions. One of the main limitations of standard algorithms for community detection from spectral embeddings is that the number of communities and the latent dimension of the embedding must be specified in advance. Estimating the number of communities and the dimensionality of the reduced latent space is crucial for a good performance of the spectral clustering algorithm. In this talk, novel model-based methods for simultaneous and automated selection of the number of communities and latent dimensionality in spectral clustering under the stochastic blockmodel (SBM) and its degree-corrected version (DCSBM) are proposed. Furthermore, a more general class of models, called latent structure block models (LSBM), is proposed to address the more general case of community-specific sub-manifold structures in the embedding. LSBMs focus on a special case of a latent space model, the random dot product graph (RDPG), and assign a latent subspace to the latent positions of each community, admitting the SBM and DCSBM as special cases. Results show improved performance over competing methods on simulated and real-world computer network data.

 L’Organizzatore                                                                                                     Il Direttore                      

Prof. Alessandra Luati                                                                                 Prof. Carlo Trivisano

                                                                    La S.V. è invitata