谱稀疏化 | Codeboy's Blog

形式陈述

谱稀疏化是图的割稀疏化目标的强化特例：它近似整个位势二次型，因此自动近似所有割；反过来，只控制割值不必控制每个实向量方向。

定义与量词

设 $G=(V,E,w)$ 是 $n$ 个顶点、正边权的无向图， $L_G$ 是它的组合图 Laplacian；零权边不贡献任何二次型，可在开始前直接移除。由原图部分边重赋非负权得到 $H=(V,E_H,\widetilde w)$ ，其中 $E_H\subseteq E$ 。称它为 $G$ 的 $\varepsilon$ -spectral sparsifier，若 $0<\varepsilon<1$ 且对所有

x\in\mathbb R^V

同时有

(1-\varepsilon)x^{\mathsf T}L_Gx \le x^{\mathsf T}L_Hx \le(1+\varepsilon)x^{\mathsf T}L_Gx.

等价地，按 Loewner 次序

(1-\varepsilon)L_G\preceq L_H\preceq(1+\varepsilon)L_G.

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

为什么谱近似蕴含割近似

图能量满足

x^{\mathsf T}L_Gx =\sum_{\{u,v\}\in E}w_{uv}(x_u-x_v)^2.

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

\mathbf1_S^{\mathsf T}L_G\mathbf1_S=w_G(\delta(S)).

谱稀疏器因此同时近似所有割。同精度的反向蕴含不成立。取单位权三角形 $G$ ，把 $H$ 的边 $01,02,12$ 分别赋权 $5/4,5/4,1/4$ 。原图三个单点割的容量都为二，新图分别为 $5/2,3/2,3/2$ ；三点图的全部非平凡割都对应一个单点或其补集，所以它是 $\varepsilon=1/4$ 的割近似。但对 $x=(0,1,-1)$ ，原能量为六，新能量为 $5/4+5/4+4\cdot(1/4)=7/2$ ，小于谱下界 $(3/4)\cdot6=9/2$ 。全部割方向的近似并未控制这个实向量方向。

有效电阻与 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,\qquad \tau_e=w_eR_e,

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

w_eb_eb_e^{\mathsf T}

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

0<\tau_e\le1,\qquad \sum_{e\in E}\tau_e=n-c,

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

显式采样规则与边数

令 $r=n-c$ 。若 $r=0$ ，图没有正权边，直接返回原图。以下设 $r>0$ ，固定 $0<\varepsilon<1$ 、 $0<\delta<1$ ，并取

a=\frac{3}{\varepsilon^2}\log\frac{2r}{\delta},\qquad q_e=\min\{1,a\tau_e\}.

独立抽取 $\xi_e\sim\operatorname{Bernoulli}(q_e)$ ；采中时保留边并赋权 $\widetilde w_e=w_e/q_e$ ，否则删除。于是

L_H=\sum_e\frac{\xi_e}{q_e}w_eb_eb_e^{\mathsf T},\qquad \mathbb EL_H=L_G.

下面证明：至少以 $1-\delta$ 的概率， $H$ 是 $\varepsilon$ -谱稀疏器。此外，边数 $M=|E_H|$ 满足

\mathbb EM=\sum_eq_e\le a\sum_e\tau_e =\frac{3r}{\varepsilon^2}\log\frac{2r}{\delta}.

这是一条期望边数界，单次输出的边数仍是随机变量；它不是“每次最多这么多条边”的保证。输出是否满足谱近似与输出有多少条边也是两个不同事件，需要同时限制时应另为边数分配失败概率。

归一化：把相对能量误差变成单位矩阵误差

记 $L=L_G$ ， $U=\operatorname{im}L=(\ker L)^\perp$ 。 $L$ 在整个顶点空间上通常奇异，但限制到 $r$ 维空间 $U$ 后正定。令 $L^{+/2}$ 表示伪逆的半正定平方根，并在 $U$ 上定义

B_e=L^{+/2}w_eb_eb_e^{\mathsf T}L^{+/2}.

每个 $b_e$ 与原图各连通分量的常向量正交，因此属于 $U$ 。由 $L=\sum_ew_eb_eb_e^{\mathsf T}$ 得

\sum_eB_e=I_U.

写 $B_e=z_ez_e^{\mathsf T}$ ，其中 $z_e=\sqrt{w_e}L^{+/2}b_e$ ，就有

\|B_e\|_2=\operatorname{tr}B_e=\|z_e\|_2^2=\tau_e, \qquad B_e^2=\tau_e B_e.

因为 $I_U-B_e$ 是其他半正定项之和， $B_e\preceq I_U$ ，所以 $\tau_e\le1$ ；对总和取迹又得到 $\sum_e\tau_e=\operatorname{tr}I_U=r$ 。正权非自环边的 $z_e\ne0$ ，故 $\tau_e>0$ 。这些恒等式同时解释了采样概率与边数为何取决于 $r$ 而不是原边数。

幅度、方差与失败概率逐项计算

归一化后的误差可写成独立中心化矩阵之和：

L^{+/2}(L_H-L)L^{+/2}\big|_U=\sum_eX_e, \qquad X_e=\left(\frac{\xi_e}{q_e}-1\right)B_e.

$q_e=1$ 的项恒为零。对 $q_e<1$ 的项， $q_e=a\tau_e$ ，且 $|\xi_e/q_e-1|\le1/q_e$ ，于是

\|X_e\|_2\le\frac{\tau_e}{q_e}=\frac1a.

Bernoulli 方差给出 $\mathbb E(\xi_e/q_e-1)^2=1/q_e-1$ ，因此

\mathbb EX_e^2 =\left(\frac1{q_e}-1\right)\tau_e B_e \preceq\frac1a B_e, \qquad \left\|\sum_e\mathbb EX_e^2\right\|_2\le\frac1a.

