Learning Sparse Graphons And The Generalized Kesten-Stigum Threshold

The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the re-cent years in sparser regimes. Yet, the current techniques still require diverg-ing degrees in order to succeed with efficient algorithms in the challenging cases where the local structure of the graph is homogeneous. This paper pro-vides an efficient algorithm to learn graphons in the constant expected degree regime. The algorithm is shown to succeed in estimating the rank-k projec-tion of a graphon in the L2 metric if the top k eigenvalues of the graphon satisfy a generalized Kesten-Stigum condition.