Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities
This work addresses the challenge of clustering and cutting probability densities, which is incremental as it builds on graph Laplacian inequalities but introduces new definitions for the density setting.
The paper tackles the problem of relating sparse cuts of probability densities to Cheeger cuts of their principal eigenfunctions, proving Cheeger and Buser type inequalities for newly defined concepts. It results in novel algorithms for cutting densities and clustering data, including a principled variant of spectral clustering.
In this paper, we show how sparse or isoperimetric cuts of a probability density function relate to Cheeger cuts of its principal eigenfunction, for appropriate definitions of `sparse cut' and `principal eigenfunction'. We construct these appropriate definitions of sparse cut and principal eigenfunction in the probability density setting. Then, we prove Cheeger and Buser type inequalities similar to those for the normalized graph Laplacian of Alon-Milman. We demonstrate that no such inequalities hold for most prior definitions of sparse cut and principal eigenfunction. We apply this result to generate novel algorithms for cutting probability densities and clustering data, including a principled variant of spectral clustering.