Abstract
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.
Introduction
Graph clustering typically aims to identify groups of nodes with high internal connectivity compared to the rest of the network. While spectral methods are well-established for undirected graphs, they often falter when applied to directed graphs (digraphs). The standard practice of "symmetrizing" a digraph—treating a directed edge from A to B as a simple connection—effectively discards the "flow" of information. This loss of directional data prevents algorithms from capturing structures defined by imbalances in edge direction rather than just density. This paper addresses this gap by introducing a spectral clustering framework that leverages complex numbers to preserve the inherent antisymmetry of directed edges.
Methodology
The proposed approach utilizes a complex-valued Hermitian adjacency matrix ($A$) to represent the digraph. In this representation, an edge from node $u$ to $v$ is encoded as $A_{u,v} = i$ (the imaginary unit), while the reverse edge is $A_{v,u} = -i$. This construction ensures the matrix is Hermitian ($A = A^*$), guaranteeing real eigenvalues and making it suitable for spectral analysis.
The Algorithm
The core algorithm computes the top eigenvectors of this Hermitian matrix to generate a low-dimensional embedding, followed by standard $k$-means clustering. To handle real-world networks with skewed degree distributions, the authors introduce a random-walk normalized version ($A_{rw} = D^{-1}A$).
Directed Stochastic Block Model (DSBM)
To evaluate the method, the authors developed the DSBM, a generative model where clusters are defined by both edge density and directional bias. This framework allows for testing the algorithm's ability to recover cluster structures even when edge density is uniform across the entire graph, relying solely on the "flow" between groups.
Experimental Results
Synthetic Performance
The Hermitian methods (HERM and HERM-RW) were benchmarked against state-of-the-art digraph clustering methods like DISG and DD-Sym using synthetic DSBM data. As shown in the figure below, the proposed methods demonstrate superior recovery of ground-truth clusters (measured by Adjusted Rand Index, ARI) across various noise levels ($\eta$) and edge probabilities ($p$).
Real-World Application: US Migration
The algorithm's practical utility is most evident in the analysis of US internal migration data (2000 Census). Traditional naive spectral methods primarily group counties by geographical proximity, reflecting that people often move to neighboring states. In contrast, the Hermitian approach identifies socio-economic patterns, clustering rural areas together and separating them from urban hubs, regardless of distance. This reveals a clear directional trend: the migration flow from rural to urbanized regions.
Conclusion
By utilizing complex-valued Hermitian matrices, this research provides a robust framework for clustering directed graphs that respects the "arrow" of information. The method is computationally efficient, maintaining the sparsity of the original graph, and excels at uncovering directional flow patterns that symmetrization methods miss. Future work will focus on automated parameter selection and extending theoretical guarantees to more complex, non-uniform density scenarios.
Summary updated