Dynamic Similarity Graph Construction with Kernel Density Estimation

We thank the reviewer for their time and feedback, and we respond to points below. > **W1**: “Similar qualitative results for both the initialisation time and the update time were achieved by Liang et. al. (2024). It seems the techniques are reasonably similar too, looking to sample points in various distance levels around the queries. Although this paper cites the Liang et. al. paper and although it is true the latter paper does not handle dynamic updates of the query set, this paper fails to mention that the qualitative results of the Liang et. al. paper are similar to this paper, and it fails to compare the techniques between the papers.” **Response:** We appreciate the reviewer’s remark, and provide a detailed comparison between our approach and that of Liang et al. (2022) below. Both our work and that of Liang et al. (2022) are based on the static LSH-based KDE estimator of Charikar et al. (2020) (referred to as CKNS in the manuscript), who introduced the technique of sampling points at geometric weight levels $L_{j}^{\mathbf{q}}$. However, the key difference is that our algorithm supports dynamic updates of maintained query points as data points are added, while Liang et al. only consider updating the CKNS estimator. This difference, outlined briefly in Lines 226-230, is expanded here for clarity: 1. Liang et al. study the setting where a new data point $\mathbf{z}$ replaces an existing point $\mathbf{x}\_i \in X$. Under this dynamic setting, they show that the CKNS _estimator_ can be maintained. They achieve this by iterating through the maintained hash buckets $B_{H_{\mu\_i, a, j, \ell}} (\mathbf{x}\_i)$ and replacing every stored $\mathbf{x}\_i$ with $\mathbf{z}$. 2. On the other hand, we study the incremental setting where a new point $\mathbf{z}$ is added to $X$. To update the estimator, we take a similar approach, and iterate through the maintained hash buckets $B_{H_{\mu\_i, a, j, \ell}} (\mathbf{z})$ and add $\mathbf{z}$ accordingly (Lines 1-10 of Algorithm 6 in the appendix). Updating the estimator like this allows for fast estimation of KDE estimates on the updated data points. _However_, it is not clear how to efficiently update the estimates of a set of maintained query points, i.e., where the update time is independent of the number of added query points, as in our Theorem 3.1. 3. Therefore, in our work, we carefully design an additional _query hash_ (Algorithm 4) to decide when to update estimates of maintained points - illustrated in Figure 1. This additional data structure allows us to bound how often a query point is updated throughout the sequence of data point insertions, as the value of $\mu_\mathbf{q}$ changes throughout the sequence of updates (Lemma B.7). To address the reviewer's concern, we have added extra discussion at the end of page 5 (in blue) to better compare our approach to that of Liang et al. Importantly, although the actual update times of both results are qualitatively similar, our update time includes returning all the updated KDE estimates. Liang et al.’s update time only includes updating the buckets. This difference is crucial for the setting where $X=Q$, as is the case in our Theorem 4.1. Any new data point changes the true KDE value for all data/query points. However, our results show that for any data/query point insertion, only $\widetilde{O}(1)$ estimates have to be updated to maintain $(1\pm \varepsilon)$-approximations for every $\mathbf{q} \in Q$. This - combined with several other techniques - allows us to bound the number of sampling paths/edges that need to be resampled, leading to our efficient update times in Theorem 4.1. Our dynamic KDE experiments further illustrate this distinction. In the CKNS baseline, we first update the buckets with the new data points (as proposed in Liang et al.), and then recalculate the estimates for all query points after every data point update. On the other hand, our algorithm shows significant performance improvements by dynamically maintaining query estimates. As a final remark, we highlight that our work is the first to rigorously implement the static CKNS algorithm, and its adaptation to the dynamic setting.

> **W2**: “Though the claim is that the update time is sublinear, the cost function depends on the value of the smallest query. For many reasonable kernels such as the Gaussian kernel, these queries have very small value, in which case the resulting update time is not small. On the other hand, for queries with large value, sampling is a standard KDE technique. Given these points, it is not clear what are the technical novelties of this paper.” **Response**: Our results indeed rely on the smallest KDE value. As is standard in the literature, we assume a lower bound for the smallest KDE value. For ease of presentation, we assume for every $\mathbf{q}$ it holds that $1 \leq \mu_\mathbf{q} \leq n$, but the results hold under the general condition that $\mu_\mathbf{q}/n = n^{-\theta(1)}$, like the work of Charikar et al. (2020). It’s important to note that this is the most interesting regime for this problem, since for $\mu_\mathbf{q}/n = n^{-\omega(1)}$ under the Orthogonal Vectors Conjecture [1], the problem cannot be solved faster than $n^{1-o(1)}$ time using space $n^{1-o(1)}$ [2]. And indeed, as noted by the reviewer, for larger values $\mu_\mathbf{q}/n = n^{-o(1)}$ random sampling solves the problem in $n^{o(1)}/\varepsilon^{2}$ time and space (Charikar et al., 2020). **References** [1] _Rubinstein, Aviad. "Hardness of approximate nearest neighbor search." Proceedings of the 50th annual ACM SIGACT symposium on theory of computing. 2018._ [2] _Charikar, Moses, and Paris Siminelakis. "Multi-resolution hashing for fast pairwise summations." 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2019._

