Small-Variance Asymptotics for Nonparametric Bayesian Overlapping Stochastic Blockmodels
This work addresses the inference bottleneck for researchers and practitioners using nonparametric Bayesian overlapping stochastic blockmodels, offering a faster alternative to MCMC methods, though it is incremental as it builds on existing LFRM foundations.
The paper tackles the challenge of slow and convergence-prone MCMC inference in the Latent Feature Relational Model (LFRM) for graph-structured data by developing a small-variance asymptotics framework, resulting in deterministic algorithms that are competitive in performance and much faster, as demonstrated on benchmark datasets.
The latent feature relational model (LFRM) is a generative model for graph-structured data to learn a binary vector representation for each node in the graph. The binary vector denotes the node's membership in one or more communities. At its core, the LFRM miller2009nonparametric is an overlapping stochastic blockmodel, which defines the link probability between any pair of nodes as a bilinear function of their community membership vectors. Moreover, using a nonparametric Bayesian prior (Indian Buffet Process) enables learning the number of communities automatically from the data. However, despite its appealing properties, inference in LFRM remains a challenge and is typically done via MCMC methods. This can be slow and may take a long time to converge. In this work, we develop a small-variance asymptotics based framework for the non-parametric Bayesian LFRM. This leads to an objective function that retains the nonparametric Bayesian flavor of LFRM, while enabling us to design deterministic inference algorithms for this model, that are easy to implement (using generic or specialized optimization routines) and are fast in practice. Our results on several benchmark datasets demonstrate that our algorithm is competitive to methods such as MCMC, while being much faster.