# Hermitian matrices for clustering directed graphs: insights and applications

arXiv: https://arxiv.org/abs/1908.02096 · HTML: https://mlsanity.com/paper/1908.02096/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2019.

## Built on by (most cited first, 27 of 27)

- [MagNet: A Neural Network for Directed Graphs](https://mlsanity.com/paper/2102.11391/) (2021)
- [PyTorch Geometric Signed Directed: A Software Package on Graph Neural Networks for Signed and Directed Graphs](https://mlsanity.com/paper/2202.10793/) (2022)
- [DIGRAC: Digraph Clustering Based on Flow Imbalance](https://mlsanity.com/paper/2106.05194/) (2021)
- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Lead-lag detection and network clustering for multivariate time series with an application to the US equity market](https://mlsanity.com/paper/2201.08283/) (2022)
- [Local Algorithms for Finding Densely Connected Clusters](https://mlsanity.com/paper/2106.05245/) (2021)
- [Koopman-based spectral clustering of directed and time-evolving graphs](https://mlsanity.com/paper/2204.02951/) (2022)
- [Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs](https://mlsanity.com/paper/2203.01388/) (2022)
- [Signed Directed Graph Contrastive Learning with Laplacian Augmentation](https://mlsanity.com/paper/2301.05163/) (2023)
- [Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning](https://mlsanity.com/paper/2102.10169/) (2021)
- [Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs](https://mlsanity.com/paper/2203.03221/) (2022)
- [Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues](https://mlsanity.com/paper/2211.09776/) (2022)
- [Transfer operators on graphs: Spectral clustering and beyond](https://mlsanity.com/paper/2305.11766/) (2023)
- [Structural Balance and Random Walks on Complex Networks with Complex Weights](https://mlsanity.com/paper/2307.01813/) (2023)
- [HyperMagNet: A Magnetic Laplacian based Hypergraph Neural Network](https://mlsanity.com/paper/2402.09676/) (2024)
- [A simpler spectral approach for clustering in directed networks](https://mlsanity.com/paper/2102.03188/) (2021)
- [A Graph Convolution for Signed Directed Graphs](https://mlsanity.com/paper/2208.11511/) (2022)
- [Parametrized Power-Iteration Clustering for Directed Graphs](https://mlsanity.com/paper/2210.00310/) (2022)
- [Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models](https://mlsanity.com/paper/2305.06704/) (2023)
- [Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian](https://mlsanity.com/paper/2407.12864/) (2024)
- [Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models](https://mlsanity.com/paper/2403.19516/) (2024)
- [A Spectral Framework for Tracking Communities in Evolving Networks](https://mlsanity.com/paper/2412.07378/) (2024)
- [Complex non-backtracking matrix for directed graphs](https://mlsanity.com/paper/2507.12503/) (2025)
- [Online Sparsification of Bipartite-Like Clusters in Graphs](https://mlsanity.com/paper/2508.05437/) (2025)
- [An Improved and Generalised Analysis for Spectral Clustering](https://mlsanity.com/paper/2511.23261/) (2025)
- [Self-Attention as Transport: Limits of Symmetric Spectral Diagnostics](https://mlsanity.com/paper/2605.04893/) (2026)
- [Hierarchical Clustering and Signal Denoising on Digraphs](https://mlsanity.com/paper/2609.34670/) (2026)

## Abstract (arXiv)

Graph clustering is a basic technique in machine learning, and has widespread applications in different domains. While spectral techniques have been successfully applied for clustering undirected graphs, the performance of spectral clustering algorithms for directed graphs (digraphs) is not in general satisfactory: these algorithms usually require symmetrising the matrix representing a digraph, and typical objective functions for undirected graph clustering do not capture cluster-structures in which the information given by the direction of the edges is crucial. To overcome these downsides, we propose a spectral clustering algorithm based on a complex-valued matrix representation of digraphs. We analyse its theoretical performance on a Stochastic Block Model for digraphs in which the cluster-structure is given not only by variations in edge densities, but also by the direction of the edges. The significance of our work is highlighted on a data set pertaining to internal migration in the United States: while previous spectral clustering algorithms for digraphs can only reveal that people are more likely to move between counties that are geographically close, our approach is able to cluster together counties with a similar socio-economical profile even when they are geographically distant, and illustrates how people tend to move from rural to more urbanised areas.