Thank you once more for your feedback and comments on our work. As the review period is ending, we wanted to check if you’ve had a chance to read our response to your last question. We are happy to respond to any further questions you might have.

We thank the reviewer for their time and feedback. > **W1**: “The paper seems technically somewhat incremental, in that there is not a lot of novelty needed in order to adapt existing work on the problem to the dynamic setting. The hashing-based estimators for KDE are naturally dynamically maintainable (just a point can simply be added or removed from its bucket in the hash table) and the paper basically builds this property into the Macgregor-Sun construction.” **Response:** We emphasise that although the LSH-based _estimator_ of CKNS can be extended to a dynamic setting as data points get added (see e.g. Liang et al., 2022), it is not clear that the _estimates_ of a set of query points can be efficiently updated, i.e., where the update time is independent of the number of added query points, as in our Theorem 3.1. To obtain the amortised running time guarantees in Theorem 3.1, we carefully design an additional query hash to decide when to update estimates of points. In the analysis, one has to consider how often a query point $\mathbf{q}$ gets updated throughout the sequence of data point insertions/deletions (See Lemma B.7), as the value of $\mu_{\mathbf{q}}$ changes throughout the sequence of updates. This part of the discussion corresponds to the proofs found in Section B.2 (Pages 18 to Page 22) An important case is where $X=Q$, as is the case in our Theorem 4.1. Any new data point changes the true KDE value for all data/query points. However, our results show that for any data/query point insertion, only $\widetilde{O}(1)$ estimates have to be updated to maintain $(1\pm \varepsilon)$-approximations for every $\mathbf{q} \in Q$. Using this, we prove that the number of paths (edges) that need to be resampled is $\widetilde{O}(1)$ (Lemma 4.6). This requires careful analysis of the difference in the KDE estimate of $\mathbf{x}$ at the root and internal nodes of the sampling tree in order to bound the number of collisions (Lemmas 4.4, and 4.5) in the relevant buckets. This part of discussion corresponds to the proofs in Section C.2 from Page 25 to Page 30. Additionally, several novel analyses are needed on top of the static algorithm of Macgregor and Sun (2023) to ensure the sublinear update time of our approximate similarity graph: (i) we have to carefully track all the sampling paths corresponding to sampled edges in the tree; (ii) the reweighting factor of the sampled edges has to be changed (see Lines 350 - 355 for the discussion), in order to bound the number of edges whose weight needs to be updated if the degree/kde estimate of a neighbour changes (Lemma C.3). Taking all of this into account, we believe that our designed algorithms and their analyses form a significant contribution.

We appreciate the reviewer for taking the time to consider our response. There is one more point we would like to address in the original review, which states that our results hold "under insertion and deletion of points." We clarify that our KDE results are only stated for the incremental case of inserting data points. Our update times are impossible to obtain in the fully dynamic case. For instance, if all query points are the same, and their KDE is dominated by a single nearby data point, repeatedly inserting and deleting this point forces updates for all query estimates at every update. This results in an amortised update time of $|Q| \cdot \varepsilon^{-2} \cdot n^{o(1)} \cdot \mathrm{cost}(k)$ - equivalent to re-estimating all query points at every data point update. Our update time on the other hand is $\varepsilon^{-2} \cdot n^{o(1)} \cdot \mathrm{cost}(k)$.

