Hermitian Spectral Clustering
Definition. 把有向加权网络的邻接矩阵 A 反对称化后乘虚数单位 i, 构造 Hermitian 矩阵 \tilde A = i(A - A^\top) 取 \tilde A 的前 k 个最大模特征向量 g_1, \ldots, g_k, 在 \mathbb{C}^p 上做 k-means, 得到"最大化两两 flow imbalance 的 k 类分割" (Cucuringu et al. 2020)。Hermitian RW 是其随机游走归一化版本, 在 lead-lag 网络上表现最佳 (Bennett-Cucuringu-Reinert 2022 实证)。
算法
# Pseudocode (Cucuringu 2020 + Bennett 2022 Hermitian RW)
# 1. 邻接矩阵反对称化并 Hermitian 化
A_tilde = 1j * (A - A.T)
# 2. 随机游走归一化 (Hermitian RW)
D = np.diag(A_tilde.sum(axis=1)) # 或按度归一化
A_rw = D^{-1/2} @ A_tilde @ D^{-1/2} # 实际需要双侧, 因 A_tilde 不对称
# 3. 取前 k 个最大 |λ| 特征向量
eigvals, eigvecs = eigh(A_tilde) # Hermitian 保证实特征值
idx = np.argsort(-np.abs(eigvals))[:k]
G = eigvecs[:, idx] # p × k 嵌入
# 4. 复数 k-means
labels = kmeans(G, n_clusters=k)
复杂度: O(kp^2 + p^3)。p 大时用 m = O(p \log p) 边采样 + 幂迭代, 近似线性。
关键性质
| 性质 | 描述 |
|---|---|
| 目标 | 找 k-partition C_1, \ldots, C_k 最大化 \sum_{a<b} \lvert\text{Cut}(C_a, C_b) - \text{Cut}(C_b, C_a)\rvert |
| 基础定理 | Cucuringu 2020 Theorem 1.1: 真实聚类在 \sigma 噪声下能被 Hermitian 谱恢复 (DSBM setting) |
| 与谱聚类区别 | 标准 spectral clustering 对对称邻接跑, 只看密度; Hermitian 利用反对称部分 (方向) 提取 flow |
| 谱含义 | 大特征值对应"有净流出方向的群组", 即 leader cluster; 小特征值对应 follower cluster |
横向对比 (Bennett 2022 §3.2 实证)
| 方法 | 目标 | 美股 lead-lag 表现 |
|---|---|---|
| Naive symmetrisation (A + A^\top) | 看密度 | 基线, ARI 显著低 |
| Bibliometric symmetrisation (Satuluri-Parthasarathy 2011) | 度折扣 + 共入/出 link | 中等 |
| DI-SIM co-clustering (Rohe 2016) | 找 send/recv 行为近似的两 partition | 接近 Hermitian RW |
| Hermitian RW (Cucuringu 2020) | 直接优化 flow imbalance | 最优 |
| Leiden (Traag 2019, directed modularity) | 最大化 directed modularity | 不适合 — 基于密度, 不利用方向 |
在美股 lead-lag 上的实证 (Bennett 2022)
- 434 NYSE 高流动性股票, 2000-2019,
ccf-auc + distance correlation构造 lead-lag matrix。 - k=10 聚类, 与 SIC 行业 Jaccard 平均 < 0.15 — 解释能力超出行业。
- 与"成交量 lead-lag" (Chordia-Swaminathan 2000)、"市值 lead-lag" (Lo-MacKinlay 1990) 均不相关 (Spearman 0.01 / -0.15)。
- 年间 ARI 0.05-0.20 (弱持续性), 2012 后衰减。
- 下游交易信号 Sharpe 0.62 / p<0.004, 显著高于 LASSO-VAR (0.27 / p>0.13) 与 S&P 500 买入持有 (0.40)。
邻近概念
- Lead-Lag Detection — 上游 pairwise metric
- Directed Network Clustering — 聚类算法全景
- Meta-Flow Graph — 聚类结果的可视化
- RowSum Leadingness — 聚类内 lead 排序
- Cartea Cucuringu Jin 2023 SPONGE — 同一 Cucuringu 团队后续 signed graph 聚类工作
起源 / 标准文献
- Cucuringu, Li, Sun & Zanetti (2020) "Hermitian matrices for clustering directed graphs: insights and applications" — 算法原型 (TDA 视角下的 Hermitian 谱方法)
- Bennett, Cucuringu, Reinert (2022) — Hermitian RW 在美股 lead-lag 上的应用 + 对比 (本 wiki 摘要)
- Rohe, Qin & Yu (2016) — DI-SIM co-clustering
- Satuluri & Parthasarathy (2011) — Bibliometric symmetrisation
- Laenen & Sun (2020) — 后续 Hermitian Laplacian 归一化变体
- Underwood, Elliot & Cucuringu (2020) — motif-based 谱聚类
Open Questions
- Hermitian RW 的 k 是 hyperparameter; 在 lead-lag 场景下能否用 eigenvalue gap (前 k vs 第 k+1 模) 自动选 k?
- 在 A 股 ~5000 股票上直接跑 Hermitian RW 是否仍可扩展 (5000² 矩阵计算 vs Bennett 2022 的 434)?
- 能否把 Hermitian 谱与 factor model 结合, 把"行业因子"作为先验约束入特征空间?