Dynamic similarity graph construction with kernel density estimation

Steinar Laenen; Peter Macgregor; He Sun

Dynamic similarity graph construction with kernel density estimation

Steinar Laenen, Peter Macgregor, He Sun^*

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In the kernel density estimation (KDE) problem, we are given a set X of data points in ℝ^d, a kernel function k : ℝ^d × ℝ^d → ℝ, and a query point q ∈ ℝ^d, and the objective is to quickly output an estimate of ∑_x∈X k(q,x). In this paper, we consider KDE 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.

Original language	English
Title of host publication	Proceedings of the 42nd international conference on machine learning
Editors	Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, Jerry Zhu
Publisher	PMLR
Pages	32130-32163
Number of pages	34
Publication status	Published - 1 Oct 2025
Event	42nd International Conference on Machine Learning - Vancouver Convention Center, Vancouver, Canada Duration: 13 Jul 2025 → 19 Jul 2025 https://icml.cc/Conferences/2025

Publication series

Name	Proceedings of machine learning research
Volume	267
ISSN (Print)	2640-3498

Conference

Conference	42nd International Conference on Machine Learning
Abbreviated title	ICLM 2025
Country/Territory	Canada
City	Vancouver
Period	13/07/25 → 19/07/25
Internet address	https://icml.cc/Conferences/2025

Access to Document

Laenen_2026_ICML_Dynamic-similarity-graph-construction_CC
© 2025 The Authors. Published under a Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0).
Final published version, 992 KBLicence: CC BY

https://proceedings.mlr.press/v267/laenen25a.htmlLicence: CC BY
https://openreview.net/forum?id=stgw28KnaXLicence: CC BY

Cite this

Laenen, S., Macgregor, P., & Sun, H. (2025). Dynamic similarity graph construction with kernel density estimation. In A. Singh, M. Fazel, D. Hsu, S. Lacoste-Julien, F. Berkenkamp, T. Maharaj, K. Wagstaff, & J. Zhu (Eds.), Proceedings of the 42nd international conference on machine learning (pp. 32130-32163). (Proceedings of machine learning research; Vol. 267). PMLR. https://proceedings.mlr.press/v267/laenen25a.html

Laenen, Steinar ; Macgregor, Peter ; Sun, He. / Dynamic similarity graph construction with kernel density estimation. Proceedings of the 42nd international conference on machine learning. editor / Aarti Singh ; Maryam Fazel ; Daniel Hsu ; Simon Lacoste-Julien ; Felix Berkenkamp ; Tegan Maharaj ; Kiri Wagstaff ; Jerry Zhu. PMLR, 2025. pp. 32130-32163 (Proceedings of machine learning research).

@inproceedings{2d7b8b7c28a84562b93635f0a657b376,

title = "Dynamic similarity graph construction with kernel density estimation",

abstract = "In the kernel density estimation (KDE) problem, we are given a set X of data points in ℝd, a kernel function k : ℝd × ℝd → ℝ, and a query point q ∈ ℝd, and the objective is to quickly output an estimate of ∑x∈X k(q,x). In this paper, we consider KDE 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.",

author = "Steinar Laenen and Peter Macgregor and He Sun",

note = "Funding: The third author of the paper is supported by an EPSRC Early Career Fellowship (EP/T00729X/1).; 42nd International Conference on Machine Learning, ICLM 2025 ; Conference date: 13-07-2025 Through 19-07-2025",

year = "2025",

month = oct,

day = "1",

language = "English",

series = "Proceedings of machine learning research",

publisher = "PMLR",

pages = "32130--32163",

editor = "Aarti Singh and Maryam Fazel and Daniel Hsu and Simon Lacoste-Julien and Felix Berkenkamp and Tegan Maharaj and Kiri Wagstaff and Jerry Zhu",

booktitle = "Proceedings of the 42nd international conference on machine learning",

url = "https://icml.cc/Conferences/2025",

}

Laenen, S, Macgregor, P & Sun, H 2025, Dynamic similarity graph construction with kernel density estimation. in A Singh, M Fazel, D Hsu, S Lacoste-Julien, F Berkenkamp, T Maharaj, K Wagstaff & J Zhu (eds), Proceedings of the 42nd international conference on machine learning. Proceedings of machine learning research, vol. 267, PMLR, pp. 32130-32163, 42nd International Conference on Machine Learning, Vancouver, British Columbia, Canada, 13/07/25. <https://proceedings.mlr.press/v267/laenen25a.html>

Dynamic similarity graph construction with kernel density estimation. / Laenen, Steinar; Macgregor, Peter; Sun, He.
Proceedings of the 42nd international conference on machine learning. ed. / Aarti Singh; Maryam Fazel; Daniel Hsu; Simon Lacoste-Julien; Felix Berkenkamp; Tegan Maharaj; Kiri Wagstaff; Jerry Zhu. PMLR, 2025. p. 32130-32163 (Proceedings of machine learning research; Vol. 267).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Dynamic similarity graph construction with kernel density estimation

AU - Laenen, Steinar

AU - Macgregor, Peter

AU - Sun, He

N1 - Funding: The third author of the paper is supported by an EPSRC Early Career Fellowship (EP/T00729X/1).

PY - 2025/10/1

Y1 - 2025/10/1

N2 - In the kernel density estimation (KDE) problem, we are given a set X of data points in ℝd, a kernel function k : ℝd × ℝd → ℝ, and a query point q ∈ ℝd, and the objective is to quickly output an estimate of ∑x∈X k(q,x). In this paper, we consider KDE 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.

AB - In the kernel density estimation (KDE) problem, we are given a set X of data points in ℝd, a kernel function k : ℝd × ℝd → ℝ, and a query point q ∈ ℝd, and the objective is to quickly output an estimate of ∑x∈X k(q,x). In this paper, we consider KDE 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.

UR - https://proceedings.mlr.press/v267/

M3 - Conference contribution

T3 - Proceedings of machine learning research

SP - 32130

EP - 32163

BT - Proceedings of the 42nd international conference on machine learning

A2 - Singh, Aarti

A2 - Fazel, Maryam

A2 - Hsu, Daniel

A2 - Lacoste-Julien, Simon

A2 - Berkenkamp, Felix

A2 - Maharaj, Tegan

A2 - Wagstaff, Kiri

A2 - Zhu, Jerry

PB - PMLR

T2 - 42nd International Conference on Machine Learning

Y2 - 13 July 2025 through 19 July 2025

ER -

Dynamic similarity graph construction with kernel density estimation

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this