Latent structure blockmodels for Bayesian spectral graph clustering
This work addresses network analysis for researchers by introducing a novel model for clustering in graphs with manifold structures, though it is incremental as it builds on existing latent space models like RDPG.
The authors tackled the problem of graph clustering when community-specific one-dimensional manifold structures are present in spectral embeddings, proposing latent structure block models (LSBM) that correctly recover underlying communities even with unknown parametric forms, achieving remarkable results on simulated and real-world data.
Spectral embedding of network adjacency matrices often produces node representations living approximately around low-dimensional submanifold structures. In particular, hidden substructure is expected to arise when the graph is generated from a latent position model. Furthermore, the presence of communities within the network might generate community-specific submanifold structures in the embedding, but this is not explicitly accounted for in most statistical models for networks. In this article, a class of models called latent structure block models (LSBM) is proposed to address such scenarios, allowing for graph clustering when community-specific one dimensional manifold structure is present. LSBMs focus on a specific class of latent space model, the random dot product graph (RDPG), and assign a latent submanifold to the latent positions of each community. A Bayesian model for the embeddings arising from LSBMs is discussed, and shown to have a good performance on simulated and real world network data. The model is able to correctly recover the underlying communities living in a one-dimensional manifold, even when the parametric form of the underlying curves is unknown, achieving remarkable results on a variety of real data.