Spectral Clustering of graphs with the Bethe Hessian
Published in
Neural Information Processing Systems(2014)External Links:
TL
TL;DR
This work proposes to use a simpler object, a symmetric real matrix known as the Bethe Hessian operator, or deformed Laplacian, and shows 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.
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.
References23 items
1
Spectral density of the non-backtracking operator on random graphs
2
Community detection thresholds and the weak Ramanujan property
3
Spectral redemption in clustering sparse networks
4
The Bethe approximation for solving the inverse Ising problem: a comparison with other inference methods
5