On the joint recovery of community structure and community features

Abstract

We study the problem of recovering both K communities and their features from a labeled graph observation. We assume that the edges of an observed graph are generated as per the symmetric Stochastic Block Model (SBM), and that the label of each node is a noisy and partially-observed version of the corresponding community feature. We characterize the information-theoretic limit of this problem, and then propose a computationally efficient algorithm that achieves the information-theoretic limit.