Fast Approximation of Similarity Graphs with Kernel Density Estimation He Sun School of Informatics School of Informatics University of Edinburgh University of Edinburgh United Kingdom

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.