Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues

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 ψ(G) of a directed graph G to the vertex-capacitated maximum reweighted second eigenvalue λ v * 2 that where ∆ is the maximum degree of G. 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 φ(G) of a directed graph G to the edge-capacitated maximum reweighted second eigenvalue λ e * 2 that λ e * 2 φ(G) λ e * 2 • log