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

A hill-climbing algorithm is typically understood as an algorithm that makes'local' moves. In a sense, this class of procedures is the discrete analog of the class of gradient-based and higher-order methods in continuous optimization. Such algorithms have been proposed in the context of graph partitioning, sometimes as a refinement step, where the objective function is typically a notion of cut and local moves often take the form of swapping vertices in order to improve the value of the objective function. More specifically, consider an undirected graph consisting of n nodes, which we take to be [n]:= {1,..., n} without loss of generality, and adjacency matrix A = (a