spectral-sparsificationspielman-srivastavagraph-algorithmsnearly-linear-timestub

Spectral Sparsification

Definition. 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 system solving、flow) 都能跑出近乎线性时间 O(m \cdot \log^c n)。

算法骨架 (effective resistance sampling)

输入: 图 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

关键: effective resistance R_e 控制每条边的"重要度", 高 effective resistance 的边优先保留。

在 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 (preservation): H 满足 \theta_k(H) = \Omega(\theta_k(G)) 且 \lambda_2(L_H) = \Omega(\lambda_2(L_G)) (以高概率), 因此稀疏化后Hermitian Laplacian 的聚类结构得以保持, SimpleHerm 仍能恢复原始 G 的 cluster。

时间: 稀疏化 O(m \log^c n) + Laplacian system O((1/\lambda^2) n \log^c n) + k-means O(nkd) → 总 O(m \log^c n) (nearly-linear)。

在有向图上的扩展

Laenen-Sun 2020 把 Spectral Sparsification 扩展到有向图: effective resistance 在 Hermitian Laplacian 下定义, 采样策略与无向图对称; 主要技术细节来自 Sun & Zanetti (2019) "Distributed graph clustering and sparsification"。

应用场景

  • 大规模有向图谱聚类 (n > 10^5): 必须稀疏化, 否则 O(m) 计算不可能。
  • Laplacian system solving: L x = b 在稀疏图上 O(n \log^c n), 在稠密图 O(n^{1.5})。
  • Graph sparsification for graph neural networks: 用谱稀疏化做 message passing 的 batching。
  • Streaming graph clustering: 一遍扫描边即可构造稀疏化图。

邻近概念

起源 / 标准文献

  • 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 应用 (ref [27] of Laenen-Sun)
  • Laenen & Sun (NeurIPS 2020) — 有向图谱稀疏化 (本 wiki 摘要)

Open Questions

  • 动态图 (边随时间增加) 的"incremental sparsification" 复杂度?
  • 与 Graph Attention Network (GAT) 结合: GNN 的 message passing 能否用谱稀疏化加速?
  • 对异质性度分布 (heavy-tailed degree) 的图, 谱稀疏化后是否仍保持 cluster 结构?