Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results

Detecting communities in networks has received a large amount of attention and has found numerous applications across various disciplines including physics, sociology, biology, statistics, computer science, etc (see the exposition [13] and the references therein). Most previous work assumes networks can be divided into groups of nodes with dense connections internally and sparser connections between groups, and considers random graph models with some underlying cluster structure such as the stochastic blockmodel (SBM), a.k.a. the planted partition model. In its simplest form, nodes are partitioned into clusters, and any two nodes are connected by an edge independently at random with probability p if they are in the same cluster and with probability q otherwise. The problem of cluster recovery under the SBM has been extensively studied and many efficient algorithms with provable performance guarantees have been developed (see e.g., [8] and the references therein). Real networks, however, may not display a clustered structure; the goal of community detection should then be redefined. As observed in [15], interactions in many real networks can be of various types and prediction of unknown interaction types may have practical merit such as prediction of missing ratings in recommender systems. Therefore an intriguing question arises: Can we accurately predict the unknown interaction types in the absence of a clustered structure? To answer it, we generalize the SBM by relaxing the cluster assumption and allowing edges to carry labels.