An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs

Abstract

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 ε-approximate spectral density estimation in the Wasserstein-1 distance, using 2^O(1/ε) 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 ε-approximation to the spectrum of a normalized graph adjacency matrix with constant success probability, even when given the full transcripts of 2^Ω(1/ε^1/6) random walks, each of length 2^Ω(1/ε^1/6), started from uniformly random nodes.