Pith. sign in

REVIEW 4 major objections 4 minor 51 references

Dynamic Similarity Graph Construction with Kernel Density Estimation

T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that kernel density estimates can be maintained under data insertions with amortised update time ε^-2 · n^o(1) · cost(k), and that this yields the first dynamic approximate similarity graph with sublinear update time.

desk verdict Real dynamic KDE and similarity-graph results with a solid main proof, a Chernoff gap in Lemma B.7, and a stress-test objection that does not hold up. read the letter →

arxiv 2507.01696 v1 pith:R2JEYIFY submitted 2025-07-02 cs.DS cs.LG

Steinar Laenen , Peter Macgregor , He Sun This is my paper
classification cs.DScs.LG MSC 68W2068W2568P05
keywords kerneldensityestimationdynamicdatastructuressimilaritygraphspectralclusteringlocality-sensitivehashingsublinearupdatetimeGaussianJLlemma
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that the static KDE framework of Charikar et al. can be made fully dynamic under data point insertions, while preserving (1 ± ε)-approximate estimates for every maintained query point. The key gain is that updating one new data point costs only $ε^{-2}$ · n^o(1) · cost(k), which is independent of the number of query points, instead of recomputing all estimates. For the Gaussian kernel this is n^(1/4+o(1)) per insertion, and the paper further argues this powers a dynamic sparse similarity graph with expected amortised update time n^o(1) · cost(k), preserving cluster structure for downstream spectral clustering. If correct, these are the first dynamic KDE and first dynamic sparse similarity graph constructions under insertions with such sublinear guarantees.

What carries the argument

The load-bearing objects are the geometric weight levels L_j^q, which partition data points by their kernel distance to a query, and a carefully maintained query hash: buckets B*_{H_{μ_i,a,j,ℓ}}(q) that store query points under the same LSH functions used for data buckets. This pairing lets ADDDATAPOINT(z) find exactly the query points whose estimates should incorporate z without scanning all queries. For the graph result, the central mechanism is a complete binary tree T where each internal node stores a dynamic KDE structure and each sampled neighbour of a vertex corresponds to a stored sampling path P_{x,ℓ}; updates resample only the paths whose estimated densities changed, with the number of resampled paths shown to be eO(1) in expectation.

What would settle it

Take a dataset with dimension d much larger than log n, insert points one at a time, and measure the wall-clock per-insertion cost and the maximum relative KDE error at every query point; if the per-insertion cost grows with d or the (1 ± ε) error guarantee degrades, then Assumption 2.1 is violated and Theorem 3.1's stated bound does not hold as written.

Watch

Extended reading notes

Core claim

The central claim is that the CKNS hash-based KDE estimator can be extended to the streaming-insertion setting by maintaining a parallel structure of query-hash buckets. When a new data point z arrives, the procedure samples z into the existing data buckets exactly as a full re-initialisation would, then recovers precisely those query points whose estimates would have changed, updating their KDE values in place. This gives amortised update time $ε^{-2}$ · n^o(1) · cost(k), and the same machinery supports inserting and deleting query points. The paper then builds a complete binary tree whose internal nodes hold such dynamic KDE structures, samples L neighbours per vertex through the tree, and stores the sampling paths so that after inserting z it can resample only the affected paths; this maintains an approximate similarity graph (a cluster-preserving sparsifier) with expected amortised update time n^o(1) · cost(k), which is n^(1/4+o(1)) for the Gaussian kernel.

Load-bearing premise

The runtime bounds assume that every data set can be treated as living in d = O(log n) dimensions via a JL projection that preserves the kernel values and cluster structure, and if that projection fails for real high-dimensional data the claimed n^(1/4+o(1)) update time does not follow.

Editorial extensions

