Spectral Clustering of Graphs with the Bethe Hessian
A. Saade1, F. Krzakala1,2 and L. Zdeborová3 1 Laboratoire de Physique Statistique, CNRS UMR 8550, Université P. et M. Curie Paris 6 et École Normale Supérieure, 24, rue Lhomond, 75005 Paris, France. 2 ESPCI and CNRS UMR 7083 Gulliver, 10 rue Vauquelin,Paris 75005 3 Institut de Physique Théorique, CEA Saclay and URA 2306, CNRS, 91191 Gif-sur-Yvette, France
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.
中文速览
图神经网络聚类领域长期依赖谱聚类方法，但标准谱方法（如基于邻接矩阵或拉普拉斯矩阵的算法）在稀疏随机块模型（stochastic block model, SBM）上表现欠佳，往往在理论可检测阈值附近就彻底失效；虽然基于非回溯游走（non-backtracking walk）算子的谱方法能达到理论最优，但它涉及高维非对称矩阵，计算和内存代价较高。本文提出用一个更简单的对称实矩阵——Bethe Hessian 算子（又称形变拉普拉斯矩阵）——来替代非回溯算子做图聚类，通过分析其与非回溯算子谱的严格对应关系，证明将参数设为图的非回溯谱半径的平方根时，该算子的负特征值恰好逐一对应可检测的社区结构，从而在随机块模型上一路检测到理论极限。数值实验表明，Bethe Hessian 在合成网络和真实世界网络上的表现均与非回溯算子相当甚至略优，同时完全继承了对称实矩阵在计算效率、内存占用和线性代数工具支持上的全部优势，还能自然推广到加权图，为稀疏图社区检测提供了一个理论最优且实用的谱算法。
原文 arXiv:1406.1880;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1406.1880v2