标题： 随机邻域图上的局部谱聚类的统计保证 显示英文标题

标题： Statistical Guarantees for Local Spectral Clustering on Random Neighborhood Graphs

摘要： 我们研究个性化PageRank（PPR）算法，这是一种用于聚类的局部谱方法，它通过围绕给定种子节点的局部偏差随机游走来提取聚类。 与之前的工作不同，我们采用了一种经典的统计学习设置，其中我们从一个未知的非参数分布中获取样本，并旨在识别足够显著的聚类。 我们引入了一组种群级别的泛函——归一化割、导通性和局部扩散性，它们与同名的基于图的泛函类似——并证明在邻域图上运行的PPR可以恢复具有小种群归一化割和大导通性和局部扩散性的聚类。 我们将我们的通用理论应用于证明PPR能够识别满足一组自然几何条件的高密度连通区域（密度聚类）。 我们还展示了相反的结果，即PPR即使在渐近情况下也可能无法恢复几何条件差的密度聚类。 最后，我们提供了对我们的理论的经验支持。 显示英文摘要

摘要： We study the Personalized PageRank (PPR) algorithm, a local spectral method for clustering, which extracts clusters using locally-biased random walks around a given seed node. In contrast to previous work, we adopt a classical statistical learning setup, where we obtain samples from an unknown nonparametric distribution, and aim to identify sufficiently salient clusters. We introduce a trio of population-level functionals -- the normalized cut, conductance, and local spread, analogous to graph-based functionals of the same name -- and prove that PPR, run on a neighborhood graph, recovers clusters with small population normalized cut and large conductance and local spread. We apply our general theory to establish that PPR identifies connected regions of high density (density clusters) that satisfy a set of natural geometric conditions. We also show a converse result, that PPR can fail to recover geometrically poorly-conditioned density clusters, even asymptotically. Finally, we provide empirical support for our theory.