If this is right

  • For the Gaussian kernel, each new data point can be incorporated in n^(1/4+o(1)) amortised time while keeping (1 ± ε) KDE estimates for every query point, independent of how many query points are maintained.
  • The dynamic KDE data structure supports insertion and deletion of query points, with each new query point estimated at ε^-2 · n^o(1) · cost(k) cost.
  • An approximate similarity graph with eO(n) edges can be maintained under insertions, and as long as the data set has a clear cluster structure the maintained graph preserves the conductance-cluster structure of the fully connected graph.
  • Spectral clustering can therefore be run dynamically: the paper reports competitive normalised mutual information on real datasets while updating the graph much faster than recomputing the fully connected or k-nearest-neighbour graphs.
  • The amortisation rests on rebuilding the whole structure only when the data size doubles, so the per-step cost stays sublinear across a long insertion sequence.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper's theory assumes d = O(log n) via the JL lemma, but its own experiments run at d = 728, 2048 and 100; extending the analysis to genuinely high-dimensional data without projection is an open gap implicit in the paper.
  • The update machinery handles data insertions and query insertions/deletions but not deletion of data points; a streaming setting with arbitrary deletions would require additional rebuilding arguments beyond the ones given.
  • Because the cost(k) term varies by kernel, the same dynamic structure would give an n^o(1) update time for the t-student kernel and n^(4/27+o(1)) for the exponential kernel, which the paper states but does not test experimentally.
  • The maintained KDE tree effectively offers a dynamic sampling-by-kernel-weight primitive, so it could be reused as a building block for dynamic versions of other similarity-graph and kernel-matrix algorithms, an extension the paper only gestures toward in its conclusion.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper introduces dynamic data structures for kernel density estimation (KDE) and approximate similarity graph construction under data-point insertions. The KDE structure maintains (1±ε)-approximate estimates for a set of query points, with an amortised update time of ε^{-2} n^{o(1)} cost(k) (Theorem 3.1), improving over full recomputation and being independent of the number of queries. The graph structure maintains a cluster-preserving sparse approximation of the fully connected similarity graph, with expected amortised update time n^{o(1)} cost(k) (Theorem 4.1), which for the Gaussian kernel is n^{1/4+o(1)}. The algorithms build on CKNS (Charikar et al., 2020) and Macgregor & Sun (2023), adding query-hash data structures and path-tracking to enable dynamic updates. The paper also reports experiments on several datasets. The proofs are detailed, but several load-bearing steps have gaps, most notably the derivation of the expected number of colliding query points in Lemma C.2 and the concentration argument in Lemma B.7.

Significance. If the main theorems are correct, the results are significant: a dynamic KDE algorithm whose update time does not grow with the number of queries, and a dynamic approximate similarity graph with sublinear expected update time, are new contributions. The paper provides an LSH-based framework with explicit algorithmic procedures, and the empirical section demonstrates scalability on some datasets. The strengths include the clear problem formulation, the use of established static machinery (CKNS and Macgregor & Sun with appropriate reweighting), and the availability of open-source code. However, the significance is contingent on repairing the technical gaps in the time-complexity proofs; as written, the theoretical guarantees are not fully established.

