Fast Approximation of Similarity Graphs with Kernel Density Estimation

Peter Macgregor, He Sun

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Constructing a similarity graph from a set X of data points in 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.
Original languageEnglish
Title of host publication37th Conference on Neural Information Processing Systems (NeurIPS 2023)
PublisherCurran Associates Inc
Pages67603-67624
Number of pages22
Volume36
Publication statusPublished - 15 Dec 2023
EventThirty-Seventh Conference on Neural Information Processing Systems - New Orleans Ernest N. Morial Convention Center, New Orleans, United States
Duration: 10 Dec 202316 Dec 2023
Conference number: 37
https://neurips.cc/Conferences/2023

Conference

ConferenceThirty-Seventh Conference on Neural Information Processing Systems
Abbreviated titleNeurIPS 2023
Country/TerritoryUnited States
CityNew Orleans
Period10/12/2316/12/23
Internet address

Fingerprint

Dive into the research topics of 'Fast Approximation of Similarity Graphs with Kernel Density Estimation'. Together they form a unique fingerprint.

Cite this