谱稀疏化

形式陈述 ​

谱稀疏化是图的割稀疏化公理库图的割稀疏化Cut sparsification · Cut sparsifier用较少重权边近似保留原图全部割值；谱稀疏化作为更强的相邻模型另行区分。目标的强化特例：它近似整个位势二次型，因此自动近似所有割；反过来，只控制割值不必控制每个实向量方向。

定义与量词 ​

设 $G=(V,E,w)$ 是 $n$ 个顶点、正边权的无向图，$L_G$ 是它的组合图 Laplacian公理库图 LaplacianGraph Laplacian · Laplacian matrix用度矩阵减邻接矩阵得到的算子，以二次型衡量相邻顶点取值的不一致。；零权边不贡献任何二次型，可在开始前直接移除。由原图部分边重赋非负权得到 $H=(V,E_H,\tilde{w})$，其中 $E_H\subseteq E$。称它为 $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)).$$

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

显式采样规则与边数 ​

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

$$a=\frac{3}{{\epsilon }^2}\log \frac{2r}{\delta },q_e=min\{1,a{\tau }_e\}.$$

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

$$L_H=\sum _e\frac{{\xi }_e}{q_e}{w}_e{b}_e{b}_e^{\mathsf{T}},\mathbb{E}{L}_H=L_G.$$

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

$$\mathbb{E}M=\sum _e{q}_e\le a\sum _e{\tau }_e=\frac{3r}{{\epsilon }^2}\log \frac{2r}{\delta }.$$

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

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

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

$$B_e=L^{+/2}{w}_e{b}_e{b}_e^{\mathsf{T}}{L}^{+/2}.$$

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

$$\sum _e{B}_e=I_U.$$

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

$$\Vert B_e{\Vert }_2=\mathrm{tr}{B}_e=\Vert z_e{\Vert }_2^2={\tau }_e,B_e^2={\tau }_e{B}_e.$$

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

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

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

$$L^{+/2}(L_H-L)L^{+/2}{|}_U=\sum _e{X}_e,X_e=(\frac{{\xi }_e}{q_e}-1)B_e.$$

$q_e=1$ 的项恒为零。对 $q_e<1$ 的项，$q_e=a{\tau }_e$，且 $|{\xi }_e/q_e-1|\le 1/q_e$，于是

$$\Vert X_e{\Vert }_2\le \frac{{\tau }_e}{q_e}=\frac{1}{a}.$$

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

$$\mathbb{E}{X}_e^2=(\frac{1}{q_e}-1){\tau }_e{B}_e⪯\frac{1}{a}{B}_e,{\Vert \sum _e\mathbb{E}{X}_e^2\Vert }_2\le \frac{1}{a}.$$

这里用到了 $B_e^2={\tau }_e{B}_e$，没有把每项范数粗略相加。在 $U$ 上应用矩阵 Bernstein 不等式公理库矩阵 Bernstein 不等式Matrix Bernstein inequality · 矩阵伯恩斯坦不等式用逐项谱范数与矩阵方差控制独立中心化 Hermitian 矩阵和，借助 Lieb 凹性完成非交换指数矩证明，并计算随机图邻接矩阵的统一方向误差。，取维数 $d=r$、幅度 $R=1/a$、方差上界 $v\le 1/a$、阈值 $t=\epsilon$，得到

$$\text{Pr}({\Vert \sum _e{X}_e\Vert }_2\ge \epsilon )\le 2r\exp (-\frac{a{\epsilon }^2}{2(1+\epsilon /3)})\le \delta .$$

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

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

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

$$-\epsilon P_U⪯L^{+/2}(L_H-L)L^{+/2}⪯\epsilon P_U.$$

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

$$-\epsilon L⪯L_H-L⪯\epsilon L.$$

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

直觉

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

例子与边界

具体例子：树与完全图 ​

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

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

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

取 $\epsilon =0.5$、$\delta =0.05$。原图有 $499500$ 条边，$r=999$、${\tau }_e=0.002$，所以

$$a=12\log \left(39960\right)\approx 127.14761079,q_e=0.002a\approx 0.2542952216.$$

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

$$\mathbb{E}M=499500q_e=999a\approx 127020.4632.$$

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

$$2\cdot 999\exp (-\frac{a\cdot {0.5}^2}{2(1+0.5/3)})\approx 0.0024222551<0.05.$$

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

核、断开图与失败边界 ​

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

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

推论与应用

按有效电阻或 leverage score 随机采样并重标权属于随机化算法公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。。这里的显式证明给出 Spielman–Srivastava 型独立采样结果，其期望边数含一个对数因子。Batson–Spielman–Srivastava 使用不同的迭代势方法可得到 $O(n/{\epsilon }^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.