# Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 41 references that are in the map.
- First posted on arXiv 28 Mar 2024.

## Builds on (most cited first, 16 of 16)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Clustering and Community Detection in Directed Networks: A Survey](https://mlsanity.com/paper/1308.0971/) (2013)
- [The Impact of Random Models on Clustering Similarity](https://mlsanity.com/paper/1701.06508/) (2017)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Hermitian matrices for clustering directed graphs: insights and applications](https://mlsanity.com/paper/1908.02096/) (2019)
- [Magnetic eigenmaps for community detection in directed networks](https://mlsanity.com/paper/1606.07359/) (2016)
- [Spectral Algorithms for Community Detection in Directed Networks](https://mlsanity.com/paper/2008.03820/) (2020)
- [Higher-Order Spectral Clustering of Directed Graphs](https://mlsanity.com/paper/2011.05080/) (2020)
- [Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity](https://mlsanity.com/paper/1403.5787/) (2014)
- [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)
- [Semiparametric spectral modeling of the Drosophila connectome](https://mlsanity.com/paper/1705.03297/) (2017)
- [Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs](https://mlsanity.com/paper/2203.01388/) (2022)

## Abstract (arXiv)

Graph clustering is a fundamental task in unsupervised learning with broad real-world applications. While spectral clustering methods for undirected graphs are well-established and guided by a minimum cut optimization consensus, their extension to directed graphs remains relatively underexplored due to the additional complexity introduced by edge directions. In this paper, we leverage statistical inference on stochastic block models to guide the development of a spectral clustering algorithm for directed graphs. Specifically, we study the maximum likelihood estimation under a widely used directed stochastic block model, and derive a global objective function that aligns with the underlying community structure. We further establish a theoretical upper bound on the misclustering error of its spectral relaxation, and based on this relaxation, introduce a novel, self-adaptive spectral clustering method for directed graphs. Extensive experiments on synthetic and real-world datasets demonstrate significant performance gains over existing baselines.