Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms

Anna Little, Mauro Maggioni, James M. Murphy

We consider the problem of clustering with the longest-leg path distance (LLPD) metric, which is informative for elongated and irregularly shaped clusters. We prove finite-sample g…