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

Area of Science:

• Graph theory
• Statistical physics
• Network science

Background:

• Graph partitioning is crucial for analyzing large networks.
• Spectral methods are widely used but their performance limits, especially in sparse graphs, require investigation.
• Understanding the detectability threshold is key to assessing partitioning accuracy.

Purpose of the Study:

• To estimate the detectability threshold for spectral graph partitioning using un-normalized and normalized Laplacians in sparse graphs.
• To analyze the impact of eigenvector localization on partitioning performance within the detectable region.
• To compare the spectral method's threshold with that from Bayesian inference.

Main Methods:

• Utilizing the replica method, a tool from spin-glass theory.
• Focusing on the bisection case for graph partitioning.
• Estimating detectability thresholds for spectral methods with different Laplacians.

Main Results:

• A considerable gap exists between the spectral method's estimated threshold and the Bayesian inference threshold in sparse graphs.
• This gap persists even without considering eigenvector localization.
• The gap diminishes in the dense graph limit.

Conclusions:

• The spectral method's performance in sparse graphs is significantly different from Bayesian inference, even under ideal eigenvector conditions.
• Eigenvector localization has a limited impact on partitioning performance in the detectable region.
• The choice of graph density critically influences the performance gap between spectral and Bayesian inference methods.