# Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation

arXiv: https://arxiv.org/abs/2108.08687 · HTML: https://mlsanity.com/paper/2108.08687/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 50 references that are in the map.
- First posted on arXiv 18 Aug 2021.

## Builds on (most cited first, 10 of 10)

- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [A variational approach to the consistency of spectral clustering](https://mlsanity.com/paper/1508.01928/) (2015)
- [Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation](https://mlsanity.com/paper/2006.02037/) (2020)
- [Lipschitz regularity of graph Laplacians on random data clouds](https://mlsanity.com/paper/2007.06679/) (2020)
- [Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs](https://mlsanity.com/paper/1910.13476/) (2019)
- [Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms](https://mlsanity.com/paper/1712.06206/) (2017)
- [Convergence of Graph Laplacian with kNN Self-tuned Kernels](https://mlsanity.com/paper/2011.01479/) (2020)
- [Balancing Geometry and Density: Path Distances on High-Dimensional Data](https://mlsanity.com/paper/2012.09385/) (2020)
- [The geometry of kernelized spectral clustering](https://mlsanity.com/paper/1404.7552/) (2014)
- [Geometric structure of graph Laplacian embeddings](https://mlsanity.com/paper/1901.10651/) (2019)

## Built on by (most cited first, 1 of 1)

- [Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms](https://mlsanity.com/paper/2307.05750/) (2023)

## Abstract (arXiv)

In this work we build a unifying framework to interpolate between density-driven and geometry-based algorithms for data clustering, and specifically, to connect the mean shift algorithm with spectral clustering at discrete and continuum levels. We seek this connection through the introduction of Fokker-Planck equations on data graphs. Besides introducing new forms of mean shift algorithms on graphs, we provide new theoretical insights on the behavior of the family of diffusion maps in the large sample limit as well as provide new connections between diffusion maps and mean shift dynamics on a fixed graph. Several numerical examples illustrate our theoretical findings and highlight the benefits of interpolating density-driven and geometry-based clustering algorithms.