Cheeger constants, structural balance, and spectral clustering analysis for signed graphs

Fatihcan M. Atay and Shiping Liu

Contact the author: Please use for correspondence this email.
Submission date: 13. Nov. 2014
Pages: 32
published in: Discrete mathematics, 343 (2020) 1, art-no. 111616 
DOI number (of the published article): 10.1016/j.disc.2019.111616
Bibtex
MSC-Numbers: 05C50, 05C22, 05C85
Download full preprint: PDF (471 kB)

Abstract:
We introduce a family of multi-way Cheeger-type constants {h_k^σ,k = 1,2,…,N} on a signed graph Γ = (G,σ) such that h_k^σ = 0 if and only if Γ has k balanced connected components. These constants are switching invariant and bring together in a unified viewpoint a number of important graph-theoretical concepts, including the classical Cheeger constant, the non-bipartiteness parameter of Desai and Rao, the bipartiteness ratio of Trevisan, the dual Cheeger constant of Bauer and Jost on unsigned graphs, and the line index of imbalance of Harary (also called the frustration index) on signed graphs.

We then propose a corresponding spectral clustering algorithm for finding k almost-balanced subgraphs, each defining a sparse cut. We find that the proper metric for the clustering algorithm is the metric on a real projective space. Remarkably, this algorithm includes the traditional spectral clustering algorithm on unsigned graphs via spherical metrics as a special case. We verify the algorithm theoretically by proving higher-order signed Cheeger inequalities, and signed improved Cheeger inequalities concerning higher-order spectral gaps.

We also prove estimates of the extremal eigenvalues of signed Laplace matrix in terms of number of signed triangles (3-cycles).