提出一种基于度数爬升的图聚类方法，能有效发现数据密度的吸引域结构。
Graph Max Shift: A Hill-Climbing Method for Graph Clustering
- 通过节点向邻接度最高点迭代迁移实现聚类
- 在满足莫尔斯正则性的随机几何图上具渐近一致性
- 适合用于高维数据密度结构探测，如流形学习
我们提出一种图聚类方法，其思想类似于空间点聚类中的梯度上升法。该算法可视为在图上进行最大度数的爬升过程，迭代地将每个节点移动到邻接度最高的邻居节点。当应用于节点对应于从具有莫尔斯正则性密度中独立同分布采样数据的随机几何图时，该方法具有渐近一致性。此处的一致性依据福库纳加与霍斯特勒的定义，指算法所识别的划分与密度梯度流的吸引域分区一致。
原文摘要 · Abstract (English)
We present a method for graph clustering that is analogous to gradient ascent methods previously proposed for clustering points in space. The algorithm, which can be viewed as a max-degree hill-climbing procedure on the graph, iteratively moves each node to a neighboring node of highest degree. We show that, when applied to a random geometric graph whose nodes correspond to data drawn i.i.d. from a density with Morse regularity, the method is asymptotically consistent. Here, consistency is in the sense of Fukunaga and Hostetler, meaning, with respect to the partition of the support of the density defined by the basins of attraction of the density gradient flow.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。