Dynamic Similarity Graph Construction with Kernel Density Estimation
Authors: Steinar Laenen
Peter Macgregor
He Sun
Venue: ICML 2025 poster (2025)
Keywords: similarity graphs
kernel density estimation
spectral clustering
Primary area: general_machine_learning->clustering
TL;DR: This paper introduces dynamic data structures for kernel density estimation and sparse similarity graph constructions, with an application to clustering.

Abstract: In the kernel density estimation (KDE) problem, we are given a set  $X$ of data points in $\mathbb{R}^d$, a kernel function $k: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$, and a query point $\mathbf{q} \in \mathbb{R}^d$, and the objective is to quickly output an estimate of $\sum_{\mathbf{x} \in X} k(\mathbf{q}, \mathbf{x})$.
In this paper, we consider $\textsf{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.

Dynamic Similarity Graph Construction with Kernel Density Estimation
Steinar Laenen'
Peter Macgregor He Sun
Abstract
data points - .,2225+0(1)) time for the Gaussian kernel'.
In particular, our algorithm maintains (1 + =) -aappooxiee estimates of the kernel densities for every query point q E Q throughout the sequence of data point insertions; see The- orem 3.1 for the formal statement. Although known that KDE estimators can be maintained dynamically (Liang et al., 2022), the best of our knowledge, this represents the first dynamic algorithm for the KDE problem that efficiently maintains query estimates under data point insertions.
In the kernel density estimation (KDE) problem, we are given a set X of data points in IR a kernel function A: Rd x IRd - R, and a query point q E 1R and the objective is to quickly output an estimate of Exex k(q,x), In this paper, we con- sider KDE in the dynamic setting, and introduce data structure that efficiently maintains the esti- mates for 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 fast dynamic spectral clustering algorithm. We further evaluate the ef- fectiveness of our algorithms on both synthetic and real-world datasets.
Among its many applications, an efficient algorithm for the KDE problem on X = Q C Rd can be used to speed up the construction of a similarity graph for X, which key component used many graph-based clustering al- gorithms (e.g., spectral clustering). These clustering algo- rithms usually have superior performance over traditional geometric clustering techniques (c.g., k-means) (Ng et al., 2001; von Luxburg, 2007), but in general lack dynamic implementation. Our second contribution addresses this challenge, and designs dynamic algorithm that maintains a similarity graph for the dataset X with expected amortised update time n. 0.25+o(1) when new data points are added; Theorem 4.1 for the formal statement. Our algorithm guar- antees that, when the set X; of data points at any time t has a cluster structure, our dynamically maintained graph will have the same cluster structure as the fully connected graph on Xy; hence a downstream graph clustering algorithm will perform well.
1. Introduction
Given set X {x1 {x,,..., }n} of data points, set Q = {qi..... I of query points, and kernel func- tion k: Rd x Rdd + Rzo, the KDE problem is to quickly approximate و A Ex,ex k(q, x:) for every q E Q. As a basic question in computer science, this problem has been actively studied since the 1990s (Greengard & Strain, 1991) and has comprehensive applications in machine learning and statisties (Bakshi et al., 2023; Genovese al., 2014; Scholkopf & Smola, 2018; Schubert et al., 2014).
Our algorithms are experimentally compared against several baseline algorithms on 8 datasets, and these experiments confirm the sub- linear update time proven in theory. These experiments further demonstrate that
In this paper we first study the KDE problem in the dynamic setting, where both the sets of data and query points change over time. The objective is to dynamically update all the KDE estimates Pq for every q E Q as data points are added X. Building on the framework for static KDE developed by Charikar al. (2020), our algorithm processes: (i) in- sertions and deletions of query points, and (ii) insertions of
our dynamic KDE algorithm scales better large datasets than several basclines, including the fast static KDE algorithm in (Charikar et al., 2020), and
our dynamic similarity graph construction algorithm runs faster than the fully-connected and k-nearest neighbour similarity graph baselines, and produces comparable clustering results when applying spectral clustering.
'University of Edinburgh, United Kingdom University of St Andrews, United Kingdom. Correspondence to: He Sun
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Ouu algorithm generalises arbitrary kernel functions, with different powers of the update time.

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Related Work. Efficient algorithms for the kernel density estimation problem in low dimensions have been known for overtwo decades (Gray& & Moore, 2003; Greengard & Strain, 1991; Yang et al., 2003). For the regime of d = (loo n), there has been some recent progress to develop sub-linear query time algorithms (Charikar et al., 2020; Charikar & Siminelakis, 2017; 2019) based on locality-sensitive hash- ing (Andoni & Indyk. 2008; Datar et al., 2004) and impor- tance sampling using algorithms for computing approxi- mate nearest neighbours (Backurs et al., 2018; Karppa et al., 2022). Many sampling based methods incur a factor of e e-2 in their complexity due to concentration bounds like Cheby- chev's ' inequality, which is costly for high accuracy (small E). Techniques based on discrepancy theory and coresets have been developed to mitigate this, achieving e- depen- dence (Phillips & Tai, 2020; Charikar et al., 2024). There has also been recent work studying the approximation of kernel similarity graphs in the static setting (Macgregor & Sun, 2023; Quanrud, 2021).
recover the data points close y. Informally speaking, a family H of hash functions H TRd Z is locality sensifive if there are values E R, > 1, and Pl > p2, such that it holds for H drawn at random from H. that P| (u)
[v)] >> p1 when ||u vil & r, and IP[ ([)) = H(v) < Pz when ||u -vl 3 c.r. That is, the collision probability of close points is higher than that of far points. Datar et al. (2004) propose a locality sensitive hash family based on random projections, and their technique is further analysed by Andoni & Indyk (2008): Lemma 2.1 ((Andoni & Indyk. 2008)). Let p and q be any pair of points in R4. Then, for any fixed r > O, there exists a hash family H such that, if
Puear - Pp(r)) 2 P PHHH(HHP) = =((()) ||p - qll rrl
and
Piar _ p2(r, 2 (PHHH|ll(p) (q)) | ||p- ql > or]
Dynamic kernel density estimation has been studied in some restricted settings. Huang et al. (2024) give a dynamic vari- ant of the fast Gauss transform (Greengard & Strain, 1991) for low-dimensional data. Given an initial dataset X, Liang et al. (2022) give efficient algorithm for maintaining KDE estimator in which some data point x; is replaced with a new point z. In the same setting, Deng et al. (2022) present a dynamic data structure that maintains a spectral sparsifier of the kernel similarity graph for smooth kernels.
for any 2 1, then
p a log 1/ 1/Pnear
logt 11/2
+ +0
log L/Ptar
for some where Pnear takes dt time.
> O(vl) and each evaluation
We follow Charikar et al. (2020) and use t log which results in (1) evaluation time and p = 2² o (1). In this case, if O (log)"n). then p
1
Our work also relates to a number of works on incremental spectral clustering (Dhanjal et al., 2014; Klopotek et al.,, 2024; Laenen & Sun, 2024; Martin et al., 2018; Ning et al., 2007; Sun et al., 2020; Zhou et al., 2019). However, these works usually assume a fixed vertex set (Dhanjal et al., 2014; Martin et al., 2018; Ning et al., 2007), are limited to only handling single edge updates (Laenen & Sun, 2024), or do not have theoretical guarantees on their algorithm performance (Klopotek et al., 2024; Sun et al., 2020; Zhou et al., 2019).
(1 B),
for B = o1). Definition 2.2 (bucket). For any hash function H : .Rd + Z and x E Rd. let Bh be the set defined by BH(x) 2 {x' (x) = H (x')); we call By (x) a bucket.
2.2. Kernel Density Estimation
Given set X = {xI...., X,, of data points, a set Q {qi..... qm) of query points, and a kernel function
Rd x Rdd + R20 the KDE problem to compute Pgq k(q. X) 2 Exxex liqq. x;) for every q E Q. We assume that 1 & Mq & n. While direct computation of the m values for every q E Q requires mnd operations, there are a number of works that develop faster algorithms for approximating these m quantities.
2. Preliminaries
This section lists several facts we use in the analysis, and is organised as follows: Section 2.1 gives a brief introduction to locality sensitive hashing, which we apply in Section 2.2 to discuss fast algorithms for Kernel Density Estimation. We informally define an approximate similarity graph in Section 2.3.
Our designed algorithms are based on the work of Charikar, Kapralov, Nouri, and Siminelakis (Charikar al., 2020). We refer to their algorithm CKNS, and provide brief overview. At high level, the CKNS algorithm is based on importance sampling and, for any query point q. their
2.1. Locality Sensitive Hashing
Given data .I..... Xn E RRd, the goal of Euclidean locality sensitive hashing (LSH) is to preprocess the data in a way such that, given a query point E RRd, we are able to quickly
We make this assumption simply for the ease of our presen- tation, and setting 1a C for any constant Ç instead will not influence the asymptotic results our work.
2

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
objective is to sample a data point x; E X with probability approximately proportional to k(q. xz). To achieve this, they introduce the notion of geometric weight levels { defined as follows:
where Cij _ min 1 log"/" nj and B = o(L) from ry Lemma 2. I. We define the general cost of kernel as cost(k) & maxpa costri (k. For any [Jpa] we further define
Definition 2.3 (CCharikar et al., 2020)). For any query and for j E [Jrgh let 19- Ex xi) E (2-1.2) 2 2- J. We define the
point q. let Jpn _ log 2n|
i i-j c 3)
Ha
kg
max log Puear.j imjth.... +1
(2.1)
corresponding distance levels as
max x.x xxx ((x,))((2 (E (-
x|x - x'Il
By the assumption that 1 < Mg & n, the cost of some popular kerness such as the Gaussian kernel kg. the t-student kernel hy, and the exponential kernel ke are cost(kg) = n ()+o(1)) cost((;)) = no(1), and cost( = (1++(())) respectively (Charikar al., 2020).
for any j E (Jral and define
U
L pq +1 X
4
2.3. Approximate Similarity Graphs
jElJag!
Constructing a similarity graph from a set of data points is the first step of most modern clustering algorithms. For any set X (X1,-... X,) of data points in IRd and kernel func- tion k R x RR + Rg0, similarity graph F (V, E, w) from X can be constructed as follows: each x; E X is ver- tex in F. and every pair of vertices x; and x, is connected by an edge with weight wx(,, Xj) = k(x,, xy). While this graph has ((n²) edges by definition, we can construct in (n) time sparse graph G with (()) edges such that (i) every cluster in F has low conductance in G, and (ii) the eigenvalue gaps of the normalised Laplacian matrices of F and G are approximately the same (Macgregor & Sun, 2023); these two conditions ensure that a typical clustering algorithm on F and G returns approximately the same result. We call such sparse graph G an approximate similarity graph, and refer the reader to Section A in the appendix for its formal definition.
These L for any query point q partition the data points into groups based on the kernel distances k(q. x,), progress- ing geometrically away from q. Their key insight is that the number of data points in each level L. is bounded:
Lemma 2.4 (CCharikar et al., 2020)), It holds for any query point q and j E (Jp.] that [.9] < 2
/dq.
Hence, one sub-sample the data points with probabil- ity 1/(2/. (4q] for every j [Jry]] and the sampled data points are stored in hash buckets using LSH. This data struc- ture will allow for fast and good estimation of Ma for any query point q. We further follow Charikar et al. (2020), and introduce the cost of a kernel k.
Lemma 2.5 (Charrikrr et al., 2020)). Assume that kernel ie induces weight level sets L and corresponding distance levels r 's. Also, for any query q, integer i E [Jpa + 1]. and j E [Jng] satisfying >> j. let p L and p' E L. Assuming that H. is an Andoni-Indyk LSH family designed for near distance r (see Lemma 2. I), the following holds for any integer 1 3 1:
2.4. Convention & Assumption
For ease of presentation, for any set X C Rd and z e Rd we always use X U uz and X z to represent X U {z} and X \ (z). For a similarity graph F constructed for any set X [x,....., x,) C Rdd we use x; to represent both the point in Ed and the corresponding vertex in F, as long as the underlying meaning of x; is clear from context. We use xx, to represent edge with x; and xy as the endpoints, and we only consider undirected graphs. We use Ö(n) to represent O(n log" n) for some constant c. The log operator takes the base 2.
1. PH (H)pp) = (a)) > Phearrs
2. PH-wu [H (p') (q) < Pnears
(1-8)
where e 2 C.j e min { 1 log n.). Puear.s 2 pi())).
and B = o(1) from Lemma 2.1.
Definition 2.6 (Cost of a Kernel), Suppose that a kernel is induces distance levels r;'s 's based on the kernel value Pa (see Definition
Assumption 2.1. Let n4 = |X| denote the number of data points at initialisation. We assume that, if X, C Rd represents the set of data points after I updates, then |X,| < ni for constant & > 0. Moreover, based on the JL Lemma (Johnson, 1984), we always assume that d = (log [Xl)), and hence our work ignores the depen- dency on d in the algorithms'' runtime.
2.3). For any j E [Jma] we define the cost of kernel i for weight level Lg as
)
i i- j
cost (k, 2 exp2
max imj+h
22 (1-11) (11- B)
3

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
3. Dynamic Kernel Density Estimation
previous work (Liang et al., 2022) has shown that the CKNS KDE estimator can be extended to the dynamic setting, our result shows that the estimates of set of query points can be efficiently updated.
In this section we design a data structure to dynamically maintain KDE estimates as new data and query points are added or removed over time. Our data structure supports INITIALISE(X, e, which creates hash data structure for the KDE estimates based on X, and supports operations for dynamically maintaining the data and query point sets as well as the corresponding estimates. Our key technical contribution is the design of a query hash data structure, in which we carefully store relevant hash values for query points, enabling efficient updates query estimates as data points are added. The main components used in updating the data structure and their performance are as follows:
3.1. Analysis for the Initialisation
The initialisation step prepares all the data structures used for subsequent data and query point updates. The main component used in INTTIALISE(X, Q,e) is the PREPROCESS(X,e) procedure, which preprocesses the data points in X to ensure that the value μa for any query point q can be fast approximated. To achieve this, PREPROCESs (X, e) defines
Theorem 3.1 (Main Result 1). Let be a kernel function with cost(k) as defined in Definition 2.6, and X Rd a set of data points updated through data point insertions. As- suming Q = 0 initially', the performance of the procedures in Algorithm is as follows:
M a {2 KE log (2m1))
and indexes every b4 E M such that μo < ... < Mog(2n)); note that pi = 2'. Then for b4 E M and j E [log(2 - m1/m)] it samples every data point in X with probability min ( (1/(2++(4)) 1). and employs a hash function H H....j. chosen uniformly at random from H* with ky = -(1) (ef. Lemma 2.5) to add every sampled x E X to the buckets {BH [x) indexed by all the possible E [Ki] with K₁ O n1 ==-?), and e E [K2] with K₂ = O(log(m1) cost(k)). In addition, PREPROCESS(X, samples every data point in X with probability 1/(2n)) ) for all the possible values of 14 and o, and adds the sampled points to set { pe hy.. We remark that our described PREPROCESS(X,,o .) is almost the same as the one presented in Charikar et al. (2020) and, although this data structure is sufficient to quickly output KDE esti- mates, we need to store additional query-hash buckets to update estimates when new data points arrive.
Initialisation: INITIALISE(X,,) V,.)) creates a hash data structure for the KDE, and runs in time e-2.. ii 1+0(3) -k) where n1 is the number of data points at initialisation.
For every query point insertion Q QUO q and deletion Q Q) q. P and DELETEQUERYPOINTIT update the corre- sponding sets and data structures. Moreover, ADDQUERYPOINT(a) returns Ba that achieves a (1 + e multiplicative factor approximation of Pq with high probubility.
Query Point Updates:
Data Point Updates: For every data point insertion ADDDATAPOINTIS updates the corre- sponding sets and data structures, and returns the up- dated estimates Ωa that achieve (1 m)mllipplicatiee factor approximations of Hq for every maintained query point E Q.
U X
X
3.2. Analysis for Updates
When a new query point q arrives, ADDQUERYPOINT(Q) performs the following operations:
computes the KDE estimate وa of Pa using the hash- based data structure from INITIALISE X, Q,
With high probability, the amortised running time for each update procedure is -2 no(1). cost(k), where | is the current number of data points.
2. It adds to the sets Qu for every E M that satisfies Pa & 14i and adds q to the buckets B B (q) for a E [K1], j [Ju,]] and E [K2], which we call the query-hash.
To examine the significance of Theorem 3.1, notice that the amortised update time (11) (k)) for the data point insertions is independent of the number of query points IQ]. This makes our algorithm significantly more efficient than re- re-estimating the query points after every update. While
When new data point z arrives, we invoke the ADDDATAPOINTI procedure. This procedure is main technical contribution to enable dynamic updates of query estimates within the framework of Charikar et al. (2020), and works as follows: ADDDATAPOINT(2) checks whether the number of data points has doubled since the last con- struction (or reconstruction) of the data structure, and re-
*When Q 0 with Q1 A m., we have additional additive factor of ma 2², p1) cost(k) and mi =² o()) cost(k) in the running time of the initialisation and data point update steps respectively.

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Data hash
Query hash
Rd
q3
42
qu
R2
41
q3
X;
4
X3
X6
q1
q
qu
t
41
BBo (z)
(u)
(b)
(c)
Figure I: Illustration of ADDDATAPOINT(Z) for a single iteration μr E M. a. KI.J and E [K2].. The first row illustrates (a) the subsampled data points Z & (Xa, Xa, Xa and query points Qn - {qu)t (b) the bucketing of Z by the hash function Hyy.o...s. as well as (c) the bucketing of Q by the same hash function. The second row illustrates (a) the relative location of new arriving data point a Rd with shaded red region indicating LJ, (b) z's inclusion the bucket By (z). as well as (c) the recovery qy BR Bipgaag (z) because E L
initialises the data structure if it is the case. Otherwise, ADDDATAPOINT(2) performs the following operations:
running time analysis of ADDDATAPOINT(2) and ADDQUERYPOINT(E can be found in Section B of the appendix.
1. It samples with probability min {1 (1/(2)+1 (4), }} for all possible μr E M,, and adds the sampled to the buckets B B (z) for all E K1, J E [J,.]. and E [K2]: also samples z with probability 1 1/(2m) for all the possible values of (4; and a, and adds the sampled point to the set ) Notice that the way that is added in the buckets exactly the same the one when executing INITIALISE(X X U 2, Q,e), and hence ADDDATAPOINTIS correctly updates all the buckets. This bucket-updating procedure is similar to Liang et al. (2022), though in their dynamic setting a newly arriving point replaces an existing one; here, we add the new point instead.
Finally, the DELETEQUFRYYPINTIII procedure simply removes any stored information about the query point throughout all the maintained data, and its running time follows from the running time of ADDQUERYPOINT(Q)
4. Dynamic Similarity Graph Construction
In this section we design an approximate dynamic algorithm that constructs similarity graph under sequence of data point insertions, and analyse its performance. Given a set X of ni points in Ed with d = Ollog n1), and a sequence of points {z} that will be added to X over time, our designed algorithm consists of the CONstRucTGRAPH and UPDATE- GRAPH procedures, whose performance is follows:
2. If z is sampled, ADDDATA (OINT(Z)) recovers all the points qe E Bionnisie (z) in the query hash that satisfies
Theorem 4.1 (Main Result 2). Let k be a kernel function with cost(k) as defined in Definition 2.6, and X C R set of data points updated through point insertions. Then, the following statements hold:
E q(Qu (Uy=s Onyy) and z E Lg. Every such q is exactly the point whose KDE estimate üq would have included z if AADQUERYPOINTIR called after running INITIALISE(X X U z, e).). Hence, the KDE estimates وa for the recovered are updated appropriately.
would have been
The Initialisation Step: with probability at least 9/ 9/10, the CONSTRUCTGRAPH procedure constructs an ap- proximate similarity graph G (X, E, wG) with FF] = Ö(n) edges, where ny = X is the number of
See Figure| for illustration.
The correctness and
5

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
data points at initialisation. The running time of the initialisation step is n.
on (T.kdd.jxxe fdde J. where T.kde is the dy- namic KDE data structure maintained the root of T- In particular, every sampled edge (X;, X;) is added with this weight independent of the edge being sampled from x, or Xj. This modification allows for correct reweighting and resampling after a sequence of data point insertions.
1++(1)_ (o.)
2.
The Dynamic Update Step: for every new arriving data point z. the UPDATEGRAPH procedure updates the approximate similarity graph G, and with prob- ability at least 9/10 G is an approximate similarity graph for X Uz. The expected amortised update time is n no)1) cost(k), where n is the number of currently considered data points.
4.2. Analysis for Dynamic Updates
The main technical contribution of our dynamic approxi- mate similarity graph result is the UPDATEGRAPH(G. T, procedure, which dynamically updates our constructed graph such that the updated graph is an approxi- mate similarity graph for X U z. At high level, UPDATEGRAPH(G, T, z) works as follows:
On the significance of Theorem 4.1, first notice that the algorithm achieves an update time of no()). (k)). For the Gaussian kernel, this corresponds to an update time of n (1+)))))) which is much faster than the ((n) time needed to update the fully connected similarity graph. Secondly, our result demonstrates that, as long as the dynamically chang- ing set X C I2d of points presents a clear cluster structure, an approximate similarity graph G for X can be dynami- cally maintained, and the conductance of every cluster in G can be theoretically analysed, due to the formal definition of approximate similarity graph (Definition A.3). This is another difference between work and many heuristic clustering algorithms that lack theoretical guarantee on their performance.
1. for every new data point z. UPDATEGRAPH T, creates a new leaf node for z, and places it appropri- ately in T ensuring that the new tree is complete binary tree;
2. UPDATEGRAPH(C: T.z) inspects the internal nodes from the new leaf z to the root of the tree, and for every such internal node it adds z as a new data point in the corresponding dynamic KDE estimators;
3. UPDATEGRAPIICS T, 22) further checks in every in- ternal node along the sample path Px..e whether the KDE estimate of any x; has changed due to the in- sertion of z. If so, Px., is added to the set A of paths that need to be updated, For every Px. E A, UPDATEGRAPH(C; T,z) finds the highest internal node T where the KDE estimate of x, has changed, removes the path from all nodes below T', and re- samples the corresponding edges; this is achieved through RESAMPLE(T, Px.,)) Additionally, it em- ploys SAMPLE((2); T,E) to sample new edges ad- jacent to z.
4.1. Analysis for the Initialisation
The main component of the initialisation step is our de- signed CONSTRUCTGRAPICXX procedure, which builds a (complete) binary tree T for X, such that each leaf corresponds to a data point x; E X. and each internal node of T corresponds to a dynamic KDE data structure (described in Section 3) on the descendant leaves/data points. At high level, CONSTRUCTGRAPH((X applies the SAMPLE(X. (X,,LEEX7)))) T, (X,T,,,TTK... E) procedure to recursively traverse T and sample L = Ollog (xl) neighbours for every vertex based on the KDEs maintained by the internal nodes. It also stores the paths Px, (x; E X, E & L). each of which records the internal nodes that x; visits when sampling its /th neighbour; with these stored paths the algorithm can adaptively resample the tree as new data points arrive. In addition, the query points whose KDE estimates are dynam- ically maintained at any internal node T' are the data points x; whose sample path Px,, visit?? T'
See Figure 2 for illustration. It is easy to see that the to- tal time complexity of UPDATEGRAPIIG, T, 2) is domi- nated by (i) the time complexity of SAMPLE ((Z)) T,E) and RESAMPLE(T, Px.e), and (ii) the total number of paths A that need to be reconstructed. We study the time complexity of these two procedures, and our result is as follows:
Lemma 4.2. For any x E Rdd and & E N, the running time of SAMPLE (x). T,E) (Algorithm 8) and RESAMPLE(T. PPx,e) (Algorithm 10) is n.()) cost.(k).
Our initialisation procedures and corresponding proofs fol- low Macgregor & Sun (2023) at a high level, however there are several crucial differences between the two al- gorithms. First of all, our algorithm explicitly tracks the sample paths Px,, to ensure we can adaptively re- sample edges of the similarity graph. Secondly, a sub- tle but key difference between our analysis and theirs is that the weight of every edge (x,, xx) added by our algo- rithm set to be (xx,, (x), (i, Here, úii,, depends
Given that SAMPLE(Z, T. is called L Ō(1) times by UPDATEGRAPH G, T,z), and RESAMPLE(T, Px.c) is called |A| times, Lemma 4.2 implies that the running time of UPDATEGRAPH depends on the number of re-sampled paths [A]. Therefore, to prove the time complexity of UP- DATEGRAPH, it remains to show that E[[A[]] is sufficiently small.
6

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Pas
T
Unchanged Pxy.
T
Pap
Resampled Pxp
Big change
X7
X5
X9 X10
X11
X8
X9 X10
X11
X1
X2
Xg X4
X;
X6
X1
X2
X1
X1
Xj X6
X]
Figure 2: Illustration of updating T after performing UPDATEGRAPH((S). (a). Pxi, e and Px: e are generated by SAMPLE((XI): and SAMPLE((X)) ), T, [,),, and correspond edges (xi,x)) and (x1, xs). (b) illustrates that, after adding z, part of Pxy,e' updated due to RESAMPLE(T", PxI,e)) and (x1, Xs) is replaced by (X1, Xo); however, the update on z doesn't change Px,,e-
Bounding the expected number of re-sampled paths cor- responds to bounding the number of query points whose KDE estimates are updated at each affected internal node T'. However, applying Theorem 3.1 directly is insufficient because, our approximate similarity graph, the dynamic KDE data structures start with X rather than Q - 0. As such, more careful analysis is needed, and the following notation for the query points Q will be used.
collisions caused by hashing z in the dynamic KDE data structure k'.dde at every affected internal node T', Cru- cially, by separately analysing the contributions from query points in Qu (T') for > and applying Lemma 4.4, we are able bound the expected number of colliding points in the buckets T' kd. B Bi.,....... sufficiently tightly each affected internal node T'.
Lemma 4.5 (Informal version of Lemma C.2). Let z be the data point that is added to T through our designed update procedures, and T be any internal node that lies on the puth from the new leaf LEAF(Z) to the root of Then holds for any a. and & that
Definition 4.3. Let T be the KDE tree constructed from CONSTRUCTGRAPH(XX and T an internal node of TT Then, for 0 & j < < [log(2 TT.de.n)], we define the sel
Qpitpy (T') A (q E Q.de.. 14 & k(q. T.q.T.kee Xdde.) < 2ps and k(q, T' kde.X) ) & pj}, (4.1)
EHag llll E T .dde.. =T'.ke..f (. Ō (mx (..22+)). (4.2)
where T .'dde is the dynamic KDE data structure main- tained at T
Combining Lemma 4.5 with the fact that z is sampled with probability min {1 (1/(2i+1ja)) (1),, for all possible [[log(2 T kde..)]]] and [J,.] along every affected in- ternal node T', and noting that there are Õ(1) such nodes, we obtain the following result.
The set Qui-pyy (T') represents the set of query points q E X whose KDE estimates bounded by μi; when computed with respect to the data points X at the root of the tree, and bounded by Mj for j < i when computed with respect to the data points X' represented at the internal node T'. Intuitively, this set captures the query points whose KDE estimates decrease when moving from the root of the tree to the internal node T'. These sets exhibit the following useful property.
Lemma 4.6. For every added the expected num- ber of paths A that need to be resampled by UPDATEGRAPI[ T,2) satisfies E[JAA]] = Ō(1)
Combining Lemmas 4.2 and 4.6 with the running time anal- ysis of other involved procedures proves the time complexity in the second part of Theorem 4.1. To show that our dynam- ically maintained G is approximate similarity graph, prove in Lemma C.6 that running CONSTRUCTGRATE followed by UPDATEGRAPH(G, T, is equivalent to running CONSTRICTGRAPH(X U z); hence the correct- ness of our constructed G follows from the one for CONSTRICTGRAPH(X)
Lemma 4.4. It holds for any q Qui-tHy (T') that
Piq E T'. kw..eeee000 Q = Ō M4
To bound the number of maintained query points whose estimate is updated, we look at the expected number of
7

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
5. Experiments
Table gives the total running time and final relative error for each algorithm, and Figure 3 shows the time taken to up- date the data structure for the census dataset at each iteration. From these results, we observe that our algorithm scales bet- ter to large datasets than the baseline algorithms, while maintaining low relative errors. Figure 3 further shows that the update time of our algorithm is sub-linear in the number of data points, as shown theoretically in Theorem 3.1. The update time of the other algorithms is linear in and their total running time is quadratic.
In this section, we experimentally evaluate our proposed dy- namic algorithms for KDE and approximate similarity graph construction on the Gaussian kernel. All experiments are performed on computer server with 64 AMD EPYC 7302 16-Core Processors and 500 Gb of RAM. We report the 2- sigma errors for all numerical results based on 3 repetitions of each experiment, and Section D gives additional exper- imental details and results. Our code can be downloaded from http:://gituub..oo//eeennnt wwwo///iiinall.nnnnnnyynaamamm waween/Dynammiccc..... Similarrt- Graph-Consttuction-Wy wittiitooo-wttt--t -eapittttoooiiiit------e--eeeeee -eemmel-Density-Baii
175
We evaluate the algorithms synthetic data, and we summarise their properties in Ta- ble 3 in Section D. The datasets cover a variety of do- mains, including synthetic data (blobs (Pedregosa et al., 2011)), images (mnist (Lecun et al., 1998), aloi (Geusebrock et al., 2005)), image embeddings (cifar10 (He et al., 2016; Krizhevsky, 2009)), word embeddings (glove (Penning- ton et al., 2014)), mixed numerical datasets (msd (Bertin- Mahieux et al., 201 I), covtype (Blackard & Dean, 1999), and census (Meek et al., 1990)).
variety of real-world and
FXACT
150
CKNS
DYNAMICRS
Update time (s)
125
OUR ALGORITIM
100
75
50
25
500
1000
1500
2000
2500
5.1. Dynamic KDE
x x10
To the best of our knowledge, our proposed algorithm is the first which solves the dynamic kernel density estimation problem. For this reason, we compare our algorithm against the following baseline approaches:
Figure 3: Dynamic KDE update time on the census dataset
5.2. Dynamic Clustering
For the dynamic similarity graph algorithm, we compare against the two baseline algorithms:
1. EXACT: the exact kernel density estimate, computed incrementally as data points are added;
1. FULLYCONNECTED: the fully-connected similarity graph with the Gaussian kernel;
2. DYNAMICRS: dynamic KDE estimator based on uni- form random sampling of the data. For all experiments, we uniformly subsample the data with sampling proba- bility 0.1;
2. KNN: the k-nearest neighbour graph. for k = 20. We split the datasets into chunks of 1, 000 and add each chunk to the dynamically constructed similarity graph, adding one complete ground-truth cluster at a time.
3. CKNS:
we use the fast kernel density estimation al- gorithm proposed by Charikar et al. (2020), and fully re re-compute the estimates every time the data is up- dated.
At each iteration, we apply the spectral clustering algorithm to the constructed similarity graph and report the normalised mutual information (NMI) (Lancichinetti et al., 2009) with respect to the ground truth clusters. Table 2 shows the total running time and final NMI values for each algorithm on each dataset. From these results, we see that our algorithm achieves competitive NMI value with faster running time than the baseline algorithms.
For each dataset, we set the parameter of the Gaussian kernel such that the average kernel density Mg n-1 x 0.01 (Karppa et al., 2022). We split the data points into chunks of size 1,000 for aloi, msd, and covtype, and size 10,000 for glove and census. Then, we add one chunk at a time to the set of data points X and the set of query points Q. At each iteration, we evaluate the kernel density estimates وu produced by each algorithm with the relative error (Karppa et al., 2022)
6. Conclusion
This paper develops dynamic algorithms for KDE and ap- proximate similarity graph constructions. Compared with many heuristic methods such as the DYNAMICRS algorithm
1
Σ (0q - Ha)/Hal
crr
[Q]
QEQ
8

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Table 1: The experimental results for the dynamic KDE algorithms. Shaded cells correspond to the algorithm with the lowest running
time. The running times of the exact algorithm are 164.5, 2715.6, 2179.9, 5251.7, and 16279.9.
CKNS
DYNAMICRS
OUR ALGORITHM
datasct
Time (8)
ErT
Time (s)
Err
Time (s)
Err
aloi
619.0+10.77
1.030=0.006
19. 3
0.010 003
46.9
0.060=v..02
msdd
14, 360.0...0
0.385 000
1, 0870
5.430 000
306.410.0
0.388 1.0000
covtype
5, 11090
0.15940.0000
309.2
0.018 000.00
131.7:+..5
0. 0.100:10.017
glove
2, 1677.7
0.221 229
1, 038.66226..
0.004 005
145.6+221..6
0.2966:0..00
census
10, 411.5
0.080 000
3, 424.
0.005
836.5
0.102++0.021
Table Running time and NMI results for the dynamic similarity graph algorithms. each dataset, the shaded cells correspond to the algorithm with the lowest running time.
FONNECCNEECTED
KNN
OUR ALGORITHM
dataset
Time (s)
NMI
Time (s)
NMI
Time (s)
NMI
blobs
72.8+2.2
1.000=0.00m
383.643.9
0.933
21.2400.
1 1.000
cifar10
19, 118..2223...
00.00
3. 503.0#490.6
0.227=+0.002
1,403.5+152..
0.339++.021
mnist
1, 159
0.460=0.c00
5, 796.3+234.3
0.812+40003
1, 1,177.3477.9
0.523+0.011
and dynamic k-NN graphs, our algorithms have theoreti- cally proven approximation guarantees. Our empirical eval- uation further demonstrates their competitive performance, with our dynamic KDE algorithm showing better scalabil- ity on large datasets and our similarity graph construction achieving faster running time while maintaining comparable clustering quality.
Communications of the ACM, 51(1):117-122, 2008.
Backurs, A., Charikar, M., Indyk, P., and Siminelakis, P. Efficient density evaluation for smooth kernels. In 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS' 18), pp. 615-626, 2018.
Bakshi, A., Indyk, P., Kacham, P., Silwal, S., and Zhou, S. Subquadratic algorithms for kernel matrices via kernel density estimation. In / Ith International Conference on Learning Representations (ICLR'23) 233), 2023.
In addition to their theoretical advances, our algorithms could have several other applications. For example, our dynamic KDE tree is able to maintain randomly sampled neighbours of given vertex by edge weight of similarity graph, which is a common primitive in many algorithms for similarity graphs (Bakshi et al., 2023), and our KDE tree could facilitate the design of dynamic variants of these algorithms
T., Ellis, D. P., Whitman, B., and Lamere, P. The million song dataset. In 12th International Confer- ence on Music Information Retrieval (ISMIR' 2011.
Blackard, J. A. and Dean, D. J. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and Electronics in Agriculture, 24(3):131- 151, 1999.
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Charikar, M. and Siminelakis, P. beashing-base-essiinne for kernel density in high dimensions. In 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS'I7), 17), pp. 1032-1043, 2017.
Acknowledgements
Charikar, M. and Siminelakis. P. Multi-resolution hashing for fast pairwise summations. In 60th Annual IEEE Sym- posium on Foundations of Computer Science (FOCS'19), pp. 769 0099-79,222 2019.
The third author of the paper is supported by EPSRC Early Career Fellowship (EP/T00729X/1).
References
Charikar, M., Kapralov, M., Nouri, N., and Siminelakis, P. Kernel density estimation through density constrained near neighbor search. In 6l Annual IEEE Symposium on
Andoni, A. and Indyk, P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Foundations of Computer Science (FOCS'20), pp. 172- 183, 2020.
Klopotek, M. A., Starosta, B., and Wierzchon, S. T. Eigenvalue-based incremental spectral clustering. Jour- nal of Artificial Intelligncee and Soft Computing Re- search, 14(2):157-169, 2024.
Charikar, M., Kapralov, M., and Waingarten, E. A quasi- monte carlo data structure for smooth kernel evaluations. In 35th Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA 24), pp. 5118-5144, 2024.
Krizhevsky, A. Learning multiple layers of features from tiny images. Master's thesis, University of Toronto, 2009,
Chung, F. R. Spectral Graph Theory. 1997.
Laenen, S. and Sun, H. Dynamic spectral clustering with provable approximation guarantee. In 4/st International Conference on Machine Learning ([CML'24) 2024.
Datar, M., Immorlica, N., Indyk. P., and Mirrokni, S. soeasity- hashing scheme based on p-stable dis- tributions. In 20th Annual symposium on Computational Geometry (SoCG'04) pp. 253-262, 2004.
Laneichinetti, A., Fortunato, S., and Kertész, Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3): 033015, 2009.
Deng, Y., Jin, W., Song, Z., Sun, X., and Weinstein, O. Dynamic kernel sparsifiers. arXiv:2211. 1..2211.442.... 2022.
Lecun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. Proceed- ings of the IEEE, 86(1 11:227--222,, 1998.
Dhanjal, C., Gaudel, R., and Clémençon, S. Efficient eigen- updating for spectral graph clustering, Neurocomputing, 131:440 4524,44-42,.. 2014.
Lee, J. R., Oveis Gharan, S., and Trevisan, L. Multiway spectral partitioning and higher-order Cheeger inequali- ties. Journal of the ACM, 616)) 2014.
Genovese, C. R., Perone-Pacifico, M., Verdinelli, I., and Wasserman, L.. Nonparametric ridge estimation. The Annals of Statistics, 42(4):1511 1545, 2014.
Liang. J., Song, Z., Xu, Z., and Zhuo, D. Dynamic mainte- nance of kernel density estimation data structure: From practice to theory. arXiv:2208.033 03915, 2022.
Geusebroek, J.-M., Burghouts, G. J., and Smeulders, A. W. The Amsterdam library of object images. International Journal of Computer Vision, 61:103-112, 2005.
Macgregor, P. and Sun, H. Fast approximation of similarity graphs with kernel density estimation. In Advances in Neural Information Processing Systems 37 (NeurIPS 2023.
Gray, A. G. and Moore, A. W. Nonparametric density estimation: Toward computational tractability. In 2003 SIAM International Conference on Data Mining, pp. 203-
211, 2003.
Martin, I.., Loukas, A., and Vandergheynst, P. Fast approxi- mate spectral clustering for dynamic networks. In 35th In- ternational Conference on Machine Learning (ICML'18) pp. 3420-3429, 2018
Greengard, L. and Strain, J. The Fast Gauss Transform. SIAM Journal Scientific & Statistical Computing, 12 (1):79-94, 1991.
Meek, C., Thiesson, B., and Heckerman, D. US Census Data (1990). UCI Machine Learning Repository, 1990.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition (CVPR'16) pp- 770-778, 2016.
NASA. Statlog (Shuttle). UCI Machine Learning Reposi- tory, 2002.
Huang, B., Song, Z., Weinstein, O., Yin, J., Zhang, H., and Zhang, R. A dynamic low-rank fast Gaussian transform. DXXiv:2202.12322 2024.
Ng. A. Y., Jordan, M. I., and Weiss, Y. On spectral cluster- ing: Analysis and an algorithm. In Advances in Neural Information Processing Systems 15 NeurlPSSO1), pp. 849-856, 2001.
Johnson, W. B. Extensions of Lipschitz mappings into Hilbert space. Contemporary Mathematics, 26:189-206 1984.
Ning, H., Xu, W., Chi, Y., Gong, Y., and Huang, Incre- mental spectral clustering with application to monitoring of evolving blog communities. In the 2007 SIAM In- ternational Conference Data Mining (SDM'07). pp. 261-272 2007.
Karppa, M., Aumüller, M., and Pagh, R. Deann: Speeding up kernel-density estimation using approximate nearest neighbor search. In 25th International Conference on Artificial Intelligence and Statistics (AISTATS'2) 22),, pp- 3108-3137, 2022.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P.,
10

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Weiss, R., Dubourg. V., Vanderplas, J., Passos, A., Cour-
napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
Peng, R., Sun, H., and Zanetti, L. Partitioning Well- Clustered Graphs: Spectral Clustering Works! SIAM Journal on Computing, 46(2):710-7433 2017.
Pennington, J., Socher, R., and Manning, C. Glove: Global vectors for word representation. Proceedings of the 2014 conference on empirical methods natural language processing (EMNLP), pp. 1532-1543, 2014.
Phillips, and Tai, W. M. Near-optimal coresets of
kernel density estimates. Discrete Computational Ge- ometry, 63:867-887, 2020.
Quanrud, K. Spectral sparsification of metrics and kernels. In 32nd Annual ACM-SIAM Symposium on Discrete Al- gorithms (SODA'21) pp. 1445-1464, 2021.
Rand, W. M. Objective criteria for the evaluation of cluster- ing methods. Journal of the American Statistical Associ- ation, 66(336):446855,, 1971.
Scholkopf, B. and Smola, A. J. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT Press, 2018.
Schubert, E., Zimek, A., and Kriegel, H.-P. Generalized outlier detection with flexible kernel density estimates. In 2014 SIAM International Conference on Data Mining, pp. 542-550, 2014.
Sun, G., Cong, Y., Wang, Q., Li, J., and Fu, Y. Lifelong spectral clustering. In 34th AAAI Conference Artificial Intelligence (A)) volume 34, pp. 5867-5874, 2020.
Sun, H. and Zanetti, L. Distributed graph clustering and sparsification. ACM Transactions Parallel Computing, 6(3):17:1-17:23, 2019.
von Luxburg, U. A tutorial on spectral clustering. Statistics and Computing volume, 17(4):395 416. 2007.
Yang, C., Duraiswami, R., Gumerov, N. A., and Davis, L. Improved fast Gauss transform and efficient kernel density estimation. In 9th International Conference on Computer Vision (ICCV'03), pp. 664 671, 2003.
Zhou, P., Shen, Y.D.,, Du, L., Ye, F,, and Li, X. Incre- mental multi-view spectral clustering. Knowledge-Band Systems, 174:73-86. 2019.

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
A. Additional Background Knowledge
This section presents additional background knowledge used our analysis, and organised as follows: Section A.1 lists further notation for graphs and useful facts in spectral graph theory; Section A.2 formally defines the concept of an approximate similarity graph.
A.1. Notation
Let G EV, E, w) be an undirected graph of vertices and weight function w : V + Rzo. For any edge (u, =
E, we write (w 2) or wG(e) to express the weight of e. For vertex u V. we denote its degree by (ug - Eesy we(u, (u, v), and the volume for any S _ V is defined as vola - Eves dega (u). . For any two subsets S,T C. V, we define the cut value between S and T by (S) & EesEo (S,T) We, where (g T)) is the set of edges between S and T. Moreover, for any S C V, the conductance of defined as
WG (S, V S) min/vol (V [S)
(S) A
S + 0, and (5(() = if $ For any integer k > 2, we call subsets vertices Aq,..., U._1 A, = V and A; n A for different and j. We define the k-way expansion of G by
, A& a k-way partition of if
PG (k) A
partitions A max (A,).
min
Part of our analysis is based algebraic properties of graphs, hence define graph Laplacian matrices. For graph G' (V, E, w), let DG E pax= be the diagonal matrix defined by Da(u, dega(u) for all E V. We denote by Ag E Rax= the adjacency matrix of G, where Ag (u, v) = wa(u, v) for all E V. The normalised Laplacian matrix of G is defined as
Lg - I - - 1/2 AGD
where I is the n n identity matrix. The normalised Laplacian LG symmetric and real-valued, and has real eigenvalues which we write as x (Cc) ... Ann (Cc). We sometimes refer to the ith eigenvalue of LG X if it is clear from the context. It is known that (CG) = 0 and (Co) (Chung, 1997). The following result will be used in analysis.
Lemma A.1 (higher-order Cheeger inequality, (Lee et al., 2014)). holds for any graph G and > that
>e(Ga)
< po(kk = 0 (R.) Ve(La))
(A.1)
A.2. Approximate Similarity Graph
We first introduce the notion of cluster-preserving sparsifiers
Definition A.2 (Cluster-preserving preserving sparsifier, (Sun & Zanetti, 2019)). Let F E, w) be any graph with is clusters, and (S)) k--ay partition of F corresponding to pr(k). We call re-weighted subgraph G = (V, E' C E. B.we) cluster-preserving sparsifier of F (i) (cc(S))=0 ( for < i & k and (ii) Ak41 (Lc) = ((A++1(Fr)
Notice that graph F EV, w) has exactly is clusters (i) has disjoint subsets Si,..., Se of low conductance, and (ii) any (k + 1)- partition of F would include some A C V of high conductance, which would be implied by lower bound on (CF)(FF) due (A.1). Together with the well-known eigen-gap heuristic (von Luxburg, 2007) and theoretical analysis on spectral clustering (Peng et al., 2017), these two conditions ensure that the & optimal clusters in F have low conductance in G as well. Based on this, we define approximate similarity graphs as follows:
Definition A.3 (Approximate Similarity Graph). For any set X Ied of n data points and the fully connected similarity graph F X, we call sparse graph G with (n) edges an approximate similarity graph X if G is a cluster-presenn sparsifier of F.
We call G an approximate similarity graph in the extended abstract satisfies the properties of Definition A.3.
12

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
B. Omitted Detail from Section 3
This section provides the detailed explanations omitted from Section and is organised as follows: Section B.1 analyses the initialisation and querying procedures. Section B.2 analyses the dynamic update step for adding data points. Finally, Section B.3 proves Theorem 3.1.
Algorithm describes all the used procedures and corresponding subprocedures, whose performance is summarised in Theorem 3.1.
Algorithm 1 DYNAMICKDE(X,,C Q,
1: Members
2: Āq
Query estimates for every point E Q > Precision parameter for KDE estimate > Set data points with query estimate less than μ4s
3:
E
4: For H4s E M,, create set Qum
5: procedure INITIALISE( X, Q 8)
6: n', + [|) m
N [log(2n)) (2n')1
D C a universal constant Number of independent estimators used
7: K1 + M.N
8: Jp: - log 2n' for μa M
+ See Definition 2.3
9: PREPROCESS(X,
D Initialise the (Charikar et al., 2020) data structure (Algorithm 2)
10: EEERROCESSQURYYPOINN
Q.
b> (Algorithm 4)
procedure ADDQUERYPPINT(Q))
Aq + QUERYPPINT(XX.
(Algorithm 3)
13: Store Paq
14: Add all sets Qu: such that Aa & p4
15:
ADDFULLHASH(Q)
(Algorithm 4)
16: procedure ADDDATAPOINT(2)
17:
n + +
if n n' n' then
INITIALISE(X Uz, Q,e)
We reconstruct the data structure
20:
else
21:
ADDPPUNTANNUUUPATTQUUUSSSSS Q,E)
(Algorithm 6)
22:
procedure DELETTQQUERYPOINT(Q)
23:
DELETEFROMDATA(2)
(Algorithm 0)
24:
Delete Ag
Algorithm 2 DynamicKDE Preprocessing
1: procedure PREPROCESS(X.
2: Input: the set X of data points, and the precision estimate &
3: for E M do
4: for a = 1, 2,
K1 do
D Ki Ollog n' n2²²) independent repetitions > Jn, log 2n' geometric weight levels
5: for j = 1, 2, ................................ Ju do
6:
K2, 200 log n' Puear
K2
See Lemma 2.5 and (2.1) for def. of Pnear.j and ky
7:
Psamp +- min 21+1 Sample every x E X w.p. Psamp- and let Zy be the set of sampled elements for .K, do
8:
9:
10:
Draw hash function Hugagge from hash family H (Lemma 2.5)
11:
for x E Z do
12:
Store x in the bucket Biunmms,ee (x)
Sample every x E X w.p. Store X pn.a
1. 2n,, and let X X be the set of sampled elements.
14:
> Set X ni.a will be used to recover points beyond L
13

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Algorithm 3 DynamicKDE Query Procedures
procedure QUERYMUESTIMATEEXXX q.
2: Input: set X of data points, query point q. precision estimate and KDE estimate 14.
3: for 1, K1 do
O(logn'/s* independent repetitions
4: for = ........ J/c do
5: K2, - 200 log ri' Pnear.j
6: for { 1,2..... ..... K2, do
7:
Recover points Bi (q) such that E 1.3 Recover points Xur.o such that x E +,, < set of all recovered points this iteration for Xx E S do
8:
9:
10:
11:
Wy +- k(x,, q)
12:
x; E L for some j [Jpcl then pv + min | 1}
13:
else x, EX (USELum) then
15:
Pv t 1 Za t +Ex, Ex,Es wp/ps
2n
17:
Store 7g
18:
for b 1,2,.... N do 5mb
Get median of N O n) means of size 0(1/e²)
7...b m
2a=(b-1)mn Zqa
20:
return Median Zg. Za
Z x)
21:
22: procedure QUERYPOINT(X, a,
23: Input: set X data points, query point q, precision estimate E. for μ4 E [[log((n') (21g (1,, /Mo] do
if QURRMUUSSTIMATEEEX 54 μ4 then
26:
return QUERYMUESTIMATE E, M441)
If estimate is larger than 14s return the previous estimate.
27: return
14

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Algorithm 4 DynamicKDE Full Hash Procedures
1: procedure PRePRocESsQuRRY Q,E)
2: Input: the set X of data points, the set of query points Q, and the precision estimate e.
3: for q E LEQQ do
4: Pq f +-QUERYPOINT(X, 9,
5: Store Pa
6: Add q to all sets Qu: such that Pa < 14
for H4 E MM do
8:
for a = 1,2,.... ..., Ki do
9:
for j = 2, Ju, do
10:
K2,j - 200 log n' P Puear
for 1,2..... K2 do
for q E Qu, do
Store q in full bucket B Bi (q) corresponding to hash value H (.
14:
15: procedure ADDFULLHASH(Q)
16: Input: new query point
17: for 14 > iq do
18: for a = 1, 2, ..., K do
for j
2, ................................ Jm. do k2
20:
K2, -- 200 log n' P
21:
for = 1, 2, K2,5 do
22:
Store in full bucket Bi
(q) corresponding to hash value H (
Algorithm 5 DynamicKDE Delete Procedures
1: procedure DELETEFROMDAAT(22)
2: Input: Query point q to remove
3: for E M do
4: Remove q from Qp:
5: for a = 1, 2....... K₁ do
6: for j = 2........ Jm. do k2
7:
K2, + 200 log n' Puear
8: for f = 1, ..... K2 do
9:
Remove from full bucket B
Bagaas.. (q)
B.1. Analysis of the INITIALISE and ADDQUERY procedures
We first analyse the INITIALISE Q,=) and ADDQUERYPOINT(2) procedures in Algorithm 1, whose corresponding subprocedures are presented in Algorithms 2, 3, and 4. At high level, the analysis begins by bounding the expected number of data points within each hash bucket (Lemma B.1). Subsequently, it establishes the query time complexity (Lemma B.2), shows that the estimator produced by QUERYMUÉSTTMATT is nearly unbiased (Lemma B.3), and provides a good approximation to the true KDE value with high probability (Lemma B.4).
We assume that μ4 is an estimate satisfying Ma & μ4; we will justify this assumption in Remark 1. We first analyse the expected number of data points to be sampled in each bucket Bit (g).
Lemma B.1. For any a j. E, it holds for Qp. that
E B
[[(x x Xpes
H Hugaaell)) H Hmaas(x))|]] = Ö(1)
any for E Qu, that
Etggnsee [1(x E Hx),s,,(()) Hm.a.. (q)[) (2)+1
H
15

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Proof. We compute the expected number of collisions in the bucket Bppaandd (q), and our analysis is by case distinction.
Case 1: j' & j. It holds by Lemma 2.4 that
1
2 Mq & 2 pii
which upper bounds the number of points that could collide from these geometric weight levels. Since every data point is sampled with probability 1/ (2/+1p)) p4) in this iteration, the expected number of sampled data points is ((1).
Case 2: j j & Jp: + We analyse the effect the LSH. Note that the jth iteration, we choose an LSH function whose corresponding distance level is rj, and use
i-j 12 B)
k 2 Kg
max
log Prear.j
?= pn +1
the numher of concatenations. Then, it holds for p E 1.g. that
PH-EM (p) -H & < (1
where e 2 Gr. = min بيية O (logl/" and p - Puear.y- Hence, the expected number of points from weight level Ö(1, where the last line holds by the choice of k. Combining the L. in the query hash bucket O 22 p ( two cases proves the first statement.
The second statement holds for the same analysis, but we have instead that 1.9. < 2 Ma & 2 pe for Qay.
The query time complexity for QUERY QUERY MUESTITTET q,
6, Mi)) follows from (Charikar et al., 2020).
Lemma B.2 (Query Time Complexity, (Charikar et al., 2020)). For any kernel k, the expected running time of QUERYMUESTIMATE X, q. e, 14) (Algorithm 3) is e-2 o(1) cost(k)..
Next we show that our returned estimator gives good approximation with high probability. Lemma B.3. For any E Rd,, Mq E (0, 2m1). pa > Pa. E (1/n2, 1), the estimator Zq for E [K1] constructed in QUERYMUESTIMATEE X, q, é, (4) (Algorithm 3) satisfies that
n Ma EiZqal & Mq-
Proof. We first fix arbitrary j and at, and sample some point p E Lg.. By Lemma 2.5 we have
PH H H)) > Prear.j"
=
Since repeat this process for K2 200 log n4 Pnear. times, it holds with high probability that any sampled point from band L.g. is recovered in at least one phase. By applying the union bound, the probability that all the sampled points are recovered is at least 1 -
-ky
We define Z A Zq and have that
11
E[xi]
W/s
Ps
)) ps & B(xi] & Pt, which implies where Xi = 1 if point is sampled and Xi = O otherwise. Hence, it holds that (1 - nn
that (1 1n Ma B[Z]+ & Pq.
Remark 1. Lemma B.3 shows that the estimator Zq is unbiased (up some small inverse polynomial error) for any choice of μ4 2 Pq. Therefore, when μ4 > 4pq. by Markov's 's inequality the probability that the estimator's returned value is larger than is at most 1/4. By laking O(log w1) independent estimates, one can conclude that (t; is higher than Pa
if the median of the estimated values is below ps, and this estimate is correct with high probability. This is achieved on Lines 18-20 of Algorithm 3. To ensure that we find a value of μ4 that satisfies pa/4 < Pa & μ4 with high probability, on Lines 18-26 the algorithm starts with μ4, = 2n and repeatedly halves the estimate until finding an estimate Pa >> p4i at this point the algorithm returns the previous estimate based on p141-
16

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Lemma B.4 (CCharikar al., 2020)), For every q E R4, Pqq E (0, 2n1). E (1/nq; 1), and b4 satisfying pu/4 & Meq & po the procedure Q q,8,, (Algorithm 3 in the appendix) outputs a (1 + appprxxiimtto Pa with high probability.
Proof. Let Z z. and we have that
27
E
E[Za|
E
Σ
Xi
W/
Pi
PIEX
Σ E XiXi
+
Σ vE(mL)
E
X
PiPj
p
w
w
WeWl
+
I[
1| +
Ip + 1]
pi
Pi
iE|mu]
E [m,]]
2
Wi 1[p * 11
Σ
Wi
+ max /E|m1]
wi [E|m1)
Pi
iE (E(m1)
< 2 (Hg)
)²
max
{wi 20t) p4 Ma
jelJn. 4
< 8pc:
(B.1)
where the second inequality follows from
Tpp = 1] & w²
Pi
and
Σ
ws) = Σ w + Σ w?
itj
aE(mg]
and the third inequality follows from (Mq)² CE, w 2 and pj > 1/ (25+1) 11))
Let
bm
Z 2 Zq.b
Zq
m7
(=(b-1))++
be the empirical mean of m such estimates, computed on Line 19 of Algorithm 3. We have that
P [| pal
> {nnaa
< P
[1
E[Z]| spq - -I[[ Mall
P 11 E|Z|| > (s - n Pa]
E
(5 n 9)² (pq))
128(Mg) )
m (e ni 9)² 2 (mq)
where the first inequality follows from 7/ |7- < -|2] + |B|2]- the second one follows from |F[2] > (1 (1-n Ma
(Lemma B.3), the third one follows from Chebyshev's 's inequality and the last one follows from E|Z²] < | < Suu /m and μ4 < 4/g- By setting m = - for large enough constant C' and taking the median of O(log(1/8) of these means we achieve a (1 + apparooxxmmtio with probability at least å per query.
B.2. Analysis of the OODDATAPOINT procedure
We now analyse ADDDATAPOINT(2) in Algorithm 1. If the number of data points has doubled, ADDDATAPOINT(22 calls the INITIALISE(X, +,=) procedure. Otherwise, ADDDATTAAPOAAAAUUUUAUUUUUUUAAAE Q, is called, which we describe in Algorithm
17

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Algorithm 6 DynamicKDE Update Procedures
1: procedure ADDPPUIN/ANOUPPXXEEUUUERUE
Q,
2: Input: New data point the set of query points Q, and the precision estimate
3: for μ4i E M do
4: for a = 1, 2,
K do
5: for j = 1, 2.
do
6:
Psampling f min 27
7:
if is sampled with probability Psampling then
k2
8:
K2.j f- 200 log n2' Pnear for = :,2..... K2,5 do
9:
10:
Store z bucket B Recover q Bit (z) such that q Qp. \U Quy and q L3
12:
Sample with probability 2nx if z is sampled then
13:
14:
Add z to Xp.a
15:
Recover E Q such that q E Qu Uy Qn and q L3 +1
16:
S <- set of all recovered points from the full hash in this iteration
17:
for E S do
18:
Wq - q)
19:
if E 1 for some j [Jp]] then
20:
Pq f- min
21:
else if z E X
USE(J,, L9 then
22:
Pq t- In
1
23:
Za += Wa/Pa
Zq [a/m] += wa/ (mpp)
A> Update empirical mean (Algorithm Line 19)
25:
Pg + Modian Zq.11 Zq.2..... 2q.0) ......).....)))
P> Update median
if Ag p4 then
27:
Que + Que (q)
28:
Remove from every Bir pe ve (4) for all d' E [Ki),5' E (Julle' E K2.9
29:
0g + QUERTP e)
To analyse the performance of ADDDATAPOINT(Z) the analysis first establishes that the KDE estimates are correctly updated after running the procedure (Lemma B.5), ensuring that Aa remains a (1 + a)-approximation of la with high probability, Subsequently, it demonstrates that total number of times any individual query point q updated during a sequence T data point insertions (1) with high probability (Lemma B.7).
Lemma B.5. After running the ADDDATAPOINT(2) procedure, holds with high probability for every E Q that Pig is a + e -approximation of Pa:
Proof. We prove that running the initialisation procedure INITIALISE U 2, 2,),) is the same as running INITIALISE(X, e, and then running ADDDATAPOINT(2).
We first examine the ADDPOUNTANNDUIIIIEQUUURSSSS Q, procedure (Algorithm 6). On Lines 7-10 and Lines 12-14, the algorithm samples the point z with probability min + and 2 respectively: sampled in Lines 7-10, the algorithm stores in the bucket corresponding hash value Hu.a, if is sampled Lines 12-14, the algorithm adds z to the set X This is the same as sampling and storing z in PREPROCESS(X X Uz, e) procedure (Algorithm 2) on Lines 8 and 13, which is called during INITIAL.SE( Uz, Q, Q, e). the stored points in Hu..as.e and X,.aa for all p4 E M, a e [K]. j E [. and & E [22 are the same as the ones after running INITIALISE(X X U Uz, Q)
Hence, after running INITIALISE(X, Q, followed by IDDPONNTANDUDDDTEQUUUEERN
18

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Next, we prove that the estimates Pa are updated correctly for every q Q. Without loss of generality, let q be query point such that q Qu: Ugtci Qug-
We first note that, when running INITIALISE(X. e (Algorithm 1), the KDE estimate for q returned by running QUSTIMMEST (4) (Line 26 of Algorithm 3).
When running INITIALISH X Q, e). if is sampled on Line 8 during PREPROCESS e) for any iteration a E [ E [.p.]. then z is stored in the bucket BBuq.ag.ee (z) for all & E [K2,] Moreover, if z is sampled on Line 13 for any iteration a E [K]]. then z is stored in Xi,a. In this case, if (. a. and 2 E I for some & E [Kg if E - then Z would be included in the set of recovered points S for the iteration a E [1]] and consequently in the estimator Zq.a when QUERYMUUSTTMMTTEE X U q. e, 14) is U z, Q, (Algorithm 4).
called during PREPROCESSQUERYPOON
- On the other hand, we notice that, when running ADDPOINTANNUUPIITIUUUUUSSSS Q,=), is recovered if () Hps.a.ee = Huzsa.jer()) and q E 1 (Line 11 of Algorithm 6) or (ii) E -3,,+1 (Line 15 of Algorithm 6). Furthermore, (i) q E L.g. if and only if z E Lg for any j' E [J + 1.. and (ii) the buckets Bi, pac.o.s. BHa (q) are populated using the same hash function (Line 13 of Algorithm 4). Therefore, q is recovered at iteration a E [K]] when running POAPPPINAAANUUAATUUUUEEEE
(q) and
(z, Q,E) if and only if z included the estimator Zqna when QUERYMUESTIMATER UZ q, e, p4) is called during PREPROCESSUUERY PEERTPOIIS((XX (XU XU z, Q, E). Then, the estimator Za is updated accordingly by adding z through Lines 17-25 of Algorithm it would be done through Lines 10-20 of Algorithm 3.
Finally, if Aq > Hs, then we re-estimate the query point on Lines 26-29, to ensure we have the correct estimate Pq. We also update the set Qre accordingly, and remove q from every Bi, Bit of (z) for all a' [K1].
j' 1. and l' E [K2
Combining everything together, we have shown that performing the initialisation procedure INITIALISE X Uz, Q.e) is the same as running INITIALISE(X, e) followed by ADDDATAPOINT(A
Next, we prove how many times any individual query point q updated as the data points are inserted using the ADDDATAPOINTIC procedure. Let X1 & "X,,..,,,,, } be the set of points presented at the time when q is added, and let Zr _ {zi...., } be the points added up until the query time T. We use z; to denote the new point added at time t. Note that it holds for the points Xy at time T > 1 that X² = X1 U Zr. Next, we define the event FA that
Pa. E =1 k(q. X.),
(B.2)
where e is the maintained query estimate for q at time from Algorithm 1. By Lemma B.4, we know that F happens with high probability. Moreover, for large enough constant C on Line 6 of Algorithm 1, ensure that this happens with high probability at every time step l. Therefore in the following we assume F. happens. We also introduce the following notation.
Definition B.6. We define Ta to be the time step such that
k(q, X9 17.
= X1) + Σ k(q,2.) & 14
and
T
k(q. 17, +1) k(q. +
k(q. 2;) > us.
By definition, Thg is the last time step at which the KDE value of q is at most p4- The next lemme analyses the number of times a query point q is updated.
Lemma B.7. Let q be maintained query point by our algorithm. Then the total number of updates U7 during T insertions is, with high probability, U. = Õ(1).
19

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Proof. Since the KDE data structure can be re-initialised most log(T) (1) times (ef. Line 18 of Algorithm 1) through the sequence of T updates, it suffices for to analyse the number of times q updated between different re-initialisations:; we assume this in the remaining part of the proof. To analyse the expected number of times that q (Line 23 of Algorithm 6) is updated throughout the sequences of updates Zr, we define the random variable Y2, by
A y4 a.t {
1
if estimate Za,a is updated at time otherwise.
Let Eg, be the event that estimate Zq is updated at time t, and we assume without loss of generality that 77, for some pv, First note that estimate Za is updated if E S (Line 16 of Algorithm 6). Furthermore, because Pqtt-1 E () k(q, XI-1) by (B.2) and T -1 < 1 & 74 one of the following holds:
<t T7
① q Quy \ (UrErQHs))
(ii) e Qu \ (1yev-1Qu)))
(iii) q Quen (Urer41 0ny)
Additionally, it holds that q E 1 for some j' E Jug-
By these conditions, q is included in S at time if and only if is sampled at either the iteration for py E M, py-1 E M or Ma++1 E MM (Line 3 of Algorithm 6), and the corresponding iteration j' Jppts on Line 7 of Algorithm 6. Therefore, it holds for E (19 py- T4 , that
1
2k(q, z4)
P P[Ea,] & 23' pV-1
< 2 pb
(B.3)
fby
where the last inequality uses the fact that q E Lig (Definition 2.3). Similarly, have that
k(q. zz)
a.t
4p
Let 19 2 EK, Σts yq, be the total number of times that the query point q is updated, and we have that
K1
T
E
E
yq
6.1
a=1
K1
T
Ca.t
Ki
Σ
[&
a=l pa EM 1=18
19
K1
2k q. 2.)
a=1 EM 1=
Ki
2p
P4
a=1 P.EM
2. K1 M
= =Ō(1),
20

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
where the first inequality follows by (B.3) and the second holds by the fact that
keq. 2:) & pe-
P4--1
Similarly, we have that By the Chernoff bound, it holds that
1
E E
Ki JM
4
e
KI-IMI/4
P P > 10- E2
<
< exp (-K1 MM]) o(n
1010
for some constant c, and we have with high probability that 27 < 20 K1 |M ((), which proves the statement.
B.3. Proof of Theorem 3.1
Proof. We start with proving the first statement. Notice that (REPROCESS(X,E) goes through M Ki Jp. K2,5 iterations, where M = (llog(m1)) )), Ki 00===2((=g(00 2-1og(m1)) Sn, (Olog(n)) and K2.j ((lo((m))ccos(() Since ky = (() by definition, the algorithm concatenates Õ(1) L.H functions. By Lemma 1, the evaluation time H*(x) for any H E Ht
is 11 o(1) and hashing all n, points yields the rumning time of E :n [++(1) cost(k) for PREPROCESS e) in the worst case. Since we start with an empty set of query points Q = 0, the running time of PREPROCESSSUERRPPONTSSCCCCCC
can be omitted. This proves the first statement.
The guarantees for ADDQUERYPOINT(q) in the second statement follow from Lemma B.2 and Lemma B.4. The running time for DELETEQUERYPOINTIQ follows from the running time guarantee for ADDQUERYPOINT(q)
Now prove the third statement. The correctness of the updated estimate of Na follows from Lemma B.5. To prove the time complexity, we notice that, when running ADDDATAPOINT(Z)) the procedure goes through M K₁ J K2 iterations, where M = O(logn) n1), K1 O(log(n)/=)) Jn, = Olog n)), and K2,j = (log(n) cost(k)). In the worst case, z is sampled in every iteration on Line Algorithm 6, and needs to be stored in the bucket BHr (z). Therefore, the running time of updating all the buckets B (z) for new is at most e (1) cost((:). To analyse Lines 17-26 of Algorithm 6, we perform amortised analysis. By Lemma B.7, it holds with high probability that every q E Q is updated Õ(1) times throughout the sequence of data point updates. When q E Q is updated, the total running time for Lines 17-26 is
Ō 2. K25 = 2cstkk))(kk) Ō(E cost(k)),
due to Lines 28 and 29, Let 7" be the total number of query and data point insertions at any point throughout the sequence of updates, and m A [Q). Then the amortised update time is
cost((k) ( =ō m mm.
( cost(k) - Ō (==².cost(k))
m
where the second inequality follows from T > m, the algorithm started with empty query set Q 0. Combining everything together proves the running time.
C. Omitted Detail from Section 4
This section presents all the detail omitted from Section 4, and organised as follow: Section C.I presents and analyses the algorithm for the initialisation step; Section C.2 presents and analyses the algorithm for the dynamic update step.
C.1. The Initialisation Step
In this subsection we present the algorithms used in the initialisation step, and analyse its correctness as well as complexity. We first introduce the tree data structure (Algorithm) 7) and the initialisation procedures for constructing an approximate
21

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
similarity graph (Algorithm 8). The analysis then establishes the probability that sampling path passes through any internal node of the constructed tree (Lemma C.1), which is erucial for the subsequent correctness and time complexity analysis that follow Macgregor & Sun (2023) to a large extent.
The following tree data structure will be used in the design of our procedures.
Algorithm Tree Data Structure
1:
LEAF(X,)
2: Input: data point x,
3: data X
Stores the data point Stores the sampling paths ending at this leaf
4: paths <- NIL
5: NODE(X)
6: Input: set of data points X
7: data <- X
> Stores the data points in the subtree rooted at this node Number of data points in the subtree rooted at this node
8:
size + |X]
9:
kde NIL
Stores the DynamicKDE structure Left child node Right child node <> Parent node
10:
left <- NIL.
11:
right < NIL
12:
parent + NIL.
13:
paths + NIL
Stores the sampling paths passing through this node
Based on this data structure, the main procedures used for constructing an approximate similarity graph in the initialisation step presented in Algorithm 8. We remark that, for any set X of data points, always set e 1/ log" |X] when rumning the DYANMICKDE.INITIII presentation of the analysis without loss of generality.
procedure. Choosing fixed value of in this section allows us simplify the
To analyse the correctness and time complexity of the algorithm, we first prove that, for any data point x; E X, the probability that its sampling path ex,, passes through any internal node T depends on the KDE value of x; with respect to data
Lemma C.1. For any point x; X, tree T constructed by CONSTRUCTGRAPH (Algorithm 8), and sampling path Px.. (for any & E [L], the probability that e passes through any internal node T' of is given by
k(x, .data)
2k(x,, T .daaa)) 1(x,, T.data)
< P E T -paatss)
2k(x;; T. .datt)
Proof. Let X = {xI...., ] be the input data points for the CONSTRUCTGRAPI(XX.c) procedure in Algorithm Then, in each recursive call (at some internal root T") to SAMPLE (Algorithm 8) we are given the data points X,, A T le..fft.data and X å T" lata we have that the probability of assigning Px,, to T7" paths is
data as input and assign Px., to either Thl & T or Til & T" right. By Line 32 of Algorithm
Ti
P [PPx., E T paths Pxx,, E T T''paths)
T fxx
By the performance guarantee of the KDE algorithm (Theorem 3.1), we have that T" ,xx E (1= -KT-kk(T"dd data, x:). This gives
k(x,, data) I+e k(x,, "..aaaa.aaaaa
< P [Pxx, e Ti. paths Px T pathhs
1 +
k(xi, Ti data)
datta
(C.1)
1-6) k(x;, T" T".t,ta))) .dta)
Next, notice that holds for sequence of internal nodes Tı, T2..... .,. To with T.ppaennt T.+1 <i<r 1) that
P ( E Ti.paths]
II
P P E Tathaths pathss,
16jšr-1
22

---

return T Dynamic Similarity Graph Construction with Kernel Density Estimation
Algorithm 8 Initialisation Procedures for Constructing an Approximate Similarity Graph
1: procedure INITALLISETRER(X
2: Input: set X data points
3: if | then
4:
return LE)R(X)
Leaves store individual data points x; X
5: else
6:
T + (X)
7:
m 4 2 211og(11/23) X1/3)1111111111111111 ft + |X]
< Nearest power of 2 less than or equal to n/2
8:
X < X(1 á - m), X & X( 1 X
>> Split the dataset into two
9:
TE & INITIALISETREE Xt), TR INTIALISETREE(XA)
T.left t- Tr. T .right < Tn
TE kde WWW.AMICIDE.NNITIAIISSEECC
(Algorithm
Top m
12:
TR.kde <- DYNAMICKDE.,NTTTAA.N Xx, 0, log
13:
14:
15:
procedure SSMPLE(S,
Input: set of points x,, KDE tree representing data points X, sample index l
Output: E {(xx; xj) for some i,
18:
for E S do
19:
Px.e Pxie UT
20:
T.paths t T .atths U (Px..} if ISSLEAF(7)) then
B> Update and store sample paths
21:
22:
return S x T.aaa
else
TL T.left, X1 -a.a
25:
TR Triight, Xn data
26:
for E S do
27:
Ti.Pxi + A...K.AADDQUURNPIIIIISS,
(Algorithm 1)
28:
TR-Pxx & TR. TR. ADQQUEERQRRRSSSNNTTSSS
29:
SL + 0, Sn +
30:
for X; E do
r Onif
T2.Rx;
32:
if & Th, TRR-AA,
then
33:
St - St (x:}
else
SR SR U {x,) return SAMPLE(SL. T2 SAMPLE(SR, Ta, e)
36:
37:
38:
procedure CONSTRUCTGRAPHC2)
39:
Input: set of data points X
40:
T t INITIALISETREE(X)
T.kde +- DYNAMICKDE.IIITIALLEE (X, X, log' X
(Algorithm
42:
E+0 0
43:
for E do
44:
E, < SAMPLE(X,T,))
45:
E+ EUE;
for (x,, ) E,
i(i,j) t L. k(x,, x kd..ee T.kde.
48:
if minn kdee T.a..T..n T.kde, } T f then
49:
Bx, + BBx {x:}
Track neighbors with higher degree
wo(x;, X,) += x(x,,,)
50:
((t))
51:
return T, G (X, E, wc)
23

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
where each term in the right hand side above corresponds to level of recursion of the SAMPLE procedure in Algorithm and there most (n1)())) terms. Then, by setting T, T, Ti T', (C.1), and the fact that the denominator and numerator of adjacent terms cancel out, we have
[lg((1)]]
k(x,, T'. ddaa))) k(x;, T Tddaa)
PXxee e E T' ppths)
E+E
+
[og(n)))
k(x;; _dtaa)
-
k(x,, 7 .ddata)
For the lower bound, we have that
[og((1)]
(1+s)
3 (1 22) [log(m))]
2 - 33 Bolo((n1) > 1/2,
where the final inequality follows by the condition of that & < 1/ log"(n1)..
For the upper bound, we similarly have
11 + [1g(1))]
< (1 36) [la((n))] exp (3c (o[[oo())))) & 2/3 2,
1-c)
where the first inequality follows since < log"(n1))
The remaining part of our analysis very similar to the proof presented in (Macgregor Sun, 2023).
For each added edge, CONSTRUCTGRAPH(XX (X) computes the estimate defined by
k(x,, x,) A=-1 min (ixes Pix, (ii 2 6C
logn1
where for the ease of notation denote f.kde.fxx. Pxx, and T. T.kde.fxx Pxy. If edge (x,,x)) is sampled, then the edge is included with weight k(x,, x)),((i,)) j). The algorithm in (Macgregor & Sun, 2023) is almost the same as algorithm, with the only difference that in their case the edge is included with weight A(x,, /)) where
p(i, 2 6C k(x,, x,) log nı
( [ix:
1
-
(6C- k(x,,x,) x,) log m1
?
Ac+1
imx
Ac+1
jix; jxx,
Notice that
k(xi, Xx) (3i)-logg -log
(
+ 1
p(i,)) < 60
< 2
Act1
Pix
Pox,
Assuming without loss of generality that
60 k(x;, x;) log
(
1,
Ak+1
fix.
prx,
we have that
p(i.)) > 30 k(x,, x,, logni ni
(
1
@(i,j) 2
AR+1
pxx
Dxx,
As such, the scaling factor (i,,)) in our algorithm and ji,, in the algorithm of (Macgregor & Sun, 2023) are within a constant factor each other. Therefore, to prove the first statement of Theorem 4.1, one can follow the proof Theorem of (Macgregor & Sun, 2023), while replacing each (ii,j) with ((i.j) appropriately.
24

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
C.2. The Dynamic Update Step
In this subsection we present the algorithm used in the dynamic update step, and analyse its correctness as well as complexity, Our main algorithm for dynamically updating approximate similarity graph is described in Algorithm 9, and the RESAMPLE procedure can be found in Algorithm 10.
Our analysis for the dynamic update step first covers the running time of the SAMPLE((x); T, and RESAMPLE(T, Px.e) procedures (Lemma 4.2). It then proves a sequence of lemmas bounding the total number of sampling paths that need to be resampled (Lemmas C.3, C.4, and C.5). Finally, the correctness follows by the fact that the update step is equivalent to full reconstruction of the tree after an update (Lemma C.6).
Algorithm 9 Dynamic Update Algorithm for Constructing Approximate Similarity Graph
procedure UPDATEGRAPI(G (X, E, wG), T,z)
2: Input: approximate similarity graph G, KDE tree T, new data point
3: A < ADDDATAPOINTTREEI/
(Algorithm 10)
4: Enew (-
5:
for l 1.,, L do
D> Sample neighbours from the new vertex z
6:
(2.X,) f- SAMPLE (z): T)
7:
Enew f- Enew U (2.,x)
L klzz, x,)
8:
(ii,j) f min (T kkdeeefe. kkde,xx))
wil (z, x,) += x()
9:
if min (T kklkee.fe. T.kde. T T.de. then
11:
Bx, t Bx, U {22
12:
E < EU Enew
13:
for x; such that T. kde.pxx has changed do
14:
Let degata be the old estimate of T kde,
15:
for X, E Bx, do
degold
xx), & xx),
Update scaling factor of adjacent edges
min kde. f : T.dde//ix,
min (T Kde.exxxxx T T.kde.ffs.... fix, f then
18:
Bx, + Bx; {x,)
19:
for Px,. do
20:
Let T be the parent of the highest internal node where Px,,e was fetched
21:
for T below T' such that Px., E 7T "ptttths do
22:
Remove Px,, from T -ptths
23:
Remove x; from the query set T left.kde and T rde Remove T from Px.!
25:
Let xj be the previous sampled neighbour of x; (i.e., leaf in Px.,))
k(x;,x,) ((,
26:
wel (x;,
>> where (ii,j) is the previous re-scaling factor
27:
if we (x, (x) = then
28:
E + x(x,,,)}}
29:
(x,, x5) < RESAMPLE(TT) Px..)s)
> Resample path (Algorithm 10)
30:
(x,, x5) & then E EU ((xxx,
L. L-K(x,, xj)
32:
C* (i, + min(T.ke ....dd.jxx.. fix, T.kde. jix;
min (T kkdeeeefpp.. (ax. T.kde. bxx; } = T rde fix; then
34:
Bxz= - Bx; {x:}
Update neighbours with higher degrees
x(x,,x))
35:
wo (x;, x;) +
Th (i,
25

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Algorithm 10 Tree Update Procedures for Constructing Approximate Similarity Graph
1: procedure ADDDATAPOINTTREE(T 2)
2: Input: KDE trec/node T, new data point
3: if ISLEAF(TT then
4: X 4 T.data
5:
A 4 -.parent.paati paths
Store paths that need to be resampled
6:
Tnew < NODE x))
Tnew.left left LEAF(x)
8:
Thew-right LEAF((Z)
9:
Tnew kde <- INNTAICCEEEETTTLLISEEEEEEE 0,E)
Initialise new KDE data structure
10:
Replace the leaf T with node Tnew
11:
return A
12:
else
13:
T T.kde.A ADDDAATAATAPONN
D> (Algorithm 1)
14:
Let A be the set of points X; E T .kkkeQQ such that T.ke. changes after adding
15:
A +- (Px,, T www.prr.ttpppm pathss x; A}
16:
if T sefe & T sright..size then
17:
return A U ADDDAVAPOINTTREE(1.CC z)
18: else
19:
return ADDDATA ADDDAATAPONNTTTEETTTnrngg
21:
procedure RESAMPLE(T,7 ex.,))
22:
Input: KDE tree/node T, and sampling path Px,, Px., Pxt,t (T)
23:
24:
T.paths + -attss U (Px..}
D Update and store sample paths
25:
if ISLEAF(TT) then
26:
return x; x T.data
else
28:
Tr T.left,
X T T..eft.data
29:
TR < .right,
X +- T rright. data
30:
AnddeAADDDEERPPINNTCS.S if x; & TT, Q
D> (Algorithm
31:
(x;) if kde.
32:
N~ 1
TL.px,
33:
ifr & Tr.Axx TR-ffx then
34:
return RESAMPLE(TI, Px.t)
35:
else
36:
return RESAMPLE (TRMPLLEETTHA Px..))
C.2.1. RUNNING TIME ANALYSIS
Proof of Lemma 4.2. The running time of the two procedures dominated by the recursive calls ADDQUERYPOINT(ss) By Theorem 3.1, the running time of adding query point is E no(1), cost(k).. Since the depth of the tree T is most [log n. there are at most [log n recursive calls to SAMPLE and RESAMPLE, Hence, the total running time of SAMPLE and RESAMPLE is =2, (1) (I:).
Proof of Lemma 4.4. By the tree construction, we have that P(q E T'kkd.Q) = IP[36" such that Pq. T', T''patts], and
2k((q d'aaa)
P(E such that p T' pattst < L- PlPq.. T' .atthhh
L
k(q. T .daat)))
L. 2k(q. T' .'de.X)
=ō [4j
k(q, 7 X)
14:
26

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
where the first inequality holds by the union bound, the second inequality follows by Lemma C.I, and the last line holds by the definition of Qp:-nn(() and L. ((1)
Next, we state Lemma 4.5 more precisely and provide its proof.
Lemma C.2. Let z be the data point that added to T through the ADDDATAPOINTTREE(T z) procedure in Algorithm 10, and T' be any internal node that lies on the path from the new leaf LEAF(Z) the rool of T. Then it holds for any i E [[log(2 T T.kde.n' I[} T' .dkeke K E [J and that
Ei Si 11 E T'ke. p4 T kde. H ((aa,e())==T T'.'''kkk .de. au m. (9]]] = -m -2+1).
Proof. We first remark that, except for the dynamic KDE structure stored at the root Tdee, it does not necessarily hold
that T' k.kkeee- = T' kde.X; this is because that the query points stored at internal nodes are the ones whose sample paths passed through this node, and the data points are the leaves of the subtree T'. Hence, to analyse the expected number of
colliding points in the bucket T' kddkBB o. (z), we need separately analyse the contributions from q Qua (T)) for d' 2 i. To achieve this, we apply Lemma B.1 and have for i' that
Eap KK T.E.T.Ke likkeeeuu I kde. H (.....((2)) = T r'.kde. a. e (q) = 0 me))
(C.2)
Therefore, it holds that
Egpanna llfq E T .d.kde.Qp.. [T..de. = = T' p. (q))ll
= pppsese
{q E T'ke.de..... kde. H H...aj,(z)) = -'k.de. a.je (q) and E Qpy (T)))
Vii
[1
T k'kee. I .7.kkde.. ( =T' kdk. H a j. (q) and q Qu (T')}]
Σ
[4i
llla E T T.kde 1T 1T'kde. p j.e T kde H ja.a...e (q)
(C.3)
pe
V3r
Mii 20+1 ui
(C.4)
= - (ny 2)+1),
(C.5)
where (C.3) follows by Lemma 4.4, and (C.4) holds by (C.2).
Lemma C.3. The expected total running time for T kddk ADDDATAPOINT(() (Line 13 of Algorithm 10) over all internal nodes T along the path from the new leaf LBAF(Z) to the root T is n()) cost(k)). Moreover, the expected number of paths (Line 3, Algorithm 9) that need to be resampled satisfies that [|| = Ö(1)
Proof. We first study the update time and the total number of paths that need be updated a single inter- nal node T'. Notice that, when T ADDPONNTANDUPDATEUURRR
(Line 13 of Algorithm 10) is called, the procedure in Algorithm 6 is called in the dynamic KDE data structure T' .de. Hence, we analyse in Algorithm 6.
the expected running time of ADDPOINTANDUPPATTOURN
First, have that executing Lines 7-11 of in Algorithm 6 takes K2 IT' .de. Bi...B........ (z)l n ro(1) time, where n' = I -aata the number of data points stored at T', and these five lines are executed with probability at most 1 1/(21+1 Since we only consider the collisions with points in T' kekkeee... Qu,, holds by Lemma C.2 that
[ kde. B an (2)) = δ (2)+2
E Hugge
27

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Hence, by our choice of K2,, (log(n') cost cost(k)), the expected total running time over all M4g a, and j of Lines 7-11 of Algorithm 6 is e cost(k) nno(1), The same analysis can also be applied for Lines 12-15 of Algorithm 6. Moreover, the expected number of recovered points in S (Line 16 of Algorithm 6) is Ó(1), as the expected number of collisions we consider is
E E
[IT Tr.kde.Bj, es ass.
[z)] O 14),
and these points are only considered with probability at most //(2++11))
Next, we analyse the rumning time of Lines 17-26 of Algorithm 6. For every q E S, the total running time for Lines 17-26 is O(= 2 K2,
+ = cos)(k)) Ō(= cost(k)), due to Lines 28 and 29.
Hence, the expected total running time for running A.de.AADDAAAPPINIIII at single T' is (E-2 nn cost (ostt))) (A)). As there most [log n nodes Tt that updated when is added and n' & n, the running time guarantee of the lemma follows.
i'
It remains to prove that E||A|| = Ö(1. Notice that, the number of points q E T' ..kkkee whose KDE estimate changes at procedure
T' is the number of recovered points in S (Line 16 of Algorithm 6). From the ADDPOINTANNDUUIATTTUURRRRR (Algorithm 6), it holds for every 14; and a that E[[s]] = O(1) as such for every T' the expected number of KDE estimates that change and therefore the number of paths that need to be resampled is Õ(1). As there are at most [log n trees T that are updated when is added, it holds that [[[LA|] Ō(1)
Next we bound the size of the set Bx, that keeps track of the neighbours x, of in the approximate similarity graph G that have higher degree.
Lemma C.4. It holds with high probability for all x; E that [Bx, & 14 L.
Proof. We first notice that Bx, = {x, E X T.kde.jix, > T jx and i E }x where Yx, - (. are the indices corresponding to the sampled neighbours of Xy. For every pair of indices J. and every & & L,, we define the random variable Zizje to be 1 if j is the neighbour sampled from at iteration L, and otherwise, i.e.,
{
= if =
Zigee
0 otherwise.
We fix an arbitrary x,, and notice that
L
1xx
Zza,e
(C.6)
t=1
==1
jux,
PPx
where for ease of notation we set Axx A kkdeexx and fxx, & T fix, to be the KDE estimates at the root T. We have that
E
Zyatee
E[Zy,ee
Dxxg T
Bxx fax;
Plyse o)
Axx >> fax;
2k((,,,
degx (Xg)
Axy > Pize
4k 4k xx) degx
Ax, > Pixe
4 L.
(C.7)
28

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Here, the second last inequality holds by the fact that
xx
px,
(1 - E dedxx(x)))) degk (x,)
degk (x;)
I+E
I+E
1+
2
where the last inequality follows by our choice of 1/6. Employing the same analysis, have that
R
Σ
Σ
Plyse < 4. L.
Jiney Dbx;
Boy b
We apply the Bernstein's 's inequality, and have that
100T2/2
P
Σ
Zisz E
Zzsiet
> 10L
& 2exp
4L + 10 L/3
j=1 Pxy Pxxs
1=1
75L.
= =2cxp
22
= o(1/n).
Hence, by the union bound, it holds with high probability for all x; E X that
Zia,
E
Σ
100;
{=1
1=1 2Pxx
Pxy >px;
Pxxy
combining this with (C.6) and (C.7), we have with high probability that ||xx 4L| < 10L, which implies that |Bx, < 147.
We are now ready prove the running time guarantee of the update step. Lemma C.5. The expected running time of UPDATEGRAPI(G, T, T, )) is o()) cost(k).
Proof. We analyse the running time of UPDATEGRAPH(G, T,z) step by step.
The ADDDATA Algorithm 10, which takes = o1)) cost(k) time by Lemma C.3.
procedure is dominated by the call to the ADDDATAPOINT procedure on Line 13 of
Next, we analyse the running time of sampling I. new neighbours of the new data point z (Lines 5-11). The algorithm samples neighbour x, using the SAMPLE procedure, which takes 5 (2)) cost(k) time (Lemma 4.2). To add the edge x,), the algorithm computes the KDE estimate TT T.kde.p2. which takes E = o cost (k) time, and the weight value k(z,x, which takes ((d) Ō(1) time. Since L Ö(1) the total running time of Lines 5-11 is e- n (1)...... cost(k).
For Lines 13-18, first note that the expected number of paths that need to be resampled is E[|A[ = Ō(1) (Lemma C.3), and the expected number of points x; such that T kdee fix, has changed is Ö(1). Since by Lemma C.4 it holds with high probability that |Bx,| 4 L = Ō(1), the total expected running time of Lines 13-18 is Ō(1)
Finally, we analyse the running time of Lines 19-35. The running time of removing all the stored data about the path Px.,e that needs to be resampled (Lines 21-28) is dominated by the time needed for removing all the stored information about X; in le.. and T T"riight.kdk for every T (Line 21). Doing this for all T takes e- . (1) cost(k) time, since there are O n) such trees T and in the data structures T lele.f.ke kde and T T*.right.kde kde, x; is removed from all buckets B Bia (xx), and there are = o( cost(k) such buckets. The running time of the rest of the loop (Lines 29-35) dominated by the running time for resampling a path Px,,e, which 2 (1)) (k) (Lemma 4.2). Therefore, by the fact that E[]A[] = 5(1) (Lemma C.3), the total
expected running time of Lines 19-35 -2 -2, (1))) cost(k).
29

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Combining everything together proves the lemma.
C.2.2. PROOF OF CORRECTNESS
Lemma C.6. Let G' = Uz E", we) ) be the updated graph after running UPDATEGRAPH(G, T,2), for the new arriving Then, it holds with probability at least 9/10 that G' is an approximate similarity graph on X U z.
Proof. We prove this statement by showing that running CONSTRUCTGRAPI(X) followed by UPDATEGRAPIIC,, equivalent to running CONSTRUCTGRAPH(XX Uz).
First, we prove that the structure of the tree T is the same in both settings: when running CONSTRUCTGRAPIIXX] ensure that the tree T is complete binary tree. Then, when inserting a data point using the ADDDATAPOINT(Z) procedure on Line 3 of Algorithm 9, z is inserted appropriately (by the condition on Line 16 of Algorithm 10) such that the updated tree is also a complete binary tree. Therefore, the structure of the tree T is identical in both settings.
Next, on Line 13 of Algorithm z is added to the relevant T' kde dynamic KDE data structures using the ADDDATAPOINTíA procedure of Algorithm 1. This ensures that the stored data points T' .d. at every internal node T' are identical in both settings and, by the guarantees of the dynamic KDE data structures (Theorem 3.1), the query estimates T kde.jiq for every internal node Ti' and any q E T kde. are the same in both settings.
For the new data point z, we sample L new neigbours (Lines 5-11 of Algorithm 9). By the previous points, it holds that the tree T is identical in both settings, and therefore the sampling procedure on Lines 5-11 in Algorithm 9 for the new data point is equivalent the sampling procedure on Lines 43-50 of Algorithm 8 for the point when executing INITIALISE( X 2)
Then, for any data point x; E X, let xx) E be one of its sampled neighbours edge after running CONSTRUCTGRAPH, holds that the scaling factor for the edge weight ue (x;, is
L k(x;, x,) i(i.)) min fxx T.kee...e.. fode.px)1
Notice that after running UPDATEG(Z). the scaling factor wG xj) can change due to a change in min(T (onn(T.keejiiie kde. px, fix, Without loss generality, let min(T Siin(T.kde.fiu. kde. T kde.jxxx, Line 49 of Algorithm 8, this case we have x; E Bx, We further distinguish between the two cases:
= T.kde. Pxy. By
1. If T .de. changes after running UPDATEGRAPH(()) then by the ADODATAAPIITTREEE(T z) procedure all the paths Px for & l & will be resampled and updated on Lines 21-35.
2. On the other hand, if T kde. changes and T T.kde.fix, does not, then the paths Px,, ending the leaf corresponding to are not necessarily resampled. In this case, the scaling factor is updated on Lines 13-18, and therefore Wor (x;, xj) is appropriately rescaled.
Let Pr, P T. .ptts be any sampling path that not resampled, i.e., Px,e & A. This implies that the KDE estimate of ' "T'kdee.ju does not change at any internal 'I' where Px,, is stored, and therefore the sampling procedure for e is identical in both settings.
Finally, let Px., E A be a sampling path that is resampled, and (X,, be the sampled edge (contribution) corresponding Px,,e- Before resampling the path Px.. starting from T', on Lines 21-28 the algorithm removes the stored paths Px,, e and query points x; from every internal node T below T', and removes the weight contribution to We (x,xx) Xÿ) from Px.,- Then, Lines 29-35, we resample new edge (x,x;), in an equivalent manner as sampling a new edge when running Lines 43-50 of Algorithm 8. Therefore, the resampling procedure for the path Px.. is identical to the sampling procedure for Px,,e when running INITIALISE(X* U Jz E), because the resampling procedure uses the updated KDE estimates at each internal node T', which are identical to the KDE estimates that would be computed in INITIALISE(X U z, E).
Combining everything together proves the lemma.
30

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Finally, we ready prove the second statement of Theorem 4.1.
Proof of the Second Statement of Theorem 4.1. Lemma C.5 shows the time complexity of UPDATEGRAPH((..: z), and Lemma C.6 shows the correctness of updated procedures. Combining these two facts together proves the second statement of Theorem 4.1.
D. A Additional Experimental Results
In this section, we provide some more details about our experimental setup and give some additional experimental results. Table 3 provides additional information about all of the datasets used in our experiments.
Table 3:
Datasets used for experimental evaluation. n the number of data points, d the dimension, and the parameter we use
the Gaussian kernel.
Dataset
d
License
Reference
Description
Synthetic clusters from mixture of Gaussian distributions.
blobs
20,000
10
0.01
BSD
(Pedregosa et al., 2011)
cifar10
50,000
2,048
0.0001
(He et al., 2016; Krizhevsky, 2009)
ResNet-50 embeddings of images.
mnist
70,000
728
0.000001
CC BY-SA 3.0
(Lecun et al., 1998)
Images of handwritten digits.
Numerical from NASA
shuttle
58,000
0.01
CC 4.0
(NASA, 2002)
space shuttle sensors.
Images of objects under a variety of lighting conditions.
aloi
108,000
128
0.01
(Geusehrnek 2005)
Numerical and categorical features of songs.
515,345
0.000001
CC 4.0
(Bertin-Mahien al., 2011)
Carlographic features used to predict forest cover type.
covtype
581.012
0,000005
CC 4.0
(Blackard & Dean, 1999)
glove
1,193,514
100
0.1
PDDL 1.0
(Pennington et al., 2014)
Word embedding vectors.
Categorical and numerical data from the 1990 US census.
census
2,458,285
68
0.01
CC BY 4.0
(Meck 1990)
D.1. Dynamic KDE Experiments
Tables 4 and 5 show the experimental evaluation of the dynamic KDE algorithms on several additional datasets. The results demonstrate that our algorithm scales better to larger datasets than the haseline algorithms. Figures 4 and show the relative errors and running times for all iterations, datasets, and algorithms for the dynamic KDE experiments.
Table 4: Experimental results for dynamic KDE, For each dataset, the shaded results correspond to the algorithm with the lowest total running time.
CKNS
DYNAMICRS
OUR ALGORITHIM
dataset
Time (s)
Er
Time (s)
Err
Time
Err
shuttle
32.942.1
0.146=0..02
0.840.0
0.07810.005
10.9
0. 10.024
aloi
11..0+10.7
0.050=0.006
19. 19.7+
0.010+0.000
46.9+
0.060+0.021
msd
14, 360.0+..0
0.385=0.000
1, 1,807.820.0
5.430=0.000
306.440.0
0.388
covtype
5, 650.3++19.0
0.159=0.002
309.2+2.1
0.018+0.000
151.7+4.5
0. 0.196:00.01
glove
2, 640.8116777
0.221
0.004
445.61214.6
0.296.10.66
census
10, 16..6
0.080=0.000
3, 42..8
0.005++0001
836.5++44.6
0.102++0.22
31

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
Table 3; Running time for dynamic KDE with the exact algorithm.
Dataset
Running Time
shuttle
4.1.0.11
aloi
164.5+13.6
msd
2, 715.6.00.0
covtype
glove
5, 25..
census
0.175
EXACT
EXACT CKNS
0.150
CKNS
DYNAMBRRS OuR ALGORTIIM
0.4
DYNAMICRS
Relative Error
0.125
0.100
Relative Eneer
0.3
OuR ALGORITHM
0.075
0.050
0.1
0.025
0.000
0.0
220
40
60
80
100
0
10
50
60
X10
(a) ALOI Relative Error
(b) SHUTTLE Relative Error
EXACT
EXACT
0.5
CKNS
10
CKNS
DYNAMICRS
DYNAMICRS
Relatvve Error
0.1
OuR ALGORITIM
8
ALGORITEM
0.3
Relative
6
0.2
4
0.1
2
0.0
0
1001
2010
300
400
500
600
100
200
300
400
500
x10'
x10
(c) COVTYPE Relative Error
(d) MSD Relative Error
0.20
ExACT
EXACT
CKNS
CKNS
DYNAMIORS
0.15
DYNAMICRS
Relative Error
OUR ALGORITHM
Relative Error
OUR ALGIORITHO
0.10
0.2
0.0
0.2
0.00
200
100
600
800
1000
1200
500
1000
1500
2000
2500
x10
x10
(c) GLOVE Relative Error
(f) CENSUS Relative Error
Figure Relative for all datasets.
32

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
EXACT
2.0
EXACT
12
CKNS
DYNAMICRS
DYNAMICRS
Update time (8)
10
OUR ALGORITHM
1.5
OUR ALGORITHM
Update
1.0
4-
0.5
2-
0
0.0
20
10
60
80
100
10
20
30
40
50
60
(a) ALOI Update Time
(b) SHUTTLE Update Time
30
EXACT
EXACT
25
CKNS
60
CKNS
DYNAMICRS
DYNAMICRS
Update sime (5)
20
OUR ALCORITHM
Update [5]
OUR ALGORITHM
15
30
10
100
200
300
400
500
600
100
200
300
100
500
x10
(c) COVTYPE Update Time
(d) MSD Update Time
EXAUT
EXACT
CKNS
150
CKNS
80
DYNAMICHS
DYNAMICRS
Updaate sime (5)
OUR ALGORITHM
125
OUR ALGORITIM
60
Update sime
100
40
50
20
2001
600
800
1000
1200
500
1000
1500
2000
2500
x10
x10
(e) GLOVE Update Time
(1) CENSUS Update Time
Figure 5: Running times data sets.
33

---

Dynamic Similarity Graph Construction with Kernel Density Estimation
D.2. Plots for Dynamic Similarity Graph Experiments
Table shows the results of the experiments for the dynamic similarity graph, evaluated with the Adjusted Rand In- dex (ARI) (Rand, 1971).
Table 6: ARI values for the dynamic similarity graph experiments.
FONLYCONNECTED
KNN
OUR ALGORITHM
datasct
Time
ARI
Time (8)
ARI
Time
ARI
blobs
72. 72.8
1.000=0 800
383.611.9
0.797:1.28
21.2+0.8
1.000=0.00 000
cifar10
19, 158. 24
0.000 coo
3, 503.0=4900
0.098:1..00 001
1, 1,400.5#1524
0.221
mnist
328. 159.5
0.149
5, 796.34234.3
0.673:10.00
1,470.3477.8
0.238++.001
34


Reviews:
[{"review_id": "ca8vyDBu59", "reviewer": "Reviewer_oi5L", "summary": "Suppose we are given a set $X = \\{x_1,\\dots,x_n\\}\\subseteq \\mathbb{R}^d$ of $n$ data points, a set $Q = \\{q_1,\\dots,q_m\\}\\subseteq\\mathbb{R}^d$ and a kernel $k : \\mathbb{R}^d\\times \\mathbb{R}^d\\to \\mathbb{R}$.\nWe would like to compute $\\mu_q := \\sum_{i=1}^n k(q,x_i)$ for all $q\\in Q$.\nHowever, computing these values has a linear running time by the brute force approach.\nHence, we want to construct a data structure such that approximating these values in sublinear time.\nMoreover, the data structure supports data point updates and query point updates.\nAs an application of this data structure, the authors showed that this data structure can be used to construct the similarity graph.\n\n## update after rebuttal\nI have read the authors' rebuttal and will keep my current score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review of our paper. The reviewer doesn’t leave specific questions for us to address. However, we’re happy to answer further questions raised by the reviewer during the later discussion phase.", "claims_and_evidence": "Yes. The proofs of the theorems are provided.", "methods_and_evaluation_criteria": "The authors provided for the experimental study.", "theoretical_claims": "I did not check all the details in the proofs.", "experimental_designs_or_analyses": "Yes. I read the figures and the experiment setup.", "relation_to_broader_scientific_literature": ".", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Estimating KDE is an important problem in machine learning.\nThe effort devoted for pushing this direction forward should be appreciated.", "other_comments_or_suggestions": ".", "questions_for_authors": ".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j8GSQQfHtF", "reviewer": "Reviewer_c5Mm", "summary": "This paper designs a dynamic similarity graph construction method with kernel density estimation. The proposed method constructs graphs more efficiently than existing methods and can also approximate the clustering results of spectral clustering. The authors provide a detailed theoretical analysis of the proposed algorithm. Comprehensive experiments demonstrate its effectiveness.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their suggestions and positive evaluation of our paper, and we respond to their comments below:\n\n>_**Question 1**: “The width parameter of the Gaussian kernel function has a significant impact on the learning algorithm. How is this parameter set in Table 3, and what is the basis for its selection?”_\n\n**Response**: For each dataset, we set $\\sigma$ of the Gaussian kernel such that the average kernel density $\\mu_{\\mathbf{q}}$ over all query points $\\mathbf{q} \\in Q$ is around $0.01$, as we describe on lines 433--436 of the paper submission. This follows the experimental setup of Karppa et al. (2022).\n\n>_**Weakness 1**: “The proof in the paper is relatively complex. It would be best to provide a general outline of the proof before presenting the detailed proof.”_\n\n**Response**: We appreciate the feedback from the reviewer. In the next version of the paper we will add proof outlines before the main proofs to improve the paper exposition.\n\n**References**\n- Matti Karppa, Martin Aumüller, and Rasmus Pagh. Deann: Speeding up kernel-density estimation using approximate nearest neighbor search. In 25th International Conference on Artificial Intelligence and Statistics (AISTATS’22), pp. 3108–3137, 2022.", "claims_and_evidence": "1. Theorem 3.1 proves that the proposed Algorithm 1 quantitatively analyzes the approximation bound for kernel density estimation and its running time.\n2. Theorem 4.1 provides the probability of the constructed approximate graph and its running time.\nThe paper provides rigorous proofs for the above two theorems.", "methods_and_evaluation_criteria": "The dynamic graph construction method proposed in the paper can assist in designing online clustering algorithms. The proposed method performs well on several benchmark datasets. The author also provides the algorithm's code, which facilitates further research.", "theoretical_claims": "I have verified parts of the proofs, and they are all correct.", "experimental_designs_or_analyses": "The width parameter of the Gaussian kernel function has a significant impact on the learning algorithm. How is this parameter set in Table 3, and what is the basis for its selection?", "relation_to_broader_scientific_literature": "The method proposed in the paper has broad connections with spectral clustering, online learning, and kernel density estimation.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1. The method proposed in the paper is highly innovative and can effectively improve the computational efficiency of spectral clustering algorithms.\n2. The paper provides a detailed proof for the proposed theorem.\n\nWeaknesses:\nThe proof in the paper is relatively complex. It would be best to provide a general outline of the proof before presenting the detailed proof.", "other_comments_or_suggestions": "No.", "questions_for_authors": "No.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ydz9RmRpjw", "reviewer": "Reviewer_J6i4", "summary": "In this paper, the authors deal with the kernel density estimation (KDE) problem. They propose a query hash data structure for dynamic graphs (it maintains the estimates for a set of query points as data points are added). They present experiments with different types and dimensionality of data, as well as some reference methods.\n\n## update after rebuttal\n\nI would like to thank the authors for providing answers to my concerns and questions, which reinforce me of the validity of the positive rating I gave initially. I hope the authors will make the promised changes to the new version of their manuscript.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback and overall positive evaluation of our paper. \n\n**Response to _Claims And Evidence and Experimental Design_**\n\nIt is known that kNN graphs achieve good empirical performance for spectral clustering. However, existing algorithms applicable for dynamic updates of kNN graphs lack rigorous theoretical guarantees. In contrast, our method provides such guarantees.\nOn the DynamicRS result, one of the key strengths of our algorithm is its theoretical approximation guarantee. Meanwhile, for DynamicRS, one can only obtain a guarantee when sufficiently many samples are drawn with respect to the smallest KDE value in the dataset, which is dataset-dependent. DynamicRS performs well in many cases but degrades significantly on the msd dataset, whereas our algorithm maintains stable performance.\nWe also appreciate the reviewer’s suggestion to run experiments on larger and more naturalistic datasets like mini-ImageNet. We highlight that our primary contributions are the theoretical guarantees and scalability, which are demonstrated in our current experiments. Nonetheless, we will include this analysis in future work.\n\n**Response to _References Not Discussed_**\n\nWe thank the reviewer for the suggestion on discussing related works in more detail. We didn’t discuss the related work in more detail due to the page limit and we will add more discussion in the next version of the paper.\nOn citing more recent work of sublinear-linear query time algorithms for the KDE problem, we will include a reference to Charikar et al. (2024), which gives an improved static KDE algorithm breaking the quadratic dependence on $\\varepsilon^{-1}$. Other than this, Charikar et al. (2020) remain the state-of-the-art for KDE.  \n\nWe will further include more references to incremental spectral clustering algorithms such as Sun et al. (2020), Kłopotek et al. (2024), and Yin et al. (2021). Compared to these, our work is the only one providing theoretical guarantees on the output clusters.\n\n**Response to Q1** \n\nThe main difference between our work and theirs is that we study the dynamic setting in which data and query points are added over time. \n\nMore specifically, while our initialisation and underlying static KDE methods share similarities with Charikar et al. (2020), our main novelty is the query hash data structure (Algo 4), enabling efficient updates of KDE estimates as data points arrive. With this, we show that the amortised update time for adding data points can be independent of $|Q|$, the number of maintained query points. To the best of our knowledge, this is the first such result. The novelty of the analysis lies in considering how often a query point $\\mathbf{q}$ gets updated throughout the sequence of data point insertions (see Lemma B.7), as the value of $\\mu_{\\mathbf{q}}$ changes over time. See Section B.2, pages 17–20. \n\nIn addition, building on Macgregor & Sun (2023), we introduce the following techniques to handle the dynamic setting:\n1. We carefully track all sampling paths for sampled edges in the tree.\n2. We modify the reweighting factor of sampled edges (Lines 300–309) so that if the degree/KDE estimate of a neighbour changes, only a bounded number of edge weights must be updated (Lemma C.3).\n3. We rigorously analyse the number of dynamically updated query points in hash buckets throughout our KDE sampling tree (Section 4.2).\n\nThese contributions are algorithmically novel and critical for dynamic KDE and similarity-graph construction. We will clarify this in the next version of the paper.\n\n**Response to Q2**\n\nThe observed peaks in execution time result from the periodic reinitialisation of our KDE data structures, triggered when the dataset doubles in size (Line 19, Algo 1). Notice that, while the reinitialisation step has time complexity $O(\\varepsilon^{-2} \\cdot n^{1+o(1)} \\cdot \\mathrm{cost}(k))$, it only occurs every $n$ updates, thus maintaining sublinear amortised time complexity.\n\n**Response to Q3**\n\nIn the next version, we will expand the following paragraph and form the conclusion section:\nThis paper develops dynamic algorithms for the dynamic KDE and similarity-graph constructions. Compared with most heuristic methods including the DynamicRS algorithm and dynamic kNN graphs, our designed algorithms have theoretically proven approximation guarantees. \n\nWe hope this addresses your questions, and we are happy to elaborate further in the discussion phase.\n\n**References**\n- Charikar, M., Kapralov, M., & Waingarten, E. 2024. A quasi-monte carlo data structure for smooth kernel evaluations. SODA\n- Sun, G., Cong, Y., Wang, Q., Li, J., & Fu, Y.  2020. Lifelong spectral clustering. AAAI\n- Kłopotek, M. A., Starosta, B., & Wierzchoń, S. T. 2024. Eigenvalue-based Incremental Spectral Clustering. Jour. of AI and Soft Computing Research\n- Zhou, P., Shen, Y. D., Du, L., Ye, F., & Li, X. 2021. Incremental multi-view spectral clustering with sparse and connected graph learning. Neural Networks", "claims_and_evidence": "The focus of the authors is amongst others on efficiency. They experimentally show that in the majority of cases their method obtains better times than the methods used in the comparisons. One thing is that their method does not usually yield the best result in terms of the accuracy, so the authors should comment on it.", "methods_and_evaluation_criteria": "Rather, yes, the authors use quite standard metrics for evaluation, while one of the methods with which they compare their solution is the one that they base their work on, so it is good.", "theoretical_claims": "The majority of theoretical analyses are taken/slightly modified from works of Charikar et al. (2020) or Macgregor & Sun (2023) - the authors cite these papers in almost all lemmas and definitions used to introduce their method.", "experimental_designs_or_analyses": "* The authors perform the experiments on different, heterogeneous datasets, the datasets have a different dimensionality, which is good (+). \n* In Tab. 2 for MNIST the authors mark their method as the best, because it has the lowest execution time. Nevertheless, kNN achieves much higher NMI (it needs more time, but provides much higher results) or for other cases in Tab. 1 DYNAMICRS lower error values. Could the authors comment on it?\n* It would be nice to include in the analysis some image embeddings for networks trained on larger and more naturalistic datasets (CIFAR10 has only a few classes and its images have a low resolution). E.g., there are many trained ImageNet models available, so even an experiment with smaller datasets, such as mini-ImageNet or so would be interesting.", "relation_to_broader_scientific_literature": "The authors should better relate their work to previous findings. E.g. they frequently cite the works like  Charikar et al. (2020) or Macgregor & Sun (2023) while introducing their work, and it is not clear for me after reading the paper what has been introduced in Charikar et al. (2020) or Macgregor & Sun (2023) and what is the novelty, it should be better highlighted.", "essential_references_not_discussed": "* The authors state in line 59: “there has been some recent progress to develop sub-linear query time algorithms (Charikar et al., 2020; Charikar & Siminelakis, 2017; 2019)” - it would be good to add some more recent papers here, as the newest one provided is from 5 years ago.\n* A lot of works on incremental spectral clustering can be found, while the authors provide mostly old references (Dhanjal et al., 2014; Martin et al., 2018; Ning et al., 2007), one exception is Laenen & Sun, 2024. The authors should again focus on more recent works and discuss what is their contribution. \n* A crucial thing is to differentiate the paper contributions from Charikar et al. (2020), as it is cited in almost all lemmas and definitions used to define the method.", "other_strengths_and_weaknesses": "Additional strengths:\n+ The figures created by the authors are very aesthetic.\n+ The formulation of the problem and the methods is clear. \n+ The Appendix and Supplementary Materials are helpful. \n\nAdditional weaknesses:\n- No clear Conclusions section with main highlights, because of that the paper seems unfinished.", "other_comments_or_suggestions": "In general, the authors should better highlight how their method improves the existing methods and better compare it to the existing literature.", "questions_for_authors": "**Q1** The authors cite Charikar et al. (2020) or Macgregor & Sun (2023)  in almost all parts of the method description. How does their work differ from them, what does it contribute?\n\n**Q2** Could the authors comment on the visible peaks in the execution times for their method?\n\n**Q3** Could the authors write down their main conclusions? What is better, what is worse when their method is used?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a dynamic data structure for kernel density estimation (KDE) and similarity graph construction that supports efficient updates to both data and query points. The method enables sublinear query time for approximate KDE and graph-based learning tasks, such as spectral clustering. Central to the work is a query hash data structure that allows fast updates and provable approximation guarantees. Theoretical contributions include bounds on update time and accuracy, while experiments on synthetic and real-world datasets demonstrate the method’s scalability and effectiveness in dynamic settings.

All reviewers recommend acceptance. They also made suggestions for improving the paper, which the authors should take into account when preparing the final version of the paper
Decision: Accept (poster)