我们研究了对图的归一化邻接矩阵谱密度估计的下界。Cohen-Steiner 等人 [KDD 2018] 提出了一个算法，用于在 Wasserstein-1 距离下进行 $\epsilon$-近似谱密度估计，该算法使用 $2^{O(1/\epsilon)}$ 次从随机节点发起的随机游走。随后，Jin 等人 [COLT 2023] 在假设算法可以访问从随机节点开始的随机游走样本的情况下，确立了加权图的近似匹配指数下界。然而，关于这个下界是否可以扩展到无权图的问题仍未解决。
本文对此进行了肯定的回答，证明了无权图的指数下界。具体而言，我们展示了即使在给定从均匀随机节点开始的 $2^{\Omega(1/\epsilon^{1/6})}$ 次随机游走的完整记录时，任何算法也无法以恒定成功概率计算归一化图邻接矩阵的 $\epsilon$-近似谱，且每次随机游走的长度为 $2^{\Omega(1/\epsilon^{1/6})}$。
博主点评： 这项研究为无权图的谱密度估计提供了重要的理论基础，揭示了在估计过程中可能遇到的固有难度，特别是在算法设计和复杂性理论方面具有深远的影响。对于图论及其应用领域的研究者而言，这一成果无疑是值得关注的里程碑。