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 is a cornerstone of machine learning, used to find communities in social networks, protein interactions, and more. Most standard algorithms, such as traditional Spectral Clustering, are designed for undirected graphs where the goal is to identify groups of nodes with high internal edge density.
When applied to directed graphs (digraphs), researchers typically "symmetrize" the adjacency matrix, treating a directed edge from A to B as a simple undirected connection. However, this process discards the very information that defines a digraph: the flow. In networks like migration patterns or political citations, the directionality—who is moving where or who is citing whom—is often more informative than the mere existence of a connection. Existing digraph methods often focus on local motifs, potentially missing large-scale imbalanced transitions between distant regions.
Methodology: The Hermitian Approach
To preserve directional information, we propose using a Hermitian adjacency matrix representation. For a digraph $G$, we define a complex-valued matrix $A$ where:
- $A_{u,v} = i$ (the imaginary unit) if there is an edge from $u$ to $v$.
- $A_{u,v} = -i$ if there is an edge from $v$ to $u$.
- $A_{u,v} = 0$ otherwise.
Because $A$ is Hermitian ($A = A^*$), its eigenvalues are real, allowing us to leverage standard spectral machinery. Our algorithm computes the top eigenvectors of this matrix to construct a projection matrix, which is then clustered using $k$-means.
To evaluate this method, we utilize the Directed Stochastic Block Model (DSBM). In this generative model, clusters are defined not just by edge density, but by the probability of edge directions between clusters (e.g., a cyclic pattern where Cluster 1 mostly points to Cluster 2, which points to Cluster 3).
Experimental Results
Synthetic Performance
On synthetic cyclic models, our Hermitian method maintains high recovery accuracy (Adjusted Rand Index) even as noise increases. Crucially, the algorithm can recover "ground truth" clusters even when edge density is uniform across the graph and the only signal is the direction of the edges—a scenario where traditional symmetrized spectral clustering fails completely.
US Migration Patterns
We applied our method to the 2000 US Census data, representing migration flows between 3,107 counties. Traditional naive clustering methods simply group counties by geographical proximity (e.g., by state boundaries). In contrast, our Hermitian approach identifies clusters based on socio-economic profiles and migration "sinks."
As shown in the figures above, our method identifies a "top pair" of clusters where 68% of the total edge weight is oriented from one cluster (source) to the other (sink). This highlights a clear rural-to-urban migration trend that transcends simple geography, grouping distant rural counties together based on their shared role as migration sources.
Political Polarization
In a network of 1,212 political blogs from the 2004 US election, the algorithm successfully separated Republican and Democratic blogs. It achieved this by identifying imbalanced citation patterns, capturing the partisan structure of the network through the flow of information.
Discussion and Future Work
By using the imaginary unit $i$, we encode directionality into a single complex value, allowing eigenvectors to "sense" edge orientation. This enables the capture of higher-order structures—relationships between clusters rather than just properties within them.
However, some limitations remain. The current representation may discard information from reciprocal edges (edges existing in both directions). Additionally, while the algorithm is empirically successful, a formal "relaxation" proof connecting this spectral method to a discrete objective function (similar to the relationship between standard spectral clustering and Normalized Cut) is still needed. Future research will explore hybrid approaches that can interpolate between density-based and flow-based clustering depending on the dataset's characteristics.
Summary updated