Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and
  Fast Algorithms   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 guarantees on the performance of clustering
with respect to this metric when random samples are drawn from multiple
intrinsically low-dimensional clusters in high-dimensional space, in the
presence of a large number of high-dimensional outliers. By combining these
results with spectral clustering with respect to LLPD, we provide conditions
under which the Laplacian eigengap statistic correctly determines the number of
clusters for a large class of data sets, and prove guarantees on the labeling
accuracy of the proposed algorithm. Our methods are quite general and provide
performance guarantees for spectral clustering with any ultrametric. We also
introduce an efficient, easy to implement approximation algorithm for the LLPD
based on a multiscale analysis of adjacency graphs, which allows for the
runtime of LLPD spectral clustering to be quasilinear in the number of data
points.

4
The categories of this paper are: cond-mat
9
The categories of this paper are: nlin
15
The categories of this paper are: nucl-ex
5
The categories of this paper are: gr-qc
36
The categories of this paper are: cmp-lg
29
The categories of this paper are: funct-an
1
The categories of this paper are: cs
37
The categories of this paper are: supr-con
23
The categories of this paper are: solv-int
24
The categories of this paper are: dg-ga
10
The categories of this paper are: q-bio
0
The categories of this paper are: hep-ph
2
The categories of this paper are: math
11
The categories of this paper are: hep-lat
6
The categories of this paper are: astro-ph
17
The categories of this paper are: q-fin