Community Detection with Side Information: Exact Recovery under the Stochastic Block Model

Abstract

The community detection problem involves making inferences about node labels in a graph, based on observing the graph edges. This paper studies the effect of additional, non-graphical side information on the phase transition of exact recovery in the binary stochastic block model (SBM) with $n$ nodes. When side information consists of noisy labels with error probability $\alpha$, it is shown that phase transition is improved if and only if $\log (\frac{1-\alpha }{\alpha })=\Omega (\log (n))$. When side information consists of revealing a fraction $1-\epsilon$ of the labels, it is shown that phase transition is improved if and only if $\log (1/\epsilon )=\Omega (\log (n))$. For a more general side information consisting of $K$ features, two scenarios are studied: (1)~$K$ is fixed while the likelihood of each feature with respect to corresponding node label evolves with $n$, and (2)~The number of features $K$ varies with $n$ but the likelihood of each feature is fixed. In each case, we find when side information improves the exact recovery phase transition and by how much. The calculated necessary and sufficient conditions for exact recovery are tight except for one special case. In the process of deriving inner bounds, a variation of an efficient algorithm is proposed for community detection with side information that uses a partial recovery algorithm combined with a local improvement procedure.

References in corpus (15)

• Community structure in social and biological networks
• Community detection in graphs
• Community detection algorithms: a comparative analysis
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Community Detection in Networks with Node Attributes
• Phase transition in the detection of modules in sparse networks
• Structure and inference in annotated networks
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• A Tensor Approach to Learning Mixed Membership Community Models
• Improved Graph Clustering
• Community Detection via Random and Adaptive Sampling
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Density Evolution in the Degree-correlated Stochastic Block Model
• Inference via Message Passing on Partially Labeled Stochastic Block Models

Cited by in corpus (10)

• MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
• Orthogonal Inductive Matrix Completion
• Semi-Supervised Node Classification by Graph Convolutional Networks and Extracted Side Information
• Almost exact recovery in noisy semi-supervised learning
• Active Community Detection with Maximal Expected Model Change
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• Exact Recovery in the General Hypergraph Stochastic Block Model
• Binary Classification with XOR Queries: Fundamental Limits and An Efficient Algorithm
• Community Detection and Matrix Completion with Social and Item Similarity Graphs
• EXIT Analysis for Community Detection