Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
GGNNs : Generalizing GNNs using Residual Connections and Weighted Message Passing
Many real-world phenomena can be modeled as a graph, making them extremely valuable due to their ubiquitous presence. GNNs excel at capturing those relationships and patterns within these graphs, enabling effective learn…
A new look at reweighted message passing
We propose a new family of message passing techniques for MAP estimation in graphical models which we call {\em Sequential Reweighted Message Passing} (SRMP). Special cases include well-known techniques such as {\em Min-…
A Theoretical Formulation of Many-body Message Passing Neural Networks
We present many-body Message Passing Neural Network (MPNN) framework that models higher-order node interactions ($\ge 2$ nodes). We model higher-order terms as tree-shaped motifs, comprising a central node with its neigh…
SensitivityA Message Passing Algorithm for the Minimum Cost Multicut Problem
We propose a dual decomposition and linear program relaxation of the NP -hard minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut polytope, it is amenable to efficient optimization by messa…
Energy Minimization of Discrete Protein Titration State Models Using Graph Theory
There are several applications in computational biophysics which require the optimization of discrete interacting states; e.g., amino acid titration states, ligand oxidation states, or discrete rotamer angles. Such optim…