We thank the reviewer for their time and feedback, and we respond to their points/question below. > **W1**: “The experimental design is a good starting point, but it makes it impossible to answer the following important question: for a given data set and a given error bound, which algorithm is the fastest? For example, for the GLOVE data set, the proposed algorithm is twice as fast as DYNAMICRS, but it also has a much higher error, so it is plausible that DYNAMICRS with a smaller sampling rate would be faster and have smaller error. Overall, the experimental section demonstrates that the proposed algorithm is implementable, but it is unclear whether it improves empirically over the state of the art. ” **Response:** In practice, the objective is to approximate the KDE efficiently without computing the true KDE values, as this is computationally expensive. A key strength of our algorithm is that it has a provable approximation guarantee. On the other hand, for the DynamicRS baseline, there is only a guarantee if sufficiently many samples are drawn with respect to the smallest KDE value in the dataset. Determining this fraction in practice is not clear and dataset-dependent. For instance, while DynamicRS performs very well in many cases, it suffers significant degradation on the msd dataset. In contrast, our algorithm has stable performance across all tested datasets. > **S2/W2/Q1**: “Converting static algorithms into dynamic data structures does not seem to require significantly new ideas, but it is not trivial either.” & “What are the main new algorithmic ideas needed to dynamize the static algorithms of Charikar et al and Macgregor-Sun ?” **Response:** We list the new algorithmic ideas below. The key algorithmic idea in our Dynamic KDE result is the introduction of an additional _query hash_ (Algorithm 4) to decide when to update estimates of maintained points - illustrated in Figure 1. We emphasise that although the LSH-based _estimator_ of CKNS can be extended to a dynamic setting as data points get added (see e.g. Liang et al., 2022), it is not as clear that the _estimates_ of a set of query points can be efficiently updated, i.e., where the update time is independent of the number of added query points, as in our Theorem 3.1. To obtain the amortised running time guarantees in Theorem 3.1, we therefore carefully design the additional query hash to decide when to update estimates of points. In the analysis, one then has to consider how often a query point $\mathbf{q}$ gets updated throughout the sequence of data point insertions/deletions (See Lemma B.7), as the value of $\mu_{\mathbf{q}}$ changes throughout the sequence of updates. This part of the discussion corresponds to the proofs found in Section B.2 (Pages 18 to Page 22) An important case is where $X=Q$, as is the case in our Theorem 4.1. Any new data point changes the true KDE value for all data/query points. However, our results show that for any data/query point insertion, only $\widetilde{O}(1)$ estimates have to be updated to maintain $(1\pm \varepsilon)$-approximations for every $\mathbf{q} \in Q$. Using this, we prove that the number of paths (edges) that need to be resampled is $\widetilde{O}(1)$ (Lemma 4.6). This requires a careful analysis of the difference in the KDE estimate of $\mathbf{x}$ at the root and internal nodes of the sampling tree in order to bound the number of collisions (Lemmas 4.4, and 4.5) in the relevant buckets. This part of discussion corresponds to the proofs in Section C.2 from Page 25 to Page 30. Additionally, several novel analysis are needed on top of the static algorithm of Macgregor and Sun (2023) to ensure the sublinear update time of our approximate similarity graph: (i) we have to carefully track all the sampling paths corresponding to sampled edges in the tree; (ii) the reweighting factor of the sampled edges has to be changed (see Lines 350 - 355 for the discussion), in order to bound the number of edges whose weight needs to be updated if the degree/kde estimate of a neighbour changes (Lemma C.3). Taking all of this into account, we believe that our designed algorithms and their analyses form a significant contribution.

We thank the reviewer for their time and positive evaluation of our paper. We respond to the questions below. > **Q1**: “The paper cites the work of Macgregor and Sun 2023 for dynamic similarity matrices (and the algorithm is based on that work), but I didn't notice experimental comparison to that work. I may have missed it, but if the authors can provide a clear comparison (both experimentally and theoretically), it would make the paper stronger.” **Response:** The work of Macgregor and Sun (2023) is a static algorithm for approximate similarity graph construction. Our result generalises their algorithm to the dynamic setting. Regarding the theoretical comparison, we achieve the same guarantees on the returned approximate similarity graph as their work. One notable difference is that their algorithm can use any KDE estimator as a black box, whereas our algorithm requires our dynamic KDE algorithm. Regarding an experimental comparison, directly comparing our dynamic method to their static approach would involve re-running their algorithm after each data point update, which is computationally intensive. Given that the theoretical guarantees for the both approaches are the same, we expect that both algorithms would yield similarity graphs with similar performance in terms of NMI and ARI. Our focus is to demonstrate the efficiency gains in the dynamic context. However, if the reviewer believes that including this experiment would improve the paper, we are willing to conduct this experiment and include the findings. > **Q2**: “About the n^{1/4} time required for the KDE step for Gaussian kernels (which is what leads to the final update time), are there any lower bounds suggesting that the time cannot be improved?” **Response:** This is an interesting question, and to the best of our knowledge there is no known running time lower bound for KDE estimation for the Gaussian kernel, in both the static and dynamic setting. In their paper, Charikar et al (2020) do provide a KDE estimator which uses data dependent LSH, and they achieve a KDE query time of $n^{0.173}$ for the Gaussian kernel in the static setting; generalising this result to the dynamic setting would be an interesting direction for future work.