Spectral Graph Partitioning

Spectral graph partitioning is a method of partitioning a graph based on eigenvalues and eigenvectors of an associated matrix. In the classical construction, the matrix is the Laplacian matrix. The signs or a threshold of the Fiedler vector give a bipartition, while several eigenvectors can embed the vertices in a low-dimensional space that is subsequently partitioned using cluster analysis.

Other spectral methods use the adjacency matrix, nonbacktracking matrix, or Bethe Hessian. The latter two are particularly useful for sparse random graphs, where informative eigenvectors of the adjacency matrix or Laplacian matrix can be obscured by fluctuations in vertex degrees (Saade et al. 2014). Spectral graph partitioning is commonly used for community detection, although a partitioning problem may instead prescribe the number or sizes of the parts and optimize a fixed cut objective.