Graph Max Shift: A Hill-Climbing Method for Graph Clustering
This work addresses graph clustering for data analysis, but it appears incremental as it adapts existing spatial methods to graphs with theoretical guarantees.
The authors tackled the problem of graph clustering by proposing a hill-climbing method analogous to gradient ascent for spatial data, showing that it achieves asymptotic consistency on random geometric graphs with Morse-regular densities, where consistency aligns with density-level clustering based on basins of attraction of density modes.
We present a method for graph clustering that is analogous with gradient ascent methods previously proposed for clustering points in space. We show that, when applied to a random geometric graph with data iid from some density with Morse regularity, the method is asymptotically consistent. Here, consistency is understood with respect to a density-level clustering defined by the partition of the support of the density induced by the basins of attraction of the density modes.