Detecting Overlapping and Correlated Communities without Pure Nodes: Identifiability and Algorithm

Many machine learning problems come in the form of networks with relational data between entities, and one of the key unsupervised learning tasks is to detect communities from such a network. We adopt the mixed-membership stochastic blockmodel as the underlying probabilistic model, and give conditions under which the membership of a subset of nodes can be uniquely identified. Our method start by constructing a second-order graph moment, which can be shown to converge to a specific product of the true parameters as the size of the network increases. To correctly recover the true membership parameters, we carefully formulate an optimization problem using insights from convex geometry. We show that if the true memberships satisfy a so called sufficiently scattered condition, then solving the proposed problem correctly identifies the ground truth. We also develop an extremely efficient algorithm, which is significantly faster than prior work and with better convergence properties. Experiments on synthetic and real data justify the effectiveness of the proposed learning framework for network data.