Title: Estimating a graph's spectrum via random Kirchhoff forests Show Chinese title

Title: 估计图的谱通过随机Kirchhoff森林

Abstract: Exact eigendecomposition of large matrices is very expensive, and it is practically impossible to compute exact eigenvalues. Instead, one may set a more modest goal of approaching the empirical distribution of the eigenvalues, recovering the overall shape of the eigenspectrum. Current approaches to spectral estimation typically work with \emph{moments} of the spectral distribution. These moments are first estimated using Monte Carlo trace estimators, then the estimates are combined to approximate the spectral density. In this article we show how \emph{Kirchhoff forests}, which are random forests on graphs, can be used to estimate certain non-linear moments of very large graph Laplacians. We show how to combine these moments into an estimate of the spectral density. If the estimate's desired precision isn't too high, our approach paves the way to the estimation of a graph's spectrum in time sublinear in the number of links. Show Chinese abstract

Abstract: 精确特征分解大矩阵非常昂贵，并且实际上不可能计算出精确的特征值。相反，可以设定一个更谦逊的目标，即逼近特征值的经验分布，恢复特征谱的整体形状。 当前谱估计的方法通常使用谱分布的 \emph{矩} 阶矩。 这些矩首先通过蒙特卡罗迹线估计器进行估计，然后将估计值组合起来以近似谱密度。 本文展示了如何利用 \emph{基尔霍夫森林} （图上的随机森林）来估计非常大的图拉普拉斯算子的某些非线性矩。 我们还展示了如何将这些矩组合成谱密度的估计值。 如果所需的估计精度不高，则我们的方法为以小于链接数量的子线性时间估算图的谱铺平了道路。