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\epsilon^{-2})$ queries to a degree and neighbor
oracle and in $O(n\epsilon^{-3})$ time, estimates the spectrum up to $\epsilon$
accuracy in the Wasserstein-1 metric. This improves on previous
state-of-the-art methods, including an $O(n\epsilon^{-7})$ time algorithm from
[Braverman et al., STOC 2022] and, for sufficiently small $\epsilon$, a
$2^{O(\epsilon^{-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\epsilon^{-2})$-query and
$O(n\epsilon^{-2})$-time algorithm for computing $O(n\epsilon^{-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).

利用一种随机算法和核稀疏化的方法，该研究提出了一种新的图谱估计方法，可在线性时间和多项式查询复杂度下，准确估计归一化邻接矩阵的谱密度。这一方法在复杂度和准确性方面均具有优势，且创造性地解决了图的稀疏化和添加谱稀疏化的相关问题。