# Fast Approximation of Similarity Graphs with Kernel Density Estimation

arXiv: https://arxiv.org/abs/2310.13870 · HTML: https://mlsanity.com/paper/2310.13870/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 21 Oct 2023.

## Builds on (most cited first, 12 of 12)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Kernel Density Estimation through Density Constrained Near Neighbor Search](https://mlsanity.com/paper/2011.06997/) (2020)
- [Algorithms and Hardness for Linear Algebra on Geometric Graphs](https://mlsanity.com/paper/2011.02466/) (2020)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Distributed Graph Clustering and Sparsification](https://mlsanity.com/paper/1711.01262/) (2017)
- [An SDP-Based Algorithm for Linear-Sized Spectral Sparsification](https://mlsanity.com/paper/1702.08415/) (2017)
- [Spectral Toolkit of Algorithms for Graphs: Technical Report (1)](https://mlsanity.com/paper/2304.03170/) (2023)
- [Efficient Interpolation of Density Estimators](https://mlsanity.com/paper/2011.04922/) (2020)

## Built on by (most cited first, 3 of 3)

- [Mini-Batch Kernel k-means](https://mlsanity.com/paper/2410.05902/) (2024)
- [Spectral Toolkit of Algorithms for Graphs: Technical Report (2)](https://mlsanity.com/paper/2407.07096/) (2024)
- [Coreset Spectral Clustering](https://mlsanity.com/paper/2503.07227/) (2025)

## Abstract (arXiv)

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 both libraries on a variety of datasets.