  DBSCAN is a popular density-based clustering algorithm. It computes the
$\epsilon$-neighborhood graph of a dataset and uses the connected components of
the high-degree nodes to decide the clusters. However, the full neighborhood
graph may be too costly to compute with a worst-case complexity of $O(n^2)$. In
this paper, we propose a simple variant called SNG-DBSCAN, which clusters based
on a subsampled $\epsilon$-neighborhood graph, only requires access to
similarity queries for pairs of points and in particular avoids any complex
data structures which need the embeddings of the data points themselves. The
runtime of the procedure is $O(sn^2)$, where $s$ is the sampling rate. We show
under some natural theoretical assumptions that $s \approx \log n/n$ is
sufficient for statistical cluster recovery guarantees leading to an $O(n\log
n)$ complexity. We provide an extensive experimental analysis showing that on
large datasets, one can subsample as little as $0.1\%$ of the neighborhood
graph, leading to as much as over 200x speedup and 250x reduction in RAM
consumption compared to scikit-learn's implementation of DBSCAN, while still
maintaining competitive clustering performance.
