Graph Clustering Dynamics: From Spectral to Mean Shift

Katy Craig (University of California, Santa Barbara)

Clustering algorithms based on mean shift or spectral methods on graphs are ubiquitous in data analysis. However, in practice, these two types of algorithms are treated as conceptually disjoint: mean shift clusters based on the density of a dataset, while spectral methods allow for clustering based on geometry. In joint work with Nicolás García Trillos and Dejan Slepčev, we define a new notion of Fokker-Planck equation on graph and use this to introduce an algorithm that interpolates between mean shift and spectral approaches, enabling it to cluster based on both the density and geometry of a dataset. We illustrate the benefits of this approach in numerical examples and contrast it with Coifman and Lafon’s well-known method of diffusion maps, which can also be thought of as a Fokker-Planck equation on a graph, though one that degenerates in the zero diffusion limit.

Katy Craig is an assistant professor at the University of California, Santa Barbara, specializing in partial differential equations and optimal transport. She received her PhD from Rutgers University in 2014, after which she spent one year at UCLA as an NSF Mathematical Sciences Postdoctoral Fellow and one year at UCSB as an UC President’s Postdoctoral Fellow.