We consider a generative model for a network, namely the planted cluster model, which is a simple extension of the classical Erdos-Renyi random graph. The task is to exactly recover the planted clusters from observation of the network.
We first derive an information limit for exact cluster recovery and show it is achieved by the maximum likelihood (ML) estimation up to constant factors. We then show a convex relaxation of ML estimation can successfully recover the clusters up to a spectral barrier but fails to achieve the information limit. We conjecture no polynomial-time algorithm can succeed significantly beyond the spectral barrier and achieve the information limit. To provide evidence, we show recovering a single cluster significantly beyond the spectral barrier is at least as hard as detecting a clique of size o(sqrt(n)) planted in an Erdos-Renyi random graph with n nodes and a constant edge probability.
This work is at the intersection of information theory, machine learning, and high-dimensional statistics. Based on joint work with Yudong Chen at UC Berkeley, and Bruce Hajek, Yihong Wu from UIUC.
Jiaming Xu is a PhD candidate in the ECE department at UIUC under the supervision of Professor Bruce Hajek. He received the B.E. degree from Tsinghua University in 2009 and the M.S. degree from UT-Austin in 2011, all in ECE. His research interests are in statistical learning, queueing and game theory.