Continuum Limits and Graph Cuts for Fermat Graph Laplacians
Fermat distances are an optimal path metric which balance density-based and geometric information present in data. Graph Laplacians constructed with Fermat distance provide a useful tool for obtaining sparse graph cuts, for dealing with elongated data structures, and for automatically detecting the number of clusters. As the sample size converges to infinity, the spectrum of the discrete Fermat Graph Laplacian converges to the spectrum of a continuum Kolmogorov operator which generates a diffusion on the associated manifold. Unlike the Euclidean case where the diffusion occurs at a constant speed, the resulting diffusion is accelerated in regions of high density, allowing for the rapid exploration of elongated data structures. This talk will discuss some of the desirable properties of Fermat Graph Laplacians and highlight how the continuum limit provides a theoretical framework for understanding these properties. In addition, these metrics can be efficiently computed by restricting to a sparse graph.