An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs
It resolves an open problem by extending the exponential lower bound from weighted to unweighted graphs, establishing fundamental limits for spectral density estimation.
The paper proves an exponential lower bound for spectral density estimation on unweighted graphs, showing that no algorithm can achieve ε-approximation with constant success probability even with 2^{Ω(1/ε^{1/6})} random walks of length 2^{Ω(1/ε^{1/6})}.
We study lower bounds for estimating the spectral density of the normalized adjacency matrix of a graph. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\varepsilon$-approximate spectral density estimation in the Wasserstein-1 distance, using $2^{O(1/\varepsilon)}$ random walks initiated from uniformly random nodes in the graph. Later, Jin et al. [COLT 2023] established a nearly matching exponential lower bound for \emph{weighted} graphs, assuming the algorithm has access to samples from random walks started at random nodes. It was left open whether this lower bound could be extended to \emph{unweighted} graphs. In this paper, we answer this question in the affirmative by proving an exponential lower bound for unweighted graphs. Specifically, we show that no algorithm can compute an $\varepsilon$-approximation to the spectrum of a normalized graph adjacency matrix with constant success probability, even when given the full transcripts of $2^{Ω(1/\varepsilon^{1/6})}$ random walks, each of length $2^{Ω(1/\varepsilon^{1/6})}$, started from uniformly random nodes.