PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral Clustering of Graphs with the Bethe Hessian

Alaa Saade, Florent Krzakala, Lenka Zdeborová

arXiv:1406.1880v2cond-mat.dis-nncs.SIphysics.soc-phstat.ML

TL;DR

Spectral clustering needs tractable methods that can detect communities optimally in the stochastic block model. This paper proposes the symmetric Bethe Hessian and shows that its negative eigenvalues recover community structure, matching the relevant performance of non-backtracking methods while extending naturally to weighted graphs.

  • Problem

    The paper addresses the need for a tractable, non-parametric clustering method that performs optimally in the stochastic block model.

  • Method

    The paper uses the Bethe Hessian, a symmetric real matrix whose negative eigenvectors provide the clustering directions.

  • Results

    The Bethe Hessian detects communities at the stochastic-block-model limit and performs at least as well as non-backtracking clustering on the reported real networks.

  • Takeaways & Limitations

    The approach combines non-backtracking-level clustering performance with the computational and scalability advantages of symmetric real matrices, including for weighted similarities.

  • Takeaways & Limitations

    The paper presents negative Bethe Hessian eigenvalues at selected regularization parameters as an approximate solution strategy for some otherwise NP-hard maximization problems.

Abstract

from arXiv · show

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.

I. CLUSTERING BASED ON THE BETHE HESSIAN MATRIX

The Bethe Hessian provides a symmetric spectral-clustering method whose negative eigenvectors identify assortative and disassortative communities. Its regularization links it to non-backtracking clustering, while weighted generalizations preserve the approach’s applicability.

  • I. CLUSTERING BASED ON THE BETHE HESSIAN MATRIX: The algorithm clusters using eigenvectors associated with negative eigenvalues of H(rc) and H(−rc).Negative eigenvalues of H(rc) reveal assortative structure, whereas those of H(−rc) reveal disassortative structure.
  • I. CLUSTERING BASED ON THE BETHE HESSIAN MATRIX: At r=±√c, informative eigenvalues are negative while the non-informative spectral bulk remains positive.This separation makes the relevant eigenvectors identifiable in stochastic-block-model networks.
  • I. CLUSTERING BASED ON THE BETHE HESSIAN MATRIX: The number of negative eigenvalues equals the number of hidden clusters, eliminating the need to know the community count beforehand.This provides a direct selection rule for relevant eigenvectors.
  • I. CLUSTERING BASED ON THE BETHE HESSIAN MATRIX: The Bethe Hessian spectrum is directly linked to the non-backtracking spectrum, and its informative eigenvalues correspond to negative eigenvalues of H(rc) and H(−rc).The regularizer is chosen from the graph; for the stochastic block model, rc=√c.
  • I. CLUSTERING BASED ON THE BETHE HESSIAN MATRIX: The construction extends to weighted graphs through a generalized Bethe Hessian that retains the connection to weighted non-backtracking operators.When all weights equal one, the weighted form reduces to the unweighted operator up to a positive factor.

II. DERIVATION AND RELATION TO PREVIOUS WORKS

The paper connects the Bethe Hessian to both non-backtracking spectral clustering and an Ising spin-glass model, using these relationships to analyze its properties.

  • II. DERIVATION AND RELATION TO PREVIOUS WORKS: The Bethe Hessian approach is connected to spectral clustering with the non-backtracking matrix.The paper treats this connection as one route for understanding the operator’s behavior.
  • II. DERIVATION AND RELATION TO PREVIOUS WORKS: The paper also connects the Bethe Hessian to an Ising spin-glass model.This provides a statistical-physics perspective on the operator.
  • II. DERIVATION AND RELATION TO PREVIOUS WORKS: The section uses these connections to discuss the Bethe Hessian’s properties.The two perspectives organize the subsequent analysis.

A. Relation with the non-backtracking matrix

The Bethe Hessian translates informative non-backtracking eigenvalues into negative eigenvalues of symmetric matrices. This correspondence explains how regularization separates community structure from the spectral bulk.

  • A. Relation with the non-backtracking matrix: For stochastic-block-model graphs, non-backtracking spectra contain an uninformative bulk and real informative eigenvalues outside its radius ρ(B).Assortative communities produce real positive eigenvalues, while disassortative communities produce real negative eigenvalues.
  • A. Relation with the non-backtracking matrix: The Ihara-Bass formula links non-backtracking eigenvalues to zeros of the Bethe Hessian.A real eigenvalue of the non-backtracking matrix corresponds to a regularizer value at which the Bethe Hessian has a zero eigenvalue.
  • A. Relation with the non-backtracking matrix: As r decreases from a sufficiently large positive value, each crossing of zero introduces a negative Bethe Hessian eigenvalue.The analogous process occurs when increasing r from a large negative value.
  • A. Relation with the non-backtracking matrix: Choosing r below rc is undesirable because negative eigenvalues move back into the positive spectrum.The recommended choice places the relevant non-backtracking eigenvalues outside the bulk radius.
  • A. Relation with the non-backtracking matrix: The spectral radius ρ(B) can be estimated without constructing the non-backtracking matrix itself.The paper uses degree moments for an initial estimate and a quadratic eigenproblem for refinement; with the selected regularizer, informative eigenvalues correspond to negative eigenvalues of H(rc) and H(−rc).

