Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
This addresses a fundamental problem in graph analysis for researchers and practitioners, offering significant speedups in spectral density estimation, though it is incremental in building upon existing sparsification techniques.
The paper tackles the problem of estimating the spectral density of a graph's adjacency matrix, providing a randomized algorithm that achieves ε accuracy in the Wasserstein-1 metric with O(nε^{-3}) time, improving on prior state-of-the-art methods such as O(nε^{-7}) and 2^{O(ε^{-1})} time algorithms.
We consider the problem of estimating the spectral density of the normalized adjacency matrix of an $n$-node undirected graph. We provide a randomized algorithm that, with $O(nε^{-2})$ queries to a degree and neighbor oracle and in $O(nε^{-3})$ time, estimates the spectrum up to $ε$ accuracy in the Wasserstein-1 metric. This improves on previous state-of-the-art methods, including an $O(nε^{-7})$ time algorithm from [Braverman et al., STOC 2022] and, for sufficiently small $ε$, a $2^{O(ε^{-1})}$ time method from [Cohen-Steiner et al., KDD 2018]. To achieve this result, we introduce a new notion of graph sparsification, which we call nuclear sparsification. We provide an $O(nε^{-2})$-query and $O(nε^{-2})$-time algorithm for computing $O(nε^{-2})$-sparse nuclear sparsifiers. We show that this bound is optimal in both its sparsity and query complexity, and we separate our results from the related notion of additive spectral sparsification. Of independent interest, we show that our sparsification method also yields the first deterministic algorithm for spectral density estimation that scales linearly with $n$ (sublinear in the representation size of the graph).