Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence

Abstract

We derive sharp thresholds for exact recovery of communities in a weighted stochastic block model, where observations are collected in the form of a weighted adjacency matrix, and the weight of each edge is generated independently from a distribution determined by the community membership of its endpoints. Our main result, characterizing the precise boundary between success and failure of maximum likelihood estimation when edge weights are drawn from discrete distributions, involves the Renyi divergence of order $\frac{1}{2}$ between the distributions of within-community and between-community edges. When the Renyi divergence is above a certain threshold, meaning the edge distributions are sufficiently separated, maximum likelihood succeeds with probability tending to 1; when the Renyi divergence is below the threshold, maximum likelihood fails with probability bounded away from 0. In the language of graphical channels, the Renyi divergence pinpoints the information-theoretic capacity of discrete graphical channels with binary inputs. Our results generalize previously established thresholds derived specifically for unweighted block models, and support an important natural intuition relating the intrinsic hardness of community estimation to the problem of edge classification. Along the way, we establish a general relationship between the Renyi divergence and the probability of success of the maximum likelihood estimator for arbitrary edge weight distributions. Finally, we discuss consequences of our bounds for the related problems of censored block models and submatrix localization, which may be seen as special cases of the framework developed in our paper.

32 pages

References in corpus (6)

• Fast unfolding of communities in large networks
• Community Detection in the Labelled Stochastic Block Model
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model

Cited by in corpus (18)

• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Optimal hypothesis testing for stochastic block models with growing degrees
• Explicitly Linking Regional Activation and Function Connectivity: Community Structure of Weighted Networks with Continuous Annotation
• MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
• Community Recovery in Graphs with Locality
• Optimal Cluster Recovery in the Labeled Stochastic Block Model
• Clustering from Sparse Pairwise Measurements
• Two-sample Test of Community Memberships of Weighted Stochastic Block Models
• Optimal Rates for Community Estimation in the Weighted Stochastic Block Model
• On the Minimax Misclassification Ratio of Hypergraph Community Detection
• Community Detection with Contextual Multilayer Networks
• Clustering in Block Markov Chains
• Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
• Exact Recovery in the General Hypergraph Stochastic Block Model
• Information-theoretic Limits for Community Detection in Network Models
• Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model
• Uniform Consistency in Stochastic Block Model with Continuous Community Label
• Community Detection with Colored Edges