这里用到了 $B_e^2=\tau_e B_e$ ，没有把每项范数粗略相加。在 $U$ 上应用矩阵 Bernstein 不等式，取维数 $d=r$ 、幅度 $R=1/a$ 、方差上界 $v\le1/a$ 、阈值 $t=\varepsilon$ ，得到

\Pr\!\left(\left\|\sum_eX_e\right\|_2\ge\varepsilon\right) \le2r\exp\!\left(-\frac{a\varepsilon^2}{2(1+\varepsilon/3)}\right) \le\delta.

最后一个不等式来自 $2(1+\varepsilon/3)<3$ 与 $a\varepsilon^2=3\log(2r/\delta)$ 。如果所有随机项都为零，就直接得到精确相等，无需使用正方差版本的定理。

回到全空间：共同的零方向如何处理

在上述成功事件上， $-\varepsilon I_U\preceq\sum_eX_e\preceq\varepsilon I_U$ 。设 $P_U$ 是到 $U$ 的正交投影。由于采样只删除和重权原图边， $L$ 与 $L_H$ 都消去 $\ker L$ ，归一化误差在该核上也为零。因此全空间中有

-\varepsilon P_U\preceq L^{+/2}(L_H-L)L^{+/2}\preceq\varepsilon P_U.

左右作 $L^{1/2}$ 的合同变换，利用 $L^{1/2}L^{+/2}=P_U$ 及 $P_U(L_H-L)P_U=L_H-L$ ，得到

-\varepsilon L\preceq L_H-L\preceq\varepsilon L.

这就是所需谱近似。再由 $1-\varepsilon>0$ ，成功时 $L_H$ 也不可能在 $U$ 中产生新零方向，所以它与 $L$ 的核完全相同，保留原图的连通分量划分。无偏性只说明平均值正确；逐项幅度、矩阵方差与这段核空间论证共同给出一次抽样后的统一保证。

直觉

每条边贡献一个 rank-one Laplacian，有效电阻衡量这项在总能量中的不可替代程度。在这里的子图采样模型中，桥必须保留，稠密图中的冗余边则可低概率采样并重权；在 $L_G$ 的像空间归一化后，矩阵集中一次性控制所有向量方向，而不只是逐割无偏。

有效电阻采样将图稀疏化，并对任意实向量保持 Laplacian 能量 — 谱稀疏化对全部实向量的能量保证

例子与边界

具体例子：树与完全图

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

对 $n\ge2$ ，在无权完全图 $K_n$ 中， $L=nI-J$ ，在 $\mathbf1^\perp$ 上等于 $nI$ 。每个 $b_e$ 的平方长度为 $2$ ，故 $R_e=\tau_e=2/n$ 。当 $a\cdot2/n<1$ 时，每条边以 $2a/n$ 的概率保留，从 $\Theta(n^2)$ 条边降到期望 $a(n-1)=O(n\log(n/\delta)/\varepsilon^2)$ 条；若概率被截断为 $1$ ，该参数下规则直接保留原图。

完整代入： $K_{1000}$ 的一次采样设计

取 $\varepsilon=0.5$ 、 $\delta=0.05$ 。原图有 $499500$ 条边， $r=999$ 、 $\tau_e=0.002$ ，所以

a=12\log(39960)\approx127.14761079, \qquad q_e=0.002a\approx0.2542952216.

逐边独立保留，采中边的权从 $1$ 改成 $1/q_e\approx3.93244$ 。期望边数为

\mathbb EM=499500q_e=999a\approx127020.4632.

这不是整数配额：实际 $M$ 服从 $\operatorname{Bin}(499500,q_e)$ 。把同一组参数代入已经证明的矩阵尾界，实际得到

2\cdot999\exp\!\left(-\frac{a\cdot0.5^2}{2(1+0.5/3)}\right) \approx0.0024222551<0.05.

因此至少以 $0.9975777$ 的概率，每个向量的图能量同时处于原能量的 $[0.5,1.5]$ 倍内。这项计算把采样率、重权、期望边数和谱失败概率连在一起；只验证 $\mathbb EL_H=L$ 无法得到最后的概率保证。

核、断开图与失败边界

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

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

推论与应用

按有效电阻或 leverage score 随机采样并重标权属于随机化算法。这里的显式证明给出 Spielman–Srivastava 型独立采样结果，其期望边数含一个对数因子。Batson–Spielman–Srivastava 使用不同的迭代势方法可得到 $O(n/\varepsilon^2)$ 条边；这个更强边数结论并非上述独立采样规则的直接推论。

谱稀疏器既保留所有割，也保留拉普拉斯二次型，因而可用于近似流割、Laplacian 线性系统预条件与更快的谱图算法。只需割值时 cut sparsifier 的接口更弱；有向图、负权和邻接矩阵谱则需要不同模型。

参考资料

Joel A. Tropp, User-Friendly Tail Bounds for Sums of Random Matrices，2011-06-15 修订预印本，Theorem 6.1(ii)、Lemma 6.7；本页在像空间上应用其双侧推论。
Rasmus Kyng, Lecture 8: Matrix Concentration and Spectral Sparsification，ETH Zürich, 2020，§2：有效电阻采样与归一化分析。
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, Cambridge University Press open manuscript, sparsification chapters, accessed 2026.

形式陈述 ​

定义与量词 ​

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

有效电阻与 leverage score ​

显式采样规则与边数 ​

归一化：把相对能量误差变成单位矩阵误差 ​

幅度、方差与失败概率逐项计算 ​

回到全空间：共同的零方向如何处理 ​

具体例子：树与完全图 ​

完整代入：K1000 的一次采样设计 ​

核、断开图与失败边界 ​

反向链接