From Graph Cuts to Isoperimetric Inequalities: Convergence Rates of Cheeger Cuts on Data Clouds
From Graph Cuts to Isoperimetric Inequalities: Convergence Rates of Cheeger Cuts on Data Clouds
复制标题
DOI：
10.1007/s00205-022-01770-8
复制
发表时间：
2020-04
影响因子：
2.5
通讯作者：
N. G. Trillos;Ryan W. Murray;Matthew Thorpe
中科院分区：
文献类型：
--
作者：
N. G. Trillos;Ryan W. Murray;Matthew Thorpe
在这项工作中，我们研究基于图的聚类算法的统计特性，这些算法依赖于平衡图割的优化，主要的例子是 Cheeger 割的优化。我们考虑从支持通用平滑紧凑流形的底层分布中采样的数据构建邻近图。在这种情况下，我们获得了 Cheeger 常数和相关的 Cheeger 切割向其连续体对应物的高概率收敛率。关键的技术工具是对插值算子的仔细估计，这些算子将经验 Cheeger 割提升到连续体，以及等周问题的连续体稳定性估计。据我们所知，这里获得的定量估计是同类中的第一个。
In this work we study statistical properties of graph-based clustering algorithms that rely on the optimization of balanced graph cuts, the main example being the optimization of Cheeger cuts. We consider proximity graphs built from data sampled from an underlying distribution supported on a generic smooth compact manifold. In this setting, we obtain high probability convergence rates for both the Cheeger constant and the associated Cheeger cuts towards their continuum counterparts. The key technical tools are careful estimates of interpolation operators which lift empirical Cheeger cuts to the continuum, as well as continuum stability estimates for isoperimetric problems. To the best of our knowledge the quantitative estimates obtained here are the first of their kind.