Cucuringu, Li, Sun & Zanetti (AISTATS 2020) — Hermitian Matrices for Clustering Directed Graphs
Authors: Mihai Cucuringu (Oxford / Alan Turing Institute), He Li (Oxford / Alan Turing), He Sun (Edinburgh), Luca Zanetti (Oxford / Alan Turing).
Venue: AISTATS 2020 (PMLR 108).
Contribution
Introduces the Hermitian adjacency approach to clustering directed graphs: \tilde A = i(A - A^\top) which is skew-symmetric (i \cdot anti-symmetric matrix) and thus Hermitian with real eigenvalues. Take the top k (or \lceil k/2 \rceil) eigenvectors of \tilde A, project onto \mathbb{C}^p, k-means.
The algorithm directly optimizes a pairwise flow imbalance objective \sum_{a < b} |\text{Cut}(C_a, C_b) - \text{Cut}(C_b, C_a)| — i.e., clustering such that between any two clusters, the edge flow is strongly asymmetric.
Theoretical guarantee: in the Directed Stochastic Block Model (DSBM) setting, the algorithm correctly recovers clusters under suitable signal-to-noise conditions.
Importance to this wiki
This is the canonical algorithm in the Hermitian clustering family:
| Paper | Math | Objective | Time | Guarantee |
|---|---|---|---|---|
| Cucuringu 2020 (this paper) | i(A-A^\top) Hermitian adjacency | pairwise flow imbalance | O(kp^2) | DSBM |
| Laenen-Sun 2020 (NeurIPS) | Hermitian Laplacian with phase factor | chain flow ratio | \tilde O(m) | general digraphs |
| Bennett 2022 (ML) | Hermitian adjacency + RW normalization | pairwise flow imbalance | O(p^2TL + kp^2) | empirical (US equity) |
entities/He Sun is the common methodological thread across Cucuringu 2020 and Laenen-Sun 2020. entities/Mihai Cucuringu is the common author between Cucuringu 2020, Bennett 2022 (lead-lag application), and SPONGE.
See also
- Hermitian Spectral Clustering — methodology
- entities/Laenen Sun 2020 Higher-Order Spectral Clustering — alternative Hermitian formulation
- entities/Bennett Cucuringu Reinert 2022 Lead-Lag Network Clustering — financial application
- Hermitian Laplacian — Laenen-Sun alternative
- entities/Mihai Cucuringu / entities/He Sun — authors