Manifold Regularized Stochastic Block Model

Stochastic block models (SBMs) play essential roles in network analysis, especially in those related to unsupervised learning (clustering). Many SBM-based approaches have been proposed to uncover network clusters, by means of maximizing the block-wise posterior probability that generates edges bridging vertices. However, none of them is capable of inferring the cluster preference for each vertex through simultaneously modeling block-wise edge structure, vertex features, and similarities between pairwise vertices. To fill this void, we propose a novel SBM dubbed manifold regularized stochastic model (MrSBM) to perform the task of unsupervised learning in network data in this paper. Besides modeling edges that are within or connecting blocks, MrSBM also considers modeling vertex features utilizing the probabilities of vertex-cluster preference and feature-cluster contribution. In addition, MrSBM attempts to generate manifold similarity of pairwise vertices utilizing the inferred vertex-cluster preference. As a result, the inference of cluster preference may well capture the comparability in the manifold. We design a novel process for network data generation, based on which, we specify the model structure and formulate the network clustering problem using a novel likelihood function. To guarantee MrSBM learns the optimal cluster preference for each vertex, we derive an effective Expectation-Maximization based algorithm for model fitting. MrSBM has been tested on five sets of real-world network data and has been compared with both classical and state-of-the-art approaches to network clustering. The competitive experimental results validate the effectiveness of MrSBM.