Multi-way dual Cheeger constants and spectral bounds of graphs

Abstract

We introduce a set of multi-way dual Cheeger constants and prove universal higher-order dual Cheeger inequalities for eigenvalues of normalized Laplace operators on weighted finite graphs. Our proof proposes a new spectral clustering phenomenon deduced from metrics on real projective spaces. We further extend those results to a general reversible Markov operator and find applications in characterizing its essential spectrum.

30 pages, 1 figure, revised; Theorem 6.4 added. Comments are welcome

References in corpus (2)

• Eigenvalue ratios of nonnegatively curved graphs
• Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap

Cited by in corpus (11)

• Eigenvalue ratios of nonnegatively curved graphs
• Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians
• Spectral distances on graphs
• Clustering Signed Networks with the Geometric Mean of Laplacians
• Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
• Curvature and higher order Buser inequalities for the graph connection Laplacian
• An optimal dimension-free upper bound for eigenvalue ratios
• Cheeger estimates of Dirichlet-to-Neumann operators on infinite subgraphs of graphs
• Bipartite Communities
• Sharp Bounds on Eigenvalues via Spectral Embedding Based on Signless Laplacians
• Bipartite noisy hypercubes have large higher-order Cheeger separation