Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues
This work provides a new spectral theory for directed graphs and an alternative for hypergraphs, addressing a foundational problem in theoretical computer science and graph theory, though it builds incrementally on existing methods for undirected graphs.
The authors tackled the problem of extending spectral graph theory to directed graphs and hypergraphs by deriving Cheeger inequalities using a reweighted eigenvalue approach, resulting in new inequalities that relate vertex expansion and edge conductance to reweighted eigenvalues, with bounds involving logarithmic factors.
We derive Cheeger inequalities for directed graphs and hypergraphs using the reweighted eigenvalue approach that was recently developed for vertex expansion in undirected graphs [OZ22,KLT22,JPV22]. The goal is to develop a new spectral theory for directed graphs and an alternative spectral theory for hypergraphs. The first main result is a Cheeger inequality relating the vertex expansion $\vecψ(G)$ of a directed graph $G$ to the vertex-capacitated maximum reweighted second eigenvalue $\vecλ_2^{v*}$: \[ \vecλ_2^{v*} \lesssim \vecψ(G) \lesssim \sqrt{\vecλ_2^{v*} \cdot \log (Δ/\vecλ_2^{v*})}. \] This provides a combinatorial characterization of the fastest mixing time of a directed graph by vertex expansion, and builds a new connection between reweighted eigenvalued, vertex expansion, and fastest mixing time for directed graphs. The second main result is a stronger Cheeger inequality relating the edge conductance $\vecφ(G)$ of a directed graph $G$ to the edge-capacitated maximum reweighted second eigenvalue $\vecλ_2^{e*}$: \[ \vecλ_2^{e*} \lesssim \vecφ(G) \lesssim \sqrt{\vecλ_2^{e*} \cdot \log (1/\vecλ_2^{e*})}. \] This provides a certificate for a directed graph to be an expander and a spectral algorithm to find a sparse cut in a directed graph, playing a similar role as Cheeger's inequality in certifying graph expansion and in the spectral partitioning algorithm for undirected graphs. We also use this reweighted eigenvalue approach to derive the improved Cheeger inequality for directed graphs, and furthermore to derive several Cheeger inequalities for hypergraphs that match and improve the existing results in [Lou15,CLTZ18]. These are supporting results that this provides a unifying approach to lift the spectral theory for undirected graphs to more general settings.