# Dynamic Kernel Graph Sparsifiers

arXiv: https://arxiv.org/abs/2211.14825 · HTML: https://mlsanity.com/paper/2211.14825/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2022.

## Built on by (most cited first, 4 of 4)

- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Faster Robust Tensor Power Method for Arbitrary Order](https://mlsanity.com/paper/2306.00406/) (2023)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)

## Abstract (arXiv)

A geometric graph associated with a set of points P= x1, x2, cdots, xn  subset ℝd and a fixed kernel function mathsfK:ℝd× ℝd→ℝ≥ 0 is a complete graph on P such that the weight of edge (xi, xj) is mathsfK(xi, xj). We present a fully-dynamic data structure that maintains a spectral sparsifier of a geometric graph under updates that change the locations of points in P one at a time. The update time of our data structure is no(1) with high probability, and the initialization time is n1+o(1). Under certain assumption, our data structure can be made robust against adaptive adversaries, which makes our sparsifier applicable in iterative optimization algorithms. We further show that the Laplacian matrices corresponding to geometric graphs admit a randomized sketch for maintaining matrix-vector multiplication and projection in no(1) time, under sparse updates to the query vectors, or under modification of points in P.