Cucuringu, Li, Sun & Zanetti (AISTATS 2020) — Hermitian Matrices for Clustering Directed Graphs
大白话：这篇论文给出对有向图做聚类的 Hermitian 邻接矩阵做法，把「两个簇之间的边流量是否对称」变成一个可以直接最小化的目标，代价是一次特征分解加 k-means。
作者：Mihai Cucuringu（Oxford / Alan Turing Institute）、He Li（Oxford / Alan Turing）、He Sun（Edinburgh）、Luca Zanetti（Oxford / Alan Turing）。
发表于：AISTATS 2020（PMLR 108）。
贡献
提出用 Hermitian 邻接矩阵 (Hermitian adjacency) 给有向图做聚类的方法： \tilde A = i(A - A^\top) 它是斜对称的（i \cdot 反对称矩阵），因此是 Hermitian 的，且特征值为实数。取 \tilde A 的前 k（或 \lceil k/2 \rceil）个特征向量，投影到 \mathbb{C}^p，再做 k-means。
该算法直接优化一个成对流量不平衡目标 \sum_{a < b} |\text{Cut}(C_a, C_b) - \text{Cut}(C_b, C_a)| —— 即聚类使得任意两个簇之间的边流强烈不对称。
理论保证：在有向随机块模型 (Directed Stochastic Block Model, DSBM) 设定下，只要信噪比条件合适，算法能正确还原聚类。
对本 wiki 的意义
这是 Hermitian 聚类家族中的标准算法：
| 论文 | 数学形式 | 目标函数 | 时间复杂度 | 保证 |
|---|---|---|---|---|
| Cucuringu 2020（本文） | i(A-A^\top) Hermitian 邻接矩阵 | 成对流量不平衡 | O(kp^2) | DSBM |
| Laenen-Sun 2020（NeurIPS） | 带相位因子的 Hermitian 拉普拉斯矩阵 | 链式流量比 | \tilde O(m) | 一般有向图 |
| Bennett 2022（ML） | Hermitian 邻接矩阵 + RW 归一化 | 成对流量不平衡 | O(p^2TL + kp^2) | 实证（美股） |
entities/He Sun 是 Cucuringu 2020 与 Laenen-Sun 2020 共同的方法主线。entities/Mihai Cucuringu 则是 Cucuringu 2020、Bennett 2022（领先-滞后应用）与 SPONGE 之间的共同作者。
相关页面
- Hermitian Spectral Clustering —— 方法论
- entities/Laenen Sun 2020 Higher-Order Spectral Clustering —— 另一种 Hermitian 形式
- entities/Bennett Cucuringu Reinert 2022 Lead-Lag Network Clustering —— 金融应用
- Hermitian Laplacian —— Laenen-Sun 的替代方案
- entities/Mihai Cucuringu / entities/He Sun —— 作者