LEARNING SPARSE GRAPHONS AND THE GENERALIZED KESTEN-STIGUM THRESHOLD

• 成果类型: Article
• 署名作者: Abbe, Emmanuel; Li, Shuangping; Sly, Allan
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Princeton University; Princeton University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/23-AOS2262
• 发表日期: 2023
• 页码: 599-623
• 关键词: stochastic blockmodels; convergent sequences; community detection; network models; reconstruction; number

摘要

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.