major comments (4)
  1. [Section C.2] The proof of Lemma C.2 applies Lemma B.1 with the roles of data points and query points swapped. Lemma B.1 bounds, for a fixed query q, the expected number of data points x with H(q)=H(x), using the geometric level bound |L_q^{j'}| ≤ 2^{j'} μ_q. It does not supply a bound on the expected number of query points q with H(z)=H(q) for a fixed z. The subsequent steps (C.3)–(C.5) depend on this swapped bound, so the inequality E[|{q ∈ T'.kde.Q_{μ_i} : H(z)=H(q)}|] = eO(μ_i 2^{j+1}) is not established by the cited lemma. The authors need to give a direct proof, for example by partitioning the queries into weight levels relative to z and using Lemma 2.4 with the kernel-cost definition, or otherwise demonstrating that the restriction q ∈ Q_{μ_i} controls the count. The stress-test counterexample in the anonymous report appears inconsistent with Lemma 2.4 (the stated combination n=2^{2j} and μ_q≈1 with all points at level j violates |L_q^j| ≤ 2^j μ_q), but the proof gap is real and load-bearing for Lemma C.3 and Theorem 4.1.
  2. [Section B.2] The proof of Lemma B.7 applies the Chernoff bound to the sum of indicators Y^q_{a,t} across t, but the events E^q_{a,t} are not independent over time: the same hash functions are reused across insertions, and the evolving data structure is deterministic given the randomness. No martingale or negative-dependence argument is provided. A Markov bound would only give a constant-probability guarantee, whereas the derivation in Section B.3 (proof of Theorem 3.1) requires the high-probability statement U_q^T = eO(1) to obtain the claimed amortised bound with high probability. The authors should either supply a valid concentration argument or restate the amortised time guarantee as an expectation bound.
  3. [Section 2.4] Assumption 2.1 sets d = O(log |X_t|) based on the JL lemma, but the JL lemma preserves distances only up to (1±ε), which does not generally preserve Gaussian (or other smooth) kernel values multiplicatively for far-apart pairs; a small relative distance change induces a large relative error in the kernel value. Consequently the theorems as stated are silent for the high-dimensional datasets used in the experiments (cifar10 d=2048, mnist d=728, glove d=100). The paper should clarify whether the analysis is intended for data that are already low-dimensional, or whether an additional kernel-preserving dimension reduction is assumed; otherwise the practical claims in the experimental section are not supported by the theoretical results.
  4. [Section C.1] The correctness proof of CONSTRUCT GRAPH is not given explicitly; the text states that the analysis of Macgregor & Sun (2023) can be followed after replacing b̂p(i,j) with b̂w(i,j), since the two are within a constant factor. This is a nontrivial substitution: the constant-factor bound alone does not automatically preserve the required cluster-conductance and eigenvalue-gap conditions in Definition A.3, because those conditions depend on the exact sampling probabilities and edge weights. The authors should either provide the details of the carrying-over argument or state precisely which lemmas of the static paper apply unchanged and what verification is needed for the modified reweighting.
minor comments (4)
  1. [Algorithm 1] Line 23 of Algorithm 1 calls DELETE FROMDATA(z) but the parameter is the query point q; the name should be consistent (e.g., DELETE QUERY POINT(q)), since 'z' elsewhere denotes a data point.
  2. [Lemma C.1] The second sentence of the proof says 'the data points XL ≜ T ′′.left.data and XR ≜ T ′′.left.data'; the second of these should be T ′′.right.data.
  3. [Section 3] The statement lists 'with high probability' for the amortised update time, but the proof in Section B.3 derives the bound through an amortised accounting that itself relies on the high-probability statement of Lemma B.7; the dependency between these probabilistic guarantees should be made explicit.
  4. [Section 5.1] The reported relative errors for the proposed algorithm on some datasets are noticeably worse than the DYNAMIC RS baseline (e.g., census 0.102 vs 0.005, covtype 0.196 vs 0.018); the text's statement that the algorithm 'maintains low relative errors' is accurate only when compared with CKNS, so the description should be more balanced.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: dynamic KDE and graph update bounds follow from cited static subroutines without predicting fitted inputs.

full rationale

The paper's derivations are self-contained with respect to the inputs of the claims. Theorem 3.1 is established by composing the static CKNS preprocessing (Charikar et al. 2020) with the paper's own query-hash bookkeeping: Lemma B.5 shows that ADDDATAPOINT reproduces the buckets of INITIALISE(X∪z,Q,ε), and Lemma B.7 bounds per-query updates via the sampling probabilities and geometric weight levels, with no fitted parameter renamed as a prediction. Theorem 4.1 likewise builds on the static approximate-similarity-graph theorem of Macgregor & Sun (2023), which is an independently published result with stated assumptions and not an unverified self-citation; the dynamic part supplies path bookkeeping and a bound on expected resampled paths. The only passages that could be raised are Assumption 2.1 (dimension reduction by JL, a scope limitation, not a circular input) and the appendix proof of Lemma C.2, where applying Lemma B.1 with data/query roles swapped is a mathematical step that the skeptic's sphere construction challenges. A false or unjustified lemma would be a correctness defect, not circularity: it does not make the claimed update time equal to an input of the paper by definition. No step in the paper defines a quantity in terms of the target result, fits a parameter to data and then calls the fit a prediction, or imports a uniqueness theorem from the authors' prior work to force a choice. Score 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data in the theoretical claims, and no new entities are postulated. The results import standard LSH and spectral graph facts plus two external static results: Charikar et al. (2020) for KDE and Macgregor and Sun (2023) for similarity graph approximation. The experimental bandwidth sigma is set per dataset so average density is around 0.01, but it does not enter the theorem statements.

assumptions (5)
  • standard math Andoni-Indyk LSH family satisfies Lemma 2.1 with rho = 1/c^2 + o(1) when t = log^{2/3} n and c = O(log^{1/7} n).
    Invoked in Lemmas B.1 and C.2 to bound hash collisions inside buckets; the update time bounds in Theorems 3.1 and 4.1 depend on it. The lemma is taken from the cited prior literature and is not re-proved.
  • domain assumption The data set can be assumed to satisfy d = O(log |Xt|) via the JL lemma, so runtime dependencies on d are ignored.
    Assumption 2.1 in Section 2.4. It is load-bearing for the n^(1/4+o(1)) update time claims, and the high-dimensional datasets in Section 5 lie outside this regime.
  • standard math The static CKNS KDE data structure satisfies Lemmas 2.4, 2.5, B.2, and B.4 as stated.
    The dynamic KDE algorithm reuses the CKNS preprocessing and inherits its sampling and query-time guarantees, so correctness of the dynamic structure assumes correctness of the static one.
  • domain assumption The static approximate similarity graph construction of Macgregor and Sun (2023) is correct, and its proof can be followed after replacing the scaling factor bp(i,j) with bw(i,j).
    Used in Section C.1 to establish the initialisation statement of Theorem 4.1. The paper says the remaining analysis is very similar to that paper and does not reproduce the proof.
  • standard math Higher-order Cheeger inequalities and cluster-preserving sparsifier properties hold for the graphs considered.
    Lemma A.1 and Definition A.2 justify why preserving eigenvalue gaps of the normalised Laplacian transfers clustering structure from the dense graph to the sparse graph.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dynamic Similarity Graph Construction with Kernel Density Estimation." pith.science (2026). https://pith.science/paper/R2JEYIFY

@misc{pith2026250701696,
  author       = {Pith},
  title        = {Pith review of: Dynamic Similarity Graph Construction with Kernel Density Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R2JEYIFY}},
  note         = {Machine review of arXiv:2507.01696}
}
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.

Figures

Figures reproduced from arXiv: 2507.01696 by the authors.

Figure 1
Figure 1. Illustration of ADDDATAPOINT(z) for a single iteration µi ∈ M, a ∈ K1, j ∈ [Jµi ], and ℓ ∈ [K2]. The first row illustrates (a) the subsampled data points Z ≜ {x3, x4, x6} and query points Qµi ≜ {qi} 4 i=1, (b) the bucketing of Z by the hash function Hµi,a,j,ℓ, as well as (c) the bucketing of Q by the same hash function. The second row illustrates (a) the relative location of a new arriving data point z ∈ R d , with … view at source ↗
Figure 2
Figure 2. Illustration of updating T after performing UPDATEGRAPH(z). In (a), Px1,ℓ and Px1,ℓ′ are generated by SAMPLE({x1}, T , ℓ) and SAMPLE({x1}, T , ℓ′ ), and correspond to edges (x1, x9) and (x1, x3). (b) illustrates that, after adding z, part of Px1,ℓ′ is updated due to RESAMPLE(T ′ , Px1,ℓ′ ), and (x1, x3) is replaced by (x1, x6); however, the update on z doesn’t change Px1,ℓ. Bounding the expected number of re-sampled… view at source ↗
Figure 3
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. FULLYCONNECTED: the fully-connected similarity graph with the Gaussian kernel; 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 c… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Relative errors for all datasets. 32 [PITH_FULL_IMAGE:figures/full_fig_p032_4.png]
Figure 5
Figure 5. Figure 5: Running times for all data sets. 33 [PITH_FULL_IMAGE:figures/full_fig_p033_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

51 extracted references · 46 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should not add it explicitly Type <Return> for now, but then later remove the command n...

  3. [3]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@first@sw \@firstoftwo \@ifundefined NAT@b*@#2 \@firstoftwo @num @NAT@ctr \@secondoft...

  4. [4]

    Hoory and Linial and Wigderson

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibsetup #1 @NAT@ctr @ @openbib .11em \@plus.33em \@minus.07em 4000 4000 `\.\@m @bibit...

    work page arXiv 1990

  5. [5]

    and Indyk, P

    Andoni, A. and Indyk, P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Communications of the ACM, 51 0 (1): 0 117--122, 2008

    2008

  6. [6]

    Efficient density evaluation for smooth kernels

    Backurs, A., Charikar, M., Indyk, P., and Siminelakis, P. Efficient density evaluation for smooth kernels. In 59th 18 , pp.\ 615--626, 2018

    work page 2018

  7. [7]

    Subquadratic algorithms for kernel matrices via kernel density estimation

    Bakshi, A., Indyk, P., Kacham, P., Silwal, S., and Zhou, S. Subquadratic algorithms for kernel matrices via kernel density estimation. In 11th International Conference on Learning Representations (ICLR'23), 2023

    work page 2023

  8. [8]

    P., Whitman, B., and Lamere, P

    Bertin-Mahieux, T., Ellis, D. P., Whitman, B., and Lamere, P. The million song dataset. In 12th International Conference on Music Information Retrieval ( ISMIR '11) , 2011

    work page 2011

Show all 51 references
  1. [9]

    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 0 (3): 0 131--151, 1999

    1999

  2. [10]

    and Siminelakis, P

    Charikar, M. and Siminelakis, P. Hashing-based-estimators for kernel density in high dimensions. In 58th 17 , pp.\ 1032--1043, 2017

    2017

  3. [11]

    and Siminelakis, P

    Charikar, M. and Siminelakis, P. Multi-resolution hashing for fast pairwise summations. In 60th 19 , pp.\ 769--792, 2019

    2019

  4. [12]

    Kernel density estimation through density constrained near neighbor search

    Charikar, M., Kapralov, M., Nouri, N., and Siminelakis, P. Kernel density estimation through density constrained near neighbor search. In 61st 20 , pp.\ 172--183, 2020

    2020

  5. [13]

    A quasi-monte carlo data structure for smooth kernel evaluations

    Charikar, M., Kapralov, M., and Waingarten, E. A quasi-monte carlo data structure for smooth kernel evaluations. In 35th 24 , pp.\ 5118--5144, 2024

    2024

  6. [14]

    Chung, F. R. Spectral Graph Theory. 1997

    1997

  7. [15]

    Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. S. Locality-sensitive hashing scheme based on p -stable distributions. In 20th Annual symposium on Computational Geometry (SoCG'04), pp.\ 253--262, 2004

    2004

  8. [16]

    Dynamic kernel sparsifiers

    Deng, Y., Jin, W., Song, Z., Sun, X., and Weinstein, O. Dynamic kernel sparsifiers. arXiv:2211.14825, 2022

    2022

  9. [17]

    Efficient eigen-updating for spectral graph clustering

    Dhanjal, C., Gaudel, R., and Clémençon, S. Efficient eigen-updating for spectral graph clustering. Neurocomputing, 131: 0 440--452, 2014

    2014

  10. [18]

    R., Perone-Pacifico, M., Verdinelli, I., and Wasserman, L

    Genovese, C. R., Perone-Pacifico, M., Verdinelli, I., and Wasserman, L. Nonparametric ridge estimation . The Annals of Statistics, 42 0 (4): 0 1511 -- 1545, 2014

    2014

  11. [19]

    J., and Smeulders, A

    Geusebroek, J.-M., Burghouts, G. J., and Smeulders, A. W. The A msterdam library of object images. International Journal of Computer Vision, 61: 0 103--112, 2005

    2005

  12. [20]

    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

    2003

  13. [21]

    and Strain, J

    Greengard, L. and Strain, J. The F ast G auss T ransform. SIAM J ournal on S cientific & S tatistical C omputing , 12 0 (1): 0 79–94, 1991

    1991

  14. [22]

    Deep residual learning for image recognition

    He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR'16), pp.\ 770--778, 2016

    2016

  15. [23]

    A dynamic low-rank fast G aussian transform

    Huang, B., Song, Z., Weinstein, O., Yin, J., Zhang, H., and Zhang, R. A dynamic low-rank fast G aussian transform. arXiv:2202.12329, 2024

    2024 arXiv

  16. [24]

    Johnson, W. B. Extensions of L ipschitz mappings into a H ilbert space. Contemporary Mathematics, 26: 0 189--206, 1984

    1984

  17. [25]

    Deann: Speeding up kernel-density estimation using approximate nearest neighbor search

    Karppa, M., Aum \"u 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'22), pp.\ 3108--3137, 2022

    2022

  18. [26]

    A., Starosta, B., and Wierzcho \'n , S

    K opotek, M. A., Starosta, B., and Wierzcho \'n , S. T. Eigenvalue-based incremental spectral clustering. Journal of Artificial Intelligence and Soft Computing Research, 14 0 (2): 0 157--169, 2024

    2024

  19. [27]

    Learning multiple layers of features from tiny images

    Krizhevsky, A. Learning multiple layers of features from tiny images. Master's thesis, University of Toronto, 2009

    2009

  20. [28]

    and Sun, H

    Laenen, S. and Sun, H. Dynamic spectral clustering with provable approximation guarantee. In 41st 24 , 2024

    2024

  21. [29]

    Detecting the overlapping and hierarchical community structure in complex networks

    Lancichinetti, A., Fortunato, S., and Kert \'e sz, J. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11 0 (3): 0 033015, 2009

    2009

  22. [30]

    Gradient-based learning applied to document recognition

    Lecun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86 0 (11): 0 2278--2324, 1998

    1998

  23. [31]

    R., Oveis Gharan, S., and Trevisan, L

    Lee, J. R., Oveis Gharan, S., and Trevisan, L. Multiway spectral partitioning and higher-order C heeger inequalities. Journal of the ACM, 61 0 (6): 0 1--30, 2014

    2014

  24. [32]

    Dynamic maintenance of kernel density estimation data structure: From practice to theory

    Liang, J., Song, Z., Xu, Z., and Zhuo, D. Dynamic maintenance of kernel density estimation data structure: From practice to theory. arXiv:2208.03915, 2022

    2022 arXiv

  25. [33]

    and Sun, H

    Macgregor, P. and Sun, H. Fast approximation of similarity graphs with kernel density estimation. In 37 23 , 2023

    2023

  26. [34]

    Fast approximate spectral clustering for dynamic networks

    Martin, L., Loukas, A., and Vandergheynst, P. Fast approximate spectral clustering for dynamic networks. In 35th 18 , pp.\ 3420--3429, 2018

    2018

  27. [35]

    US Census Data (1990)

    Meek, C., Thiesson, B., and Heckerman, D. US Census Data (1990) . UCI Machine Learning Repository, 1990

    1990

  28. [36]

    Statlog (Shuttle)

    NASA. Statlog (Shuttle) . UCI Machine Learning Repository, 2002

    2002

  29. [37]

    Y., Jordan, M

    Ng, A. Y., Jordan, M. I., and Weiss, Y. On spectral clustering: Analysis and an algorithm. In 15 01 , pp.\ 849--856, 2001

    2001

  30. [38]

    Incremental spectral clustering with application to monitoring of evolving blog communities

    Ning, H., Xu, W., Chi, Y., Gong, Y., and Huang, T. Incremental spectral clustering with application to monitoring of evolving blog communities. In the 2007 SIAM I nternational C onference on D ata Mining (SDM'07) , pp.\ 261--272, 2007

    2007

  31. [39]

    Scikit-learn: Machine learning in P ython

    Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in P ython. Journal of ...

    2011

  32. [40]

    Partitioning Well - Clustered Graphs : Spectral Clustering Works ! SIAM Journal on Computing, 46 0 (2): 0 710--743, 2017

    Peng, R., Sun, H., and Zanetti, L. Partitioning Well - Clustered Graphs : Spectral Clustering Works ! SIAM Journal on Computing, 46 0 (2): 0 710--743, 2017

    2017

  33. [41]

    Pennington, J., Socher, R., and Manning, C. D. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp.\ 1532--1543, 2014

    2014

  34. [42]

    Phillips, J. M. and Tai, W. M. Near-optimal coresets of kernel density estimates. Discrete & Computational Geometry, 63: 0 867--887, 2020

    2020

  35. [43]

    Spectral sparsification of metrics and kernels

    Quanrud, K. Spectral sparsification of metrics and kernels. In 32nd 21 , pp.\ 1445--1464, 2021

    2021

  36. [44]

    Rand, W. M. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66 0 (336): 0 846--850, 1971

    1971

  37. [45]

    and Smola, A

    Scholkopf, B. and Smola, A. J. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT Press, 2018

    2018

  38. [46]

    Generalized outlier detection with flexible kernel density estimates

    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

    2014

  39. [47]

    Lifelong spectral clustering

    Sun, G., Cong, Y., Wang, Q., Li, J., and Fu, Y. Lifelong spectral clustering. In 34th 20 , volume 34, pp.\ 5867--5874, 2020

    2020

  40. [48]

    and Zanetti, L

    Sun, H. and Zanetti, L. Distributed graph clustering and sparsification. ACM Transactions on Parallel Computing , 6 0 (3): 0 17:1--17:23, 2019

    2019

  41. [49]

    A tutorial on spectral clustering

    von Luxburg, U. A tutorial on spectral clustering. Statistics and Computing volume, 17 0 (4): 0 395--416, 2007

    2007

  42. [50]

    A., and Davis, L

    Yang, C., Duraiswami, R., Gumerov, N. A., and Davis, L. Improved fast G auss transform and efficient kernel density estimation. In 9th International Conference on Computer Vision (ICCV'03), pp.\ 664--671, 2003

    2003

  43. [51]

    Incremental multi-view spectral clustering

    Zhou, P., Shen, Y.-D., Du, L., Ye, F., and Li, X. Incremental multi-view spectral clustering. Knowledge-Based Systems, 174: 0 73--86, 2019

    2019

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.