谱稀疏化

定义与量词 ​

设 $G=(V,E,w)$ 是 $n$ 个顶点、正边权的无向图，$L_G$ 为组合 Laplacian；零权边不贡献任何二次型，可在开始前直接移除。图 $H=(V,E_H,\tilde{w})$ 是 $G$ 的 $\epsilon$-spectral sparsifier，若 $0<\epsilon <1$ 且对所有

$$x\in {\mathbb{R}}^V$$

同时有

$$(1-\epsilon )x^{\mathsf{T}}{L}_{G}x\le x^{\mathsf{T}}{L}_{H}x\le (1+\epsilon )x^{\mathsf{T}}{L}_{G}x.$$

等价地，按 Loewner 次序公理库正定与半正定矩阵Positive definite matrix · Positive semidefinite matrix · PSD matrix由二次能量严格为正或非负定义的实对称与复 Hermitian 矩阵。

$$(1-\epsilon )L_G⪯L_H⪯(1+\epsilon )L_G.$$

量词是一次随机采样后对所有 $x$ 同时成立，不是对每个固定 $x$ 分别高概率成立。

为什么谱近似蕴含割近似 ​

图能量满足

$$x^{\mathsf{T}}{L}_{G}x=\sum _{\{u,v\}\in E}{w}_{uv}(x_u-x_v{)}^2.$$

取集合 $S\subseteq V$ 的指示向量 $x={\mathbf{1}}_S$，只有跨越割 $\delta (S)$ 的边贡献 $1$，所以

$${\mathbf{1}}_S^{\mathsf{T}}{L}_G{\mathbf{1}}_S=w_G(\delta (S)).$$

谱稀疏器因此同时近似所有割。反向不成立：割向量只是 $\{0,1{\}}^V$ 中的特殊方向，保留它们未必控制任意实向量的能量，也未必适合作 Laplacian 线性系统预条件器。

有效电阻与 leverage score ​

给边 $e=\{u,v\}$ 定向并令

$$b_e={\mathbf{e}}_u-{\mathbf{e}}_v.$$

其有效电阻与 leverage score 为

$$R_e=b_e^{\mathsf{T}}{L}_G^{+}{b}_e,{\tau }_e=w_e{R}_e,$$

其中 $L_G^{+}$ 是 Moore–Penrose 伪逆。${\tau }_e$ 衡量边的 rank-one Laplacian

$$w_e{b}_e{b}_e^{\mathsf{T}}$$

在总能量中的不可替代程度，并满足

$$0<{\tau }_e\le 1,\sum _{e\in E}{\tau }_e=n-c,$$

$c$ 是 $G$ 的连通分量数。桥的 ${\tau }_e=1$；稠密图中许多冗余边的 leverage 很小。

采样、重权与边数 ​

固定失败概率 $0<\delta <1$，独立地以

$$q_e=min\{1,C\frac{{\tau }_e\log \left(n/\delta \right)}{{\epsilon }^2}\}$$

采样每条边。若采中，就在 $H$ 中赋权

$${\tilde{w}}_e=\frac{w_e}{q_e};$$

否则删除。重权保证

$$\mathbb{E}[L_H]=L_G.$$

更重要的是，矩阵 Chernoff/Bernstein 不等式在 $L_G$ 的像空间上同时控制全部特征方向，给出概率至少 $1-\delta$ 的谱近似。期望边数为

$$\sum _e{q}_e=O\left(\frac{(n-c)\log \left(n/\delta \right)}{{\epsilon }^2}\right).$$

这是 Spielman–Srivastava 型经典随机结果。Batson–Spielman–Srivastava 通过不同的迭代势方法可得到 $O(n/{\epsilon }^2)$ 边；不能把更强边数写成简单独立有效电阻采样的直接结论。

矩阵集中证明骨架 ​

在 $L_G$ 的像空间中归一化每条边：

$$Y_e=L_G^{+/2}\frac{w_e}{q_e}{b}_e{b}_e^{\mathsf{T}}{L}_G^{+/2}{\xi }_e,$$

其中 ${\xi }_e$ 是采样指示变量。则

$$\mathbb{E}\sum _e{Y}_e=L_G^{+/2}{L}_G{L}_G^{+/2},$$

即投影到每个连通分量内与常向量正交的空间。又因为

$$\Vert L_G^{+/2}{w}_e{b}_e{b}_e^{\mathsf{T}}{L}_G^{+/2}\Vert ={\tau }_e,$$

按 ${\tau }_e$ 选择 $q_e$ 使每个随机矩阵项的谱范数被 $O({\epsilon }^2/\log \left(n/\delta \right))$ 控制。矩阵集中于是把归一化和压在 $(1\pm \epsilon )$ 投影之间；左右乘 $L_G^{1/2}$ 就恢复所需 Loewner 不等式。

无偏性本身远远不够：它只控制每个矩阵元素的期望，不能保证指数多个向量方向同时准确。Leverage 采样正是为了给矩阵尾界提供逐项范数上限。

具体例子：树与完全图 ​

若 $G$ 是一棵树，每条边都是桥，${\tau }_e=1$。采样概率因而截断为 $1$，结构不会删除任何边；删掉树边会增加 Laplacian 核维数，连最基本的连通性都无法保持。树已经没有谱意义上的冗余。

在无权完全图 $K_n$ 中，每条边有效电阻为 $2/n$，故 ${\tau }_e=2/n$。每条边只需约 $O(\log \left(n/\delta \right)/(n{\epsilon }^2))$ 的采样概率，最终从 $\mathrm{\Theta }(n^2)$ 条边降到 $O(n\log \left(n/\delta \right)/{\epsilon }^2)$，重权后仍近似全部能量方向。

核、断开图与失败边界 ​

$L_G$ 的核由各连通分量的常向量张成。谱比较必须在相同顶点空间上理解，并要求 $H$ 保留同一分量划分；否则存在某个 $x$ 在 $G$ 中能量为零、在 $H$ 中不为零，或反之。对断开图，可在每个分量上使用伪逆与采样，孤立顶点原样保留。

本页近似的是 Laplacian，不是邻接矩阵特征值。负边权会破坏边 Laplacian 的半正定分解，有向图也不再给出同一对称能量，不能直接套用。准确或近似计算所有有效电阻本身需要 Laplacian 求解器；快速构造使用近似 leverage scores，过高估计仍安全但会增加边数，低估则可能破坏保证。

参考资料

• Daniel A. Spielman and Nikhil Srivastava, “Graph Sparsification by Effective Resistances,” SIAM Journal on Computing 40(6), 2011, 1913–1926.
• Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava, “Twice-Ramanujan Sparsifiers,” SIAM Journal on Computing 41(6), 2012.
• Daniel A. Spielman, Spectral and Algebraic Graph Theory, lecture notes, sparsification chapters.