Author

Lap Chi Lau, Kam Chuen Tung, Robert Wang

Category

cs.DS

Date Published

2022/11/17

Date Retrieved

2022/11/20

Date Updated

2022/11/20

Description

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{\psi}(G)$ of a directed graph $G$ to the vertex-capacitated maximum
reweighted second eigenvalue $\vec{\lambda}_2^{v*}$: \[ \vec{\lambda}_2^{v*}
\lesssim \vec{\psi}(G) \lesssim \sqrt{\vec{\lambda}_2^{v*} \cdot \log
(\Delta/\vec{\lambda}_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{\phi}(G)$ of a directed graph $G$ to the edge-capacitated
maximum reweighted second eigenvalue $\vec{\lambda}_2^{e*}$: \[
\vec{\lambda}_2^{e*} \lesssim \vec{\phi}(G) \lesssim \sqrt{\vec{\lambda}_2^{e*}
\cdot \log (1/\vec{\lambda}_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.

Posts

6

Readers

0

Score

1

Tweeters

4

URL

https://arxiv.org/abs/2211.09776

TOP