# Higher-Order Spectral Clustering of Directed Graphs

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2020.

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

- [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)
- [High-order Multi-view Clustering for Generic Data](https://mlsanity.com/paper/2209.10838/) (2022)
- [Local Algorithms for Finding Densely Connected Clusters](https://mlsanity.com/paper/2106.05245/) (2021)
- [Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs](https://mlsanity.com/paper/2203.01388/) (2022)
- [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)
- [A simpler spectral approach for clustering in directed networks](https://mlsanity.com/paper/2102.03188/) (2021)
- [A Probabilistic Framework for Knowledge Graph Data Augmentation](https://mlsanity.com/paper/2110.13205/) (2021)
- [Parametrized Power-Iteration Clustering for Directed Graphs](https://mlsanity.com/paper/2210.00310/) (2022)
- [On Learning the Structure of Clusters in Graphs](https://mlsanity.com/paper/2212.14345/) (2022)
- [Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models](https://mlsanity.com/paper/2403.19516/) (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)
- [Hierarchical Clustering and Signal Denoising on Digraphs](https://mlsanity.com/paper/2609.34670/) (2026)

## Abstract (arXiv)

Clustering is an important topic in algorithms, and has a number of applications in machine learning, computer vision, statistics, and several other research disciplines. Traditional objectives of graph clustering are to find clusters with low conductance. Not only are these objectives just applicable for undirected graphs, they are also incapable to take the relationships between clusters into account, which could be crucial for many applications. To overcome these downsides, we study directed graphs (digraphs) whose clusters exhibit further "structural" information amongst each other. Based on the Hermitian matrix representation of digraphs, we present a nearly-linear time algorithm for digraph clustering, and further show that our proposed algorithm can be implemented in sublinear time under reasonable assumptions. The significance of our theoretical work is demonstrated by extensive experimental results on the UN Comtrade Dataset: the output clustering of our algorithm exhibits not only how the clusters (sets of countries) relate to each other with respect to their import and export records, but also how these clusters evolve over time, in accordance with known facts in international trade.