Spectral Clustering of Graphs with the Bethe Hessian
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.
Clustering a graph into groups or functional modules (sometimes called communities) is a central task in many fields ranging from machine learning to biology. A common benchmark for this problem is to consider graphs generated by the stochastic block model (SBM) [7,22]. In this case, one considers n vertices and each of them has a group label g v ∈ {1, . . . , q}. A graph is then created as follows: all edges are generated independently according to a q × q matrix p of probabilities, with Pr[A u,v = 1] = p gu,gv . The group labels are hidden, and the task is to infer them from the knowledge of the graph. The stochastic block model generates graphs that are a generalization of the Erdős-Rényi ensemble where an unknown labeling has been hidden.
We concentrate on the sparse case, where algorithmic challenges appear. In this case p ab is O(1/n), and we denote p ab = c ab /n. For simplicity we concentrate on the most commonly-studied case where groups are equally sized, c ab = c in if a = b and c ab = c out if a = b. Fixing c in > c out is referred to as the assortative case, because vertices from the same group connect with higher probability than with vertices from other groups. c out > c in is called the disassortative case. An important conjecture [4] is that any tractable algorithm will only detect communities if
where c is the average degree. In the case of q = 2 groups, in particular, this has been rigorously proven [15,12] (in this case, one can also prove that no algorithm could detect communities if this condition is not met). An ideal clustering algorithm should have a low computational complexity while being able to perform optimally for the stochastic block model, detecting clusters down to the transition (1).
So far there are two algorithms in the literature able to detect clusters down to the transition (1). One is a message-passing algorithm based on belief-propagation [5,4]. This algorithm, however, needs to be fed with the correct parameters of the stochastic block model to perform well, and its computational complexity scales quadratically with the number of clusters, which is an important practical limitation. To avoid such problems, the most popular non-parametric approaches to clustering are spectral methods, where one classifies vertices according to the eigenvectors of a matrix associated with the network, for instance its adjacency matrix [11,16]. However, while this works remarkably well on regular, or dense enough graphs [2], the standard versions of spectral clustering are suboptimal on graphs generated by the SBM, and in some cases completely fail to detect communities even when other (more complex) algorithms such as belief propagation can do so. Recently, a new class of spectral algorithms based on the use of a non-backtracking walk on the directed edges of the graph has been introduced [9] and argued to be better suited for spectral clustering. In particular, it has been shown to be optimal for graphs generated by the stochastic block model, and able to detect communities even in the sparse case all the way down to the theoretical limit (1).
These results are, however, not entirely satisfactory. First, the use a of a high-dimensional matrix (of dimension 2m -where m is the number of edges -rather than n, the number of nodes) can be expensive, both in terms of computational time and memory. Secondly, linear algebra methods are faster and more efficient for symmetric matrices than non-symmetric ones. The first problem was partially resolved in [9] where an equivalent operator of dimensions 2n was shown to exist. It was still, however, a non-symmetric one and more importantly, the reduction does not extend to weighted graphs, and thus presents a strong limitation.
In this contribution, we provide the best of both worlds: a non-parametric spectral algorithm for clustering with a symmetric n × n, real operator that performs as well as the non-backtracking operator of [9], in the sense that it identifies communities as soon as (1) holds. We show numerically that our approach performs as well as the belief-propagation algorithm, without needing prior knowledge of any parameter, making it the simplest algorithmically among the best-performing clustering methods. This operator is actually not new, and has been known as the Bethe Hessian in the context of statistical physics and machine learning [14,17] or the deformed Laplacian in other fields. However, to the best of our knowledge, it has never been considered in the context of spectral clustering.
The paper is organized as follows. In Sec. 1 we give the expression of the Bethe Hessian operator. We discuss in detail its properties and its connection with both the non-backtracking operator and an Ising spin glass in Sec. 2. In Sec. 3, we study analytically the spectrum in the case of the stochastic block model. Finally, in Sec. 4 we perform numerical tests on both the stochastic block model and on some real networks.
Summary:This paper proposes a new spectral approach for clustering/community detection of graphs.It builds upon a recent approach based on the non-backtracking random walk operator whose spectral properties allow community detection or clustering of graphs generated by the Stochastoc Block Model down to the theorectical limit.Observing that the non-backtracking random walk operator is non-symmetric, high-dimensional and complicated, the authors of this submission propose using a simpler, symmetric operator, the Bethe Hessian, and show that its spectrum is closely related to that of the non-backtracking walk operator and achieves the same theoretical performance limit. The authors also derive connections to Bethe free energy of a certain Ising model, offering perspectives from spin glass theory and phase transition of random graphs.Experiments on synthetic networks confirm their theorectical result. On several real networks where the assumption of Stochastic Block Modelmay not hold, the proposed algorithm still performs quite well.  Quality: This work is of decent quality: the proposed approach is interesting and potentially useful in real applications, the authors provide clear arguments about its performance guarantee and connections to other methods. The only thing that is a bit disappointing is the experiment on real data, where details (e.g., sizes of networks, parameters of algorithms, competitors) are missing. Clarity:The paper is written in a succinct and clear way, but there are a few places that may benefit fromextra explanation: * Lines 185-187: It is easy to see as r gets closer to 1, the Eigenvalues of H become non-negative because H(1) is the usual Laplacian.But the relation between "B's Eigenvalues come in pairs having their product close to \rho(B)" and "for r < r_c, the negative eigenvaluesof H(r_c ) move back into the positive part of the spectrum" is less clear. Can the authors provide a bit more explanation? * Line 189: What is d and what is the notation <>?* Eq. (17): The Jacobian of F in (15) should be a (2M+1) x (2M) matrix, but Eq. (17) seems to be (2M+1) x (2M+1). It looks like removing the first column and replacing the first row of J in (17) with -1's gives the correct Jacobian.* Eigen vectors of Bethe Hessian: Section 2.1 gives connections of the spectrums, but how about the eigenvectors? How do the Eigenvectors of the Bethe Hessian relate to those of the non-backtracking walk operator? How do they reveal community structures? Originality:The proposed approach can be viewed as an elegant reformulation of the non-backtracking walk approach, though the main techinical result facilitating the reformulation, as pointed out by the authors, has been presented in earlier work.Therefore it is not particularly strong in terms of originality.Significance:The proposed approach seems to be a promising addition to the suite of spectral clustering techniques.Avantages over other spectral methods are that the number of negative Eigenvalues provides an estimate of the number of clusters, there is a well-defined way to set the parameter r, making the algorithm tuning-parameter free, and it is guaranteed to detect the communities generated by a Stochastic Block Model down to a theoretical limit.However, whether it should be chosen over other spectral methods on real data is not clear given the experimental results in the paper. The authors stated the performances are comparable to other spectral methods, but did not give details of the methods. For example, how was the number of clusters chosen? Is number of negative Eigenvalues of Bethe Hessian a good estimate of number of communities?Also, there are no timing results to demonstrate the better computational efficiency of the proposed method than the non-backtracking approach. Most of the real networks in the paper are small, which limits the significance of the experimental results.