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

MaRDI QIDQ4969043zbMATH OpenFDO

Authors Tengyuan Liang, Alexander Rakhlin, T. Tony Cai

Publication date 5 October 2020

Full work available at URL https://arxiv.org/abs/1709.03907, https://jmlr.csail.mit.edu/papers/v21/18-573.html

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)

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.

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

Cites work

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

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)