论文标题
学习稀疏的图形和广义的凯斯滕·斯蒂格姆阈值
Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold
论文作者
论文摘要
学习图形的问题吸引了几个科学社区的大量关注，近年来在稀疏政权中取得了重大进展。然而，当前技术仍然需要分歧度，以便在图形局部结构均匀的挑战性情况下通过有效的算法取得成功。本文提供了一种有效的算法，以学习恒定的预期学位制度中的图形。如果Graphon的顶部$ K $特征值满足了广义的Kesten-Stigum条件，则该算法已显示出成功估算$ L_2 $ Metric的Graphon的排名-K $投影。
The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the recent years in sparser regimes. Yet, the current techniques still require diverging degrees in order to succeed with efficient algorithms in the challenging cases where the local structure of the graph is homogeneous. This paper provides an efficient algorithm to learn graphons in the constant expected degree regime. The algorithm is shown to succeed in estimating the rank-$k$ projection of a graphon in the $L_2$ metric if the top $k$ eigenvalues of the graphon satisfy a generalized Kesten-Stigum condition.
