paperdirected-graphspectral-clusteringhermitian-laplacianflow-ratiocheeger-inequalityneurips-2020sparsification

Laenen & Sun (NeurIPS 2020) — Higher-Order Spectral Clustering of Directed Graphs

大白话：给有向图做聚类时，常规做法是丢掉边的方向或者用一堆绕圈的技巧来「补正」方向；这篇论文提出用 Hermitian 拉普拉斯矩阵把方向信息直接写进谱分解，得到一条链式（有序）的聚类目标函数，并给出首个适用于一般有向图（不只随机图模型）的近似比保证。

作者：Steinar Laenen (Oxford Research Group, FiveAI; then MSc at University of Edinburgh), He Sun (School of Informatics, University of Edinburgh).

出处：NeurIPS 2020 (Vancouver, Canada). Hash 0a5052334511e344f15ae0bfafd47a67.

贡献

为有向图引入了 Hermitian 拉普拉斯矩阵（Hermitian Laplacian）： A_{uv} = w(u,v) \cdot \omega_{2\pi/k} \quad \text{if } u \rightsquigarrow v, \quad L_G = I - D^{-1/2} A D^{-1/2} 以及 flow ratio（流量比） 目标函数（一种链式结构目标函数，只在有序划分中相邻的簇对之间求和）。

三项技术贡献：

  1. 谱嵌入定理（定理 3.2）：最优 flow-ratio 划分的指示向量，恰好就是 L_G 在 \mathbb{C}^n 上最小特征向量的各个分量，簇的位置用 k 次单位根的相位编码。
  2. Cheeger 式近似比保证（定理 4.4）：SimpleHerm 返回的划分 A_0, \ldots, A_{k-1} 满足 \text{vol}(A_j \triangle S_j) \le \epsilon \cdot \text{vol}(S_j)，其中 \epsilon = O(k^3 / (\gamma_k - 1))。这是首个适用于一般有向图的此类保证（不只适用于 DSBM）。
  3. 近线性时间：借助谱稀疏化（spectral sparsification, Spielman-Srivastava 2011），总时间 O(m \cdot \log^c n)，优于 Herm-RW 的 O(kp^2)（当 p \gg 10^3 时）。

SimpleHerm 算法只用到1 个特征向量（最小的那个），且在 \mathbb{C}^2 上运算；性能超过 Herm-RW（需要 \lceil k/2 \rceil 个）和 DD-SYM（Satuluri 2011，需要 k 个外加矩阵乘法）。

实验要点

  • 合成 DSBM（n=1000-2000，k=4-8，链式拓扑）：SimpleHerm 的 ARI \sim 1.0，显著优于 Herm-RW（0.2–0.5）和 DD-SYM（0.0）。
  • UN Comtrade 国际石油贸易（2002–2017，246 个国家，k=4）：2006–2008 稳定，2008–2009 剧烈转变（金融危机），2004–2005 另有一个高峰（委内瑞拉石油罢工 + 伊拉克战争 → 减产 540 万桶/日）。
  • UN Comtrade 国际木材贸易（k=4）：第 1 簇 = 加拿大 / 巴西 / 俄罗斯 / 德国 / 中国（森林资源丰富），2008–2009 的转变使东欧 / 中东 / 中亚跨簇移动。
  • COVID-19 韩国传染图（67 个顶点，66 条边，k=4）：识别出一个超级传播者簇。

对本 wiki 的重要性

这是有向图上 Hermitian 聚类理论基础的标准引用来源——与提供算法的 entities/Cucuringu Li Sun Zanetti 2020 Hermitian Adjacency 互补，也与把 Hermitian 随机游走用到金融领先-滞后关系的 entities/Bennett Cucuringu Reinert 2022 Lead-Lag Network Clustering 互补。

链式结构假设（沿着有向路径排列簇）天然契合贸易网络（出口 → 转运 → 加工 → 进口）、信息扩散和疫情传播——因此当簇之间是有序的（而不只是领先/滞后）时，这篇论文是标准参考。

相关页面