2024/11/27 by Ery Arias-Castro, Arias-Castro, Ery, Elizabeth Coda +3
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Data Management and Algorithms #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.2411.18794
openalex publication_date 2024/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.