Efficient inference in stochastic block models with vertex labels
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic Block ModelSimilar Papers 제목 키워드 기반
Robust Vertex Classification
For random graphs distributed according to stochastic blockmodels, a special case of latent position graphs, adjacency spectral embedding followed by appropriate vertex classification is asymptotically Bayes optimal; but…
ClassificationGeneral ClassificationPositionInformation Recovery in Shuffled Graphs via Graph Matching
While many multiple graph inference methodologies operate under the implicit assumption that an explicit vertex correspondence is known across the vertex sets of the graphs, in practice these correspondences may only be …
ClusteringGraph ClusteringGraph MatchingSpectral Graph Clustering+1On spectral algorithms for community detection in stochastic blockmodel graphs with vertex covariates
In network inference applications, it is often desirable to detect community structure, namely to cluster vertices into groups, or blocks, according to some measure of similarity. Beyond mere adjacency matrices, many rea…
ClusteringCommunity DetectionLost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels
Two-sample network hypothesis testing is an important inference task with applications across diverse fields such as medicine, neuroscience, and sociology. Many of these testing methodologies operate under the implicit a…
SociologyStochastic Block ModelVertex nomination: The canonical sampling and the extended spectral nomination schemes
Suppose that one particular block in a stochastic block model is of interest, but block labels are only observed for a few of the vertices in the network. Utilizing a graph realized from the model and the observed block …
ClusteringStochastic Block Model