spectral-sparsificationspielman-srivastavagraph-algorithmsnearly-linear-timestub

Spectral Sparsification

大白话：一张有上百万条边的图，其实只要保留 O(n\log n) 条精心挑的边，它的谱（Laplacian 特征值）就和原图几乎一样。用了这个技巧，谱聚类之类基于 Laplacian 的算法能从平方级时间降到近乎线性。

定义。 Spielman & Srivastava (2011) 的图谱稀疏化：给定图 G = (V, E)， 找 H = (V, F)（边子集 F \subseteq E，|F| = O(n \log n / \epsilon^2) 条边）， 使得 H 的 Laplacian L_H \approx L_G，谱差 |L_H - L_G| \le \epsilon。 应用：把 O(m) 条边降到 O(n \log n) 条边后， 任何基于 Laplacian 的算法（谱聚类、Laplacian 方程组求解、流）都能跑到近乎线性时间 O(m \cdot \log^c n)。

算法骨架（有效电阻采样）

输入: 图 G = (V, E), 边权 w
输出: 稀疏子图 H = (V, F)

对每条边 e = (u, v) ∈ E:
   R_e = effective resistance between u and v
   p_e = min(1, q · w(e) · R_e)   # q = O(log n / ε²) 控制采样总数

  # 总采样边数: |F| = O((1/λ²) · n · log n)
  # 其中 λ_2(L_G) 是 algebraic connectivity

以 p_e 概率采样 e 进 F
权重重标: w_H(e) = w(e) / p_e

关键：有效电阻 R_e 控制每条边的「重要度」，高有效电阻的边优先保留。

在 Laenen-Sun 2020 的 Hermitian Laplacian 中的角色

SimpleHerm 的加速子程序（Laenen-Sun §4.1）：

输入: digraph G, 目标 k
1. spectral_sparsify(G) → H     # O((1/λ²) · n · log n) 边
2. compute L_H (Hermitian Laplacian of H)
3. f_1 = min eigenvector of L_H
4. k-means in C² on (Re f_1, Im f_1)

Theorem 4.5（保持性）：H 以高概率满足 \theta_k(H) = \Omega(\theta_k(G)) 且 \lambda_2(L_H) = \Omega(\lambda_2(L_G))，因此稀疏化后 Hermitian Laplacian 的聚类结构得以保持，SimpleHerm 仍能恢复原始 G 的簇。

时间：稀疏化 O(m \log^c n) + Laplacian 方程组 O((1/\lambda^2) n \log^c n) + k-means O(nkd) → 总计 O(m \log^c n)（近乎线性）。

在有向图上的扩展

Laenen-Sun 2020 把谱稀疏化扩展到有向图：有效电阻在 Hermitian Laplacian 下定义， 采样策略与无向图对称；主要技术细节来自 Sun & Zanetti (2019) "Distributed graph clustering and sparsification"。

应用场景

  • 大规模有向图谱聚类（n > 10^5）：必须稀疏化，否则 O(m) 的计算不可行。
  • Laplacian 方程组求解：L x = b 在稀疏图上是 O(n \log^c n)，在稠密图上是 O(n^{1.5})。
  • 图神经网络中的图稀疏化：用谱稀疏化来做消息传递 (message passing) 的批处理。
  • 流式图聚类：一遍扫描边就能构造出稀疏化图。

邻近概念

起源 / 标准文献

  • Spielman & Srivastava (2011) SIAM J. Comput. "Graph sparsification by effective resistances" —— 原型
  • Batson, Spielman, Srivastava (2013) —— 更紧的界 O(n \log n / \epsilon^2)
  • Sun & Zanetti (2019) ACM TOPC —— 分布式扩展 + Hermitian Laplacian 应用（Laenen-Sun 的 ref [27]）
  • Laenen & Sun (NeurIPS 2020) —— 有向图谱稀疏化（本 wiki 摘要）

待研究问题

  • 动态图（边随时间增加）的「增量稀疏化」复杂度有多高？
  • 与 Graph Attention Network (GAT) 结合：GNN 的消息传递能否用谱稀疏化加速？
  • 对异质度分布（重尾度）的图，谱稀疏化后是否仍保持簇结构？