An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
复制标题
DOI：
10.1137/1.9781611975031.85
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
N. Srivastava;L. Trevisan
中科院分区：
文献类型：
--
作者：
N. Srivastava;L. Trevisan
我们针对一般（不一定是正则）加权图证明以下 Alon-Boppana 型定理：如果 $G$ 是平均组合度 $d$ 的 $n$ 节点加权无向图（即 $G$ 有 $dn/2$ 边）且周长 $g> 2d^{1/8}+1$，并且如果 $\lambda_1 \leq \lambda_2 \leq \cdots \lambda_n$ 是$G$ 的（非归一化）拉普拉斯算子的特征值，则 \[ \frac {\lambda_n}{\lambda_2} \geq 1 + \frac 4{\sqrt d} - O \left( \frac 1{d^{\frac 58} }\right) \] （阿隆-博帕纳定理意味着，如果 $G$ 未加权且 $d$ 为正则，则 $\frac {\lambda_n}{\lambda_2} \geq 1 + \frac 4{\sqrt d} - O\left( \frac 1 d \right)$ 如果直径至少为 $d^{1.5}$。）我们的结果意味着谱稀疏器的下界。图 $H$ 是图 $G$ 的谱 $\epsilon$ 稀疏器，如果 \[ L(G) \preceq L(H) \preceq (1+\epsilon) L(G) \] 其中 $L(G)$ 是 $G$ 的拉普拉斯矩阵，$L(H)$ 是 $H$ 的拉普拉斯矩阵。 Batson、Spielman 和 Srivastava 证明，对于每个 $G$，都有一个平均度为 $d$ 的 $\epsilon$ 稀疏器 $H$，其中 $\epsilon \approx \frac {4\sqrt 2}{\sqrt d}$ 并且 $H$ 的边是 $G$ 边的（加权）子集。 Batson、Spielman 和 Srivastava 还表明，当 $G$ 是一个派系时，$\epsilon$ 上的界限不能降低到 $\approx \frac 2{\sqrt d}$ 以下；我们的 Alon-Boppana 型结果意味着，当 $G$ 来自超等度和超等周长的扩展器系列时，$\epsilon$ 不能减少到 $\approx \frac 4{\sqrt d}$ 以下。 Batson、Spielman 和 Srivastava 的方法证明了一个更一般的结果，即稀疏化一级矩阵的和，并且他们的方法适用于“在线”设置。我们表明，对于在线矩阵设置，$4\sqrt 2 / \sqrt d$ 界限很紧，直到低阶项。
We prove the following Alon-Boppana type theorem for general (not necessarily regular) weighted graphs: if $G$ is an $n$-node weighted undirected graph of average combinatorial degree $d$ (that is, $G$ has $dn/2$ edges) and girth $g> 2d^{1/8}+1$, and if $\lambda_1 \leq \lambda_2 \leq \cdots \lambda_n$ are the eigenvalues of the (non-normalized) Laplacian of $G$, then \[ \frac {\lambda_n}{\lambda_2} \geq 1 + \frac 4{\sqrt d} - O \left( \frac 1{d^{\frac 58} }\right) \] (The Alon-Boppana theorem implies that if $G$ is unweighted and $d$-regular, then $\frac {\lambda_n}{\lambda_2} \geq 1 + \frac 4{\sqrt d} - O\left( \frac 1 d \right)$ if the diameter is at least $d^{1.5}$.) Our result implies a lower bound for spectral sparsifiers. A graph $H$ is a spectral $\epsilon$-sparsifier of a graph $G$ if \[ L(G) \preceq L(H) \preceq (1+\epsilon) L(G) \] where $L(G)$ is the Laplacian matrix of $G$ and $L(H)$ is the Laplacian matrix of $H$. Batson, Spielman and Srivastava proved that for every $G$ there is an $\epsilon$-sparsifier $H$ of average degree $d$ where $\epsilon \approx \frac {4\sqrt 2}{\sqrt d}$ and the edges of $H$ are a (weighted) subset of the edges of $G$. Batson, Spielman and Srivastava also show that the bound on $\epsilon$ cannot be reduced below $\approx \frac 2{\sqrt d}$ when $G$ is a clique; our Alon-Boppana-type result implies that $\epsilon$ cannot be reduced below $\approx \frac 4{\sqrt d}$ when $G$ comes from a family of expanders of super-constant degree and super-constant girth. The method of Batson, Spielman and Srivastava proves a more general result, about sparsifying sums of rank-one matrices, and their method applies to an "online" setting. We show that for the online matrix setting the $4\sqrt 2 / \sqrt d$ bound is tight, up to lower order terms.