Fast Approximation of Similarity Graphs with Kernel Density Estimation
Peter Macgregor He Sun
Constructing a similarity graph from a set $X$ of data points in
$\mathbb{R}^d$ is the first step of many modern clustering algorithms. However,
typical constructions of a similarity graph have high time complexity, and a
quadratic space dependency with respect to $|X|$. We address this limitation
and present a new algorithmic framework that constructs a sparse approximation
of the fully connected similarity graph while preserving its cluster structure.
Our presented algorithm is based on the kernel density estimation problem, and
is applicable for arbitrary kernel functions. We compare our designed algorithm
with the well-known implementations from the scikit-learn library and the FAISS
library, and find that our method significantly outperforms the implementation
from both libraries on a variety of datasets.