Research map / Learning theory and algorithms / Clustering
Dynamic Similarity Graph Construction with Kernel Density Estimation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a dynamic KDE data structure that maintains (1±ε) query estimates under data insertions, and uses it to build a dynamic sparse approximate similarity graph for spectral clustering.
Problem
Kernel density estimation under data insertions (maintaining estimates for all query points), and dynamically maintaining a sparse similarity graph for graph-based clustering.
Approach
Extends the CKNS importance-sampling/LSH KDE framework with a query-hash structure that stores query points in hash buckets so that inserting a data point updates the estimates of affected query points, and a binary KDE tree with stored sample paths that resamples only affected edges when points are inserted.
Key results
- On census, the dynamic KDE algorithm reaches 836.5 s with 0.102 relative error versus 10,471.5 s for CKNS and 3,424.8 s for DynamicRS (DynamicRS has lower error 0.005 but the paper shades its fastest cases differently).
- On blobs, the dynamic similarity graph takes 21.2 s with NMI 1.000 versus 72.8 s for FullyConnected and 383.6 s for kNN.
- On cifar10, the dynamic similarity graph reaches NMI 0.339 in 1,403.5 s versus FullyConnected at 19,158.2 s with NMI 0.001.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the dynamic KDE algorithm instead of DynamicRS | Dynamic KDE · msd; covtype; glove; census | Time (s): 1,887.8{\scriptstyle \pm 0.0} -> 306.4{\scriptstyle \pm 0.0}; 309.2{\scriptstyle \pm 2.4} -> 151.7{\scriptstyle \pm 4.5} | Helped |
| Use the dynamic KDE algorithm instead of DynamicRS | Dynamic KDE · aloi | Time (s): 19.7{\scriptstyle \pm 0.3} -> 46.9{\scriptstyle \pm 0.7} | Hurt |
| Use the dynamic KDE algorithm instead of DynamicRS | Dynamic KDE · msd | Err: 5.430{\scriptstyle \pm 0.000} -> 0.388{\scriptstyle \pm 0.000} | Helped |
| Use the dynamic KDE algorithm instead of DynamicRS | Dynamic KDE · aloi; covtype; glove; census | Err: 0.010{\scriptstyle \pm 0.003} -> 0.060{\scriptstyle \pm 0.021}; 0.018{\scriptstyle \pm 0.003} -> 0.196{\scriptstyle \pm | Hurt |
| Use the dynamic similarity graph algorithm instead of FullyConnected | Dynamic similarity graph construction · blobs; cifar10 | Time (s): 72.8{\scriptstyle \pm 2.2} -> 21.2{\scriptstyle \pm 0.8}; 19,158.2{\scriptstyle \pm 231.6} -> 1,403.5{\scriptstyle \pm 1 | Helped |
| Use the dynamic similarity graph algorithm instead of FullyConnected | Dynamic similarity graph construction · mnist | Time (s): 1,328.3{\scriptstyle \pm 159.5} -> 1,470.3{\scriptstyle \pm 77.9} | Hurt |
| Use the dynamic similarity graph algorithm instead of FullyConnected | Dynamic similarity graph construction · blobs | NMI: 1.000{\scriptstyle \pm 0.000} -> 1.000{\scriptstyle \pm 0.000} | No clear effect |
| Use the dynamic similarity graph algorithm instead of FullyConnected | Dynamic similarity graph construction · cifar10; mnist | NMI: 0.001{\scriptstyle \pm 0.000} -> 0.339{\scriptstyle \pm 0.021}; 0.460{\scriptstyle \pm 0.000} -> 0.523{\scriptstyle \pm | Helped |
| Use the dynamic similarity graph algorithm instead of kNN | Dynamic similarity graph construction · blobs; cifar10; mnist | Time (s): 383.6{\scriptstyle \pm 3.9} -> 21.2{\scriptstyle \pm 0.8}; 3,503.0{\scriptstyle \pm 490.6} -> 1,403.5{\scriptstyle \pm 1 | Helped |
| Use the dynamic similarity graph algorithm instead of kNN | Dynamic similarity graph construction · cifar10 | NMI: 0.227{\scriptstyle \pm 0.002} -> 0.339{\scriptstyle \pm 0.021} | Helped |
| Use the dynamic similarity graph algorithm instead of kNN | Dynamic similarity graph construction · blobs; mnist | NMI: 0.933{\scriptstyle \pm 0.095} -> 1.000{\scriptstyle \pm 0.000}; 0.812{\scriptstyle \pm 0.003} -> 0.523{\scriptstyle \pm | Hurt |
Surprising findings
- On several datasets the dynamic KDE baseline DynamicRS (uniform sampling) is faster than the proposed algorithm, e.g., on aloi and covtype, and reaches lower error on most datasets.
- On mnist, the fully connected graph achieves the lowest runtime and NMI 0.460, while the proposed method has NMI 0.523 but is slower than FullyConnected.
Limitations
- Theoretical guarantees hold only with high probability or with probability 9/10 and depend on the assumption that the data has cluster structure.
- Experiments are on a CPU server with no GPU, and the dynamic KDE baseline DynamicRS is faster on several datasets.
- Only insertions of data points are handled for the graph; deletions are not supported in the graph construction.
Experimental setup
Datasets: blobs mnist aloi cifar10 glove msd covtype census
Benchmarks: aloi msd covtype glove census blobs cifar10 mnist
Metrics: running time (s) relative error normalised mutual information (NMI)
Baselines: Exact DynamicRS CKNS FullyConnected kNN
Builds on: CKNS fast KDE Andoni-Indyk LSH Gaussian kernel fast KDE sparsification framework
Closest papers by meaning
- Fast Approximation of Similarity Graphs with Kernel Density Estimation (NeurIPS 2023 · similarity 0.92)
- Even Faster Kernel Matrix Linear Algebra via Density Estimation (ICML 2026 · similarity 0.88)
- Fully Dynamic Coreset Spectral Clustering (ICML 2026 · similarity 0.87)
- Dynamic Spectral Clustering with Provable Approximation Guarantee (ICML 2024 · similarity 0.86)
- COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering (ICML 2025 · similarity 0.86)
- Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.