Spectral Clustering of Graphs with the Bethe Hessian

Abstract

Spectral clustering is a standard approach to label nodes on a graph by studying the (largest or lowest) eigenvalues of a symmetric real matrix such as e.g. the adjacency or the Laplacian. Recently, it has been argued that using instead a more complicated, non-symmetric and higher dimensional operator, related to the non-backtracking walk on the graph, leads to improved performance in detecting clusters, and even to optimal performance for the stochastic block model. Here, we propose to use instead a simpler object, a symmetric real matrix known as the Bethe Hessian operator, or deformed Laplacian. We show that this approach combines the performances of the non-backtracking operator, thus detecting clusters all the way down to the theoretical limit in the stochastic block model, with the computational, theoretical and memory advantages of real symmetric matrices.

arXiv comment8 pages, 2 figures

Cited by in corpus (12)

• Statistical physics of inference: Thresholds and algorithms
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Phase Transitions in Semidefinite Relaxations
• Block Models and Personalized PageRank
• Estimating network edge probabilities by neighborhood smoothing
• Graph Comparison via the Non-backtracking Spectrum
• Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
• Community detection with nodal information
• Clustering from Sparse Pairwise Measurements
• Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method
• An Alon-Boppana theorem for powered graphs and generalized Ramanujan graphs
• How Well Do Local Algorithms Solve Semidefinite Programs?