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

Ning Zhang, Xiaowen Dong, Mihai Cucuringu
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:928-936, 2026.

Abstract

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. Building on its spectral relaxation, we propose two novel spectral clustering algorithms for directed graphs and establish theoretical guarantees for their misclustering error. Extensive experiments on synthetic and real-world datasets demonstrate significant performance gains over existing baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-zhang26a, title = { Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models }, author = {Zhang, Ning and Dong, Xiaowen and Cucuringu, Mihai}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {928--936}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/zhang26a/zhang26a.pdf}, url = {https://proceedings.mlr.press/v300/zhang26a.html}, abstract = { 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. Building on its spectral relaxation, we propose two novel spectral clustering algorithms for directed graphs and establish theoretical guarantees for their misclustering error. Extensive experiments on synthetic and real-world datasets demonstrate significant performance gains over existing baselines. } }
Endnote
%0 Conference Paper %T Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models %A Ning Zhang %A Xiaowen Dong %A Mihai Cucuringu %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-zhang26a %I PMLR %P 928--936 %U https://proceedings.mlr.press/v300/zhang26a.html %V 300 %X 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. Building on its spectral relaxation, we propose two novel spectral clustering algorithms for directed graphs and establish theoretical guarantees for their misclustering error. Extensive experiments on synthetic and real-world datasets demonstrate significant performance gains over existing baselines.
APA
Zhang, N., Dong, X. & Cucuringu, M.. (2026). Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:928-936 Available from https://proceedings.mlr.press/v300/zhang26a.html.

Related Material