Hermitian Laplacian
Definition. Laenen & Sun (NeurIPS 2020) 提出的有向图 Laplacian, 在无向图 Laplacian 的基础上引入相位因子 \omega_{2\pi/k}: A_{uv} = w(u,v) \cdot \omega_{2\pi/k} \quad \text{if } u \rightsquigarrow v L_G = I - D^{-1/2} A D^{-1/2} 其中 D 对角元 D_{uu} = d^{\text{in}}_u + d^{\text{out}}_u = \text{vol}(u)。A 是 Hermitian (因 A_{uv} = \overline{A_{vu}}), 因此 L_G 也是 Hermitian, 实特征值, 谱分解良定义。
与 Cucuringu 2020 Hermitian adjacency 的关键区别
| 维度 | Cucuringu 2020 Herm-RW | Laenen-Sun 2020 Hermitian Laplacian |
|---|---|---|
| 数学对象 | i(A - A^\top) (反对称 Hermitian) | I - D^{-1/2} A D^{-1/2}, A 含 phase factor |
| 相位 | i = \omega_{\pi/2} (固定 k=4 phase) | \omega_{2\pi/k} (任意 k) |
| 目标 | Pairwise flow imbalance (任意 k cluster 对) | Chain flow ratio (cluster 沿链展开) |
| 特征向量数 | \lceil k/2 \rceil | 1 (最小特征向量, 嵌入 \mathbb{C}^2) |
| 时间复杂度 | O(k p^2) | \tilde O(m) (sparsification) |
| 理论保证 | DSBM 下保证 | 通用 Cheeger 风格保证 (Theorem 4.4) |
Phase factor 的物理含义
\omega_{2\pi/k} = e^{2\pi i / k} 是 k 次单位根, 把每个 cluster 的"位置"编码到 k 个等分复数方向上 (位于单位圆):
ω_0 = 1 k=4 时
1
ω_3 ω_1 ω_3 ω_1
ω_2 = -1 ω_2 = -1
把 cluster j 的 indicator 乘以 \omega_{2\pi j/k} 后, 不同 cluster 的点云在 \mathbb{C}^2 上围绕原点散开, 且"散开方向"反映 cluster 在链中的位置。最小特征向量就是这个"散开结构"的线性组合。
谱聚类算法 SimpleHerm
1. 构造 A_{uv} = w(u,v) · ω_{2π/k} for u ⇝ v
2. D = diag(in_degree + out_degree)
3. L = I - D^{-1/2} A D^{-1/2}
4. f_1 = min eigenvector of L in C^n
5. 把 f_1 的 (Re, Im) 作为 2D 嵌入
6. k-means 在 C 中
7. (稀疏化) 先做 Spielman-Srivastava 谱稀疏化降边数, 再算 L → O(m · log^c n)
关键观察: f_1 \approx \sum_{j=0}^{k-1} \chi_j, 即所有 cluster indicator 的相位加权组合。f_1 在 \mathbb{C}^2 上的"散开角度"由 cluster 在链中的位置决定 — 不需要多个特征向量。
理论保证 (Theorem 4.4)
设 \{S_0, \ldots, S_{k-1}\} 是 flow ratio \Phi^* 的最优划分, \gamma_k = 1 / (1 - \Phi^*), APT 是 k-means 近似比, 则 SimpleHerm 输出 \{A_0, \ldots, A_{k-1}\} 满足:
\text{vol}(A_j \triangle S_j) \le \epsilon \cdot \text{vol}(S_j), \quad \epsilon = \frac{48 k^3 (1 + \text{APT})}{\gamma_k - 1}
- 与无向图 Cheeger 不等式 (k=2 时) 完全同构。
- \gamma_k - 1 是 "flow ratio gap", 越大 → cluster 结构越显著 → 越易恢复。
- k^3 因子是"链式"目标比"成对"目标更难的代价。
- 不限 DSBM: 对通用有向图 成立 (Cucuringu 2020 限 DSBM)。
在金融 lead-lag 上的适用性 (与 Bennett 2022 对比)
| 维度 | Hermitian Laplacian (Laenen-Sun) | Hermitian RW (Bennett 2022) |
|---|---|---|
| 适用 lead-lag 场景 | 强: 美股 / 国际油贸 都有链式结构 | 强: lead-lag 可解释为 cluster 流方向 |
| 时间复杂度 | \tilde O(m) (大规模图友好) | O(k p^2) (中小图) |
| 美股 lead-lag ARI | 未实证 | ~ 1.0 (合成) / 实测显著 (434 stocks) |
| 解释性 | 额外: cluster 在链中的"位置" (出口 / 中 / 进口) | Pairwise "谁 lead 谁" |
潜在应用: 美股 lead-lag 用 Hermitian Laplacian 看 cluster 是否沿 "value chain" 排序 (上游行业 → 中游 → 下游消费); 国际油贸直接用 Laenen-Sun 2020 实证。
邻近概念
- Hermitian Spectral Clustering — 父类
- Flow Ratio (chain objective) — 目标函数
- Spectral Sparsification — 加速子程序
- Directed Network Clustering — 算法全景
- Lead-Lag Detection — 下游金融应用
起源 / 标准文献
- Laenen & Sun (NeurIPS 2020) — 原始定义 + 理论 + UN Comtrade + COVID-19 (本 wiki 摘要 summaries/202012-higher-order-spectral-clustering-directed-graphs/202012-higher-order-spectral-clustering-directed-graphs)
- Cucuringu, Li, Sun, Zanetti (AISTATS 2020) — 同期 Hermitian adjacency 算法 (ref [9])
- Chung (2005) "Laplacians and the Cheeger inequality for directed graphs" — 早期 directed Laplacian
- Peng, Sun, Zanetti (2017) SIAM J. Comput. — 无向 spectral clustering 理论 (ref [23])
- Spielman & Srivastava (2011) — 谱稀疏化 (ref [26])
- Shi & Malik (1997) — Normalized cuts (ref [25])
Open Questions
- 美股 lead-lag 数据上跑 Hermitian Laplacian, cluster 是否沿价值链 (上游材料 → 中游制造 → 下游消费) 排序? 与 Bennett 2022 的"行业聚类"是否对齐?
- k 自适应: 链的"长度"通常未知 (贸易链有几个 cluster?), 能否用特征值间隙估计?
- 与 Graph Neural Network (He 2021 DGCN) 结合, 把节点特征融入 Hermitian 谱分解?
- 异步 / 动态图 (有向边权随时间变化) 上的 Hermitian Laplacian 是否仍稳定?