B. Hessian of the Bethe free energy

The Bethe Hessian arises as the Hessian of a Bethe-approximated Ising model around its paramagnetic point. Its negative eigenvalues mark transitions toward identifiable community structure while the non-informative bulk remains positive.

  • B. Hessian of the Bethe free energy: The paper defines a pairwise Ising model on the graph using binary variables x_i∈{−1,+1}.The regularizer r controls interaction strength, with larger |r| corresponding to weaker interactions.
  • B. Hessian of the Bethe free energy: The Bethe approximation replaces Ising means and pairwise moments with parameters that minimize the Bethe free energy.Although this framework can derive belief propagation, the paper focuses on a spectral algorithm.
  • B. Hessian of the Bethe free energy: At high r, the Bethe free energy has a paramagnetic point with zero node means and unit pairwise moments.This point remains a stationarity point as r varies.
  • B. Hessian of the Bethe free energy: The Bethe Hessian is obtained by studying the Hessian of the Bethe free energy around the paramagnetic point.The relevant matrix is the block governing perturbations in the node means.
  • B. Hessian of the Bethe free energy: Each negative Hessian eigenvalue corresponds to a phase transition where a cluster or set of clusters becomes identifiable.The associated eigenvector gives the direction toward the cluster labeling.
  • B. Hessian of the Bethe free energy: At r=±√c, all transitions toward hidden structure have occurred while the non-informative bulk remains positive.This produces the spectral separation used for clustering in the stochastic block model.

III. THE SPECTRUM OF THE BETHE HESSIAN

The section analyzes the Bethe Hessian spectrum using belief-propagation equations on tree-like graphs, showing that its uninformative bulk reaches zero at the regularizer choice r_c = √ρ(B).

  • Spectral-density analysis: The spectral density of the Bethe Hessian is computed analytically on tree-like graphs to justify the regularizer and characterize the uninformative spectrum.The approach is asymptotically exact for random graphs such as stochastic block models in the locally tree-like limit.
  • Spectral-density analysis: The spectral-density calculation converts the problem into a graphical-model marginalization followed by belief-propagation equations for cavity variables.The variables Δ_i→j satisfy a linearly stable belief-propagation recursion.
  • Stability analysis: At λ = 0, Δ_i→j = 1/r^2 is a real solution, and the Jacobian analysis gives spectral radius ρ(B)/r^2.This quantity is strictly below one when r exceeds √ρ(B), ensuring local stability.
  • Stability analysis: For r > √ρ(B), a real stable solution exists around λ = 0, so the spectral density vanishes in an open neighborhood of zero.Continuity then shows that the bulk reaches zero at r_c = √ρ(B).

A. Synthetic networks

On synthetic stochastic block-model graphs, the Bethe Hessian systematically outperforms the non-backtracking operator and approaches belief propagation, while requiring less prior information.

  • Evaluation: The experiments evaluate standard spectral methods and belief propagation using overlap with the true labeling, maximized over permutations of community labels.The graphs are generated by the stochastic block model, and belief propagation is treated as asymptotically optimal under its stated assumptions.
  • Results: The Bethe Hessian systematically outperforms the non-backtracking operator and performs almost as well as belief propagation with oracle parameters.The comparison uses belief propagation supplied with the number of communities, their sizes, and the interaction matrix.
  • Results: The Bethe Hessian can infer the number of communities by counting negative eigenvalues and does not require the interaction matrix.This contrasts with the oracle-parameter setup used for belief propagation.

B. Real networks

On real benchmark networks, the Bethe Hessian remains useful beyond the stochastic block model, matching or exceeding non-backtracking performance and identifying relevant eigenvalues clearly.

  • Benchmark results: The Bethe Hessian systematically equals or outperforms the non-backtracking operator in benchmark overlap comparisons.The table uses signs of the second eigenvector for two communities and k-means for networks with three or more communities.
  • Benchmark results: The Bethe Hessian produces large correlations with ground truth on several real benchmark networks.Its performance is at least equal to, and sometimes better than, that of the non-backtracking operator.
  • Method scope: In all benchmark cases, the considered eigenvalues lie in the negative spectral region and are clearly identifiable.This supports selecting the relevant eigenvectors in the real-network experiments.
  • Method scope: Counting negative eigenvalues estimates the number of clusters, and the approach also works for disassortative networks such as word adjacency networks.The method is therefore applied beyond assortative community structure.

V. CONCLUSION AND PERSPECTIVES

The paper presents Bethe-Hessian spectral clustering as a tractable, non-parametric approach combining sparse symmetric-matrix advantages with non-backtracking performance. It also identifies extensions to real-valued similarities and broader objective functions as future directions.

  • The Bethe Hessian combines standard sparse symmetric real-matrix advantages with the performance of non-backtracking or oracle-parameter belief-propagation methods.
  • The approach can be generalized to spectral clustering with real-valued similarities without sacrificing scalability relative to the non-backtracking operator.
  • Generalizing the graphical-model cost function to objectives such as modularity could make Bethe-Hessian negative eigenvalues an approximate relaxation for some known NP-hard problems.
Loading 1406.1880v2…