Efficient inference in stochastic block models with vertex labels

Abstract

We study the stochastic block model with two communities where vertices contain side information in the form of a vertex label. These vertex labels may have arbitrary label distributions, depending on the community memberships. We analyze a linearized version of the popular belief propagation algorithm. We show that this algorithm achieves the highest accuracy possible whenever a certain function of the network parameters has a unique fixed point. Whenever this function has multiple fixed points, the belief propagation algorithm may not perform optimally. We show that increasing the information in the vertex labels may reduce the number of fixed points and hence lead to optimality of belief propagation.

References in corpus (8)

• Phase transition in the detection of modules in sparse networks
• Statistical and computational phase transitions in spiked tensor estimation
• Phase transitions in semisupervised clustering of sparse networks
• Typology of phase transitions in Bayesian inference problems
• Fundamental limits of low-rank matrix estimation: the non-symmetric case
• Non-Reconstructability in the Stochastic Block Model
• Community detection with nodal information
• Detection limits in the high-dimensional spiked rectangular model

Cited by in corpus (1)

• Mutual Information in Community Detection with Covariate Information and Correlated Networks