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

Abstract

We introduce a family of multi-way Cheeger-type constants $\{h_k^{\sigma },k=1,2,\dots ,n\}$ on a signed graph $\Gamma =(G,\sigma )$ such that $h_k^{\sigma }=0$ if and only if $\Gamma$ 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, those measures of bipartiteness introduced by Desai-Rao, Trevisan, Bauer-Jost, respectively, on unsigned graphs,, and the frustration index (originally called the line index of balance by Harary) on signed graphs. We further unify the (higher-order or improved) Cheeger and dual Cheeger inequalities for unsigned graphs as well as the underlying algorithmic proof techniques by establishing their corresponding versions on signed graphs. In particular, we develop a spectral clustering method for finding $k$ almost-balanced subgraphs, each defining a sparse cut. The proper metric for such a clustering is the metric on a real projective space. We also prove estimates of the extremal eigenvalues of signed Laplace matrix in terms of number of signed triangles ($3$-cycles).

We add more details for the proof of Lemma 6.4, Theorem 6.2, Theorem 6.3. We also explain more details about the control of those various absolute constant appearing in our estimates

References in corpus (5)

• Multi-way dual Cheeger constants and spectral bounds of graphs
• Applications of Structural Balance in Signed Social Networks
• Ramanujan Graphs and the Solution of the Kadison-Singer Problem
• Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
• New Bounds for the Laplacian Spectral Radius of a Signed Graph

Cited by in corpus (6)

• Searching for polarization in signed graphs: a local spectral approach
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Spreading and Structural Balance on Signed Networks
• Signatures, lifts, and eigenvalues of graphs
• An isoperimetric constant for signed graphs
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy