Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information

zbMATH Open1497.68413arXiv1709.03907MaRDI QIDQ4969043FDOQ4969043

Authors: Tengyuan Liang, Alexander Rakhlin, T. Tony Cai 

Publication date: 5 October 2020

Abstract: We study the misclassification error for community detection in general heterogeneous stochastic block models (SBM) with noisy or partial label information. We establish a connection between the misclassification rate and the notion of minimum energy on the local neighborhood of the SBM. We develop an optimally weighted message passing algorithm to reconstruct labels for SBM based on the minimum energy flow and the eigenvectors of a certain Markov transition matrix. The general SBM considered in this paper allows for unequal-size communities, degree heterogeneity, and different connection probabilities among blocks. We focus on how to optimally weigh the message passing to improve misclassification.

Full work available at URL: https://arxiv.org/abs/1709.03907

Recommendations

• Optimal rates for community estimation in the weighted stochastic block model
• Community detection and stochastic block models
• Weighted stochastic block model
• Weighted community detection and data clustering using message passing
• Community detection and stochastic block models: recent developments

zbMATH Keywords

misclassificationstatistical inferencesemi-supervised learninggeneral stochastic block modelsminimum energy flowweighted message passing

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• A proof of the block model threshold conjecture
• Convexified modularity maximization for degree-corrected stochastic block models
• Spectral redemption in clustering sparse networks
• Mixed membership stochastic blockmodels
• Belief propagation, robust reconstruction and optimal recovery of block models
• Title not available (Why is that?)
• Community detection thresholds and the weak Ramanujan property
• Introduction to nonparametric estimation
• Fast community detection by SCORE
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Exact Recovery in the Stochastic Block Model
• Community detection in sparse networks via Grothendieck's inequality
• Finding one community in a sparse graph
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Probability on trees and networks
• Locality in Distributed Graph Algorithms
• Broadcasting on trees and the Ising model.
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
• Information flow on trees
• Reconstruction on trees: Beating the second eigenvalue
• Geometric inference for general high-dimensional linear inverse problems
• The small-world phenomenon: an algorithmic perspective
• Universality in polytope phase transitions and message passing algorithms
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Robust phase transitions for Heisenberg and other models on general trees
• Graph partitioning via adaptive spectral techniques
• A Limit Theorem for Multidimensional Galton-Watson Processes
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Limits of local algorithms over sparse random graphs
• Robust reconstruction on trees is determined by the second eigenvalue.
• Proof of the achievability conjectures for the general stochastic block model
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• Asymptotic mutual information for the balanced binary stochastic block model
• Group synchronization on grids
• Community detection on Euclidean random graphs
• Global and local information in clustering labeled block models

Cited In (2)

• Optimal rates for community estimation in the weighted stochastic block model
• Weighted community detection and data clustering using message passing

This page was built for publication: Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4969043)