Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913872544268288 |
|---|---|
| author | Zhang, Ning Dong, Xiaowen Cucuringu, Mihai |
| author_facet | Zhang, Ning Dong, Xiaowen Cucuringu, Mihai |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_19516 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models Zhang, Ning Dong, Xiaowen Cucuringu, Mihai Machine Learning Social and Information Networks Statistics Theory 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. |
| title | Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models |
| topic | Machine Learning Social and Information Networks Statistics Theory |
| url | https://arxiv.org/abs/2403.19516 |