# Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2019.

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

- [Learning Parametrised Graph Shift Operators](https://mlsanity.com/paper/2101.10050/) (2021)

## Abstract (arXiv)

Spectral clustering is one of the most popular, yet still incompletely understood, methods for community detection on graphs. This article studies spectral clustering based on the Bethe-Hessian matrix Hr = (r2-1)In + D-rA for sparse heterogeneous graphs (following the degree-corrected stochastic block model) in a two-class setting. For a specific value r = zeta, clustering is shown to be insensitive to the degree heterogeneity. We then study the behavior of the informative eigenvector of Hzeta and, as a result, predict the clustering accuracy. The article concludes with an overview of the generalization to more than two classes along with extensive simulations on synthetic and real networks corroborating our findings.