# Dynamic Similarity Graph Construction with Kernel Density Estimation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2025.

## Abstract (arXiv)

In the kernel density estimation (KDE) problem, we are given a set X of data points in ℝd, a kernel function k: ℝd × ℝd rightarrow ℝ, and a query point q ∈ ℝd, and the objective is to quickly output an estimate of sumx ∈ X k(q, x). In this paper, we consider textsfKDE in the dynamic setting, and introduce a data structure that efficiently maintains the estimates for a set of query points as data points are added to X over time. Based on this, we design a dynamic data structure that maintains a sparse approximation of the fully connected similarity graph on X, and develop a fast dynamic spectral clustering algorithm. We further evaluate the effectiveness of our algorithms on both synthetic and real-world datasets.