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

Abstract

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.

26 pages, 13 figures

References in corpus (35)

• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• The performance of modularity maximization in practical contexts
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Consistency of spectral clustering
• Limits of modularity maximization in community detection
• Spectral methods for network community detection and graph partitioning
• Phase transition in the detection of modules in sparse networks
• An efficient and principled method for detecting communities in networks
• Graph spectra and the detectability of community structure in networks
• Parsimonious module inference in large networks
• Community detection in networks: Structural communities versus ground truth
• Efficiently inferring community structure in bipartite networks
• Sparse random matrices: the eigenvalue spectrum revisited
• Entropy of stochastic blockmodel ensembles
• A single defect approximation for localized states on random lattices
• On the localization transition in symmetric random matrices
• Estimating the resolution limit of the map equation in community detection
• (Un)detectable cluster structure in sparse networks
• Exploring the limits of community detection strategies in complex networks
• Detectability of communities in heterogeneous networks
• Spectra of random graphs with community structure and arbitrary degrees
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• A paradox in community detection
• First eigenvalue/eigenvector in sparse random symmetric matrices: influences of degree fluctuation
• Improving the performance of algorithms to find communities in networks
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Phase Transitions in Community Detection: A Solvable Toy Model
• Global disorder transition in the community structure of large-q Potts systems

Cited by in corpus (18)

• Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Super-resolution community detection for layer-aggregated multilayer networks
• Mean-field theory of graph neural networks in graph partitioning
• Algorithmic detectability threshold of the stochastic block model
• Comparative analysis on the selection of number of clusters in community detection
• Detectability of the spectral method for sparse graph partitioning
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• A Tractable Fully Bayesian Method for the Stochastic Block Model
• Graph powering and spectral robustness
• Performance of a community detection algorithm based on semidefinite programming
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• Spectral partitioning in equitable graphs
• Detectability thresholds of general modular graphs
• Consistency between ordering and clustering methods for graphs
• Fragility of spectral clustering for networks with an overlapping structure
• Network construction: A learning framework through localizing principal eigenvector
• Spectral clustering of annotated graphs using a factor graph representation