# Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2015.

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

- [Consistency between ordering and clustering methods for graphs](https://mlsanity.com/paper/2208.12933/) (2022)

## Abstract (arXiv)

Investigating the performance of different methods is a fundamental problem in graph partitioning. In this paper, we estimate the so-called detectability threshold for the spectral method with both unnormalized and normalized Laplacians in sparse graphs. The detectability threshold is the critical point at which the result of the spectral method is completely uncorrelated to the planted partition. We also analyze whether the localization of eigenvectors affects the partitioning performance in the detectable region. We use the replica method, which is often used in the field of spin-glass theory, and focus on the case of bisection. We show that the gap between the estimated threshold for the spectral method and the threshold obtained from Bayesian inference is considerable in sparse graphs, even without eigenvector localization. This gap closes in a dense limit.