Efficient inference in stochastic block models with vertex labels

Clara Stegehuis, Laurent Massoulié

Research output: Contribution to journalArticleAcademicpeer-review

19 Downloads (Pure)


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.
Original languageEnglish
JournalIEEE Transactions on Network Science and Engineering
Publication statusE-pub ahead of print/First online - 30 Apr 2019
Externally publishedYes


  • stat.ML
  • cs.LG
  • math.PR


Dive into the research topics of 'Efficient inference in stochastic block models with vertex labels'. Together they form a unique fingerprint.

Cite this