We study lower bounds for estimating the spectral density of the normalized adjacency matrix of a graph. Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\epsilon$-approximate spectral density estimation in the Wasserstein-1 distance, using $2^{O(1/\epsilon)}$ random walks initiated from uniformly random nodes in the graph. Later, Jin et al. [COLT 2023] established a nearly matching exponential lower bound for 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 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 $\epsilon$-approximation to the spectrum of a normalized graph adjacency matrix with constant success probability, even when given the full transcripts of $2^{\Omega(1/\epsilon^{1/6})}$ random walks, each of length $2^{\Omega(1/\epsilon^{1/6})}$, started from uniformly random nodes.
Blogger's Review: This research provides a significant theoretical foundation for spectral density estimation in unweighted graphs, revealing inherent difficulties that may arise during estimation, particularly with profound implications for algorithm design and complexity theory. This result is undoubtedly a milestone worth noting for researchers in graph theory and its applications.