Graph Max Shift: A Hill-Climbing Method for Graph Clustering

Ery Arias-Castro, Elizabeth Coda, Wanli Qiao
11/27/2024
stat.MLcs.LG

No official code found. Best implementation: lizzycoda/GraphMaxShift (0 stars, last commit 2024-12-02).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

lizzycoda/GraphMaxShiftCommunity100%
01Python, Jupyter NotebookAug 22, 20241 years ago

Similar Papers

Learning Uniform Clusters on Hypersphere for Deep Graph-level Clustering

81% match2023

Optimal Graph Clustering without Edge Density Signals

81% match1 repo2025

Locally Regularized Sparse Graph by Fast Proximal Gradient Descent

80% match2024

Advanced Graph Clustering Methods: A Comprehensive and In-Depth Analysis

80% match1 repo62024

Cluster Catch Digraphs with the Nearest Neighbor Distance

80% match2025

Contrastive Graph Clustering in Curvature Spaces

80% match2023

Cite this paper

@article{ariascastro2024graph,
  title  = {Graph Max Shift: A Hill-Climbing Method for Graph Clustering},
  author = {Ery Arias-Castro and Elizabeth Coda and Wanli Qiao},
  year   = {2024},
  eprint = {2411.18794},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2411.18794v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2411.18794.svg)](https://codeofpaper.com/paper/2411.18794)

Discussion