An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs
2026-06-26 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how hard it is to estimate the spectral density, which is a way to understand the structure, of a graph using random walks. Previous work showed that for weighted graphs, you need an exponentially large number of random walks to get a good approximation. The authors extend this result to unweighted graphs, proving that even with many long random walks from random nodes, you cannot efficiently approximate the spectrum. This means estimating the spectral density for unweighted graphs is also very computationally hard.
spectral densitynormalized adjacency matrixrandom walksunweighted graphsWasserstein distanceexponential lower boundgraph spectrumapproximation algorithms
Authors
Pan Peng, Yuyang Wang, Joy Qiping Yang, Yichun Yang
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 $\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.