Fast Approximation of Similarity Graphs with Kernel Density Estimation

Dec 10, 2023



Constructing a similarity graph from a set X of data points in ℝ^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 the both libraries on a variety of datasets.


Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 2 viewers voted for saving the presentation to eternal vault which is 0.2%


Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow NeurIPS 2023