# Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues

arXiv: https://arxiv.org/abs/2211.09776 · HTML: https://mlsanity.com/paper/2211.09776/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 48 references that are in the map.
- First posted on arXiv 17 Nov 2022.

## Builds on (most cited first, 15 of 15)

- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Hermitian matrices for clustering directed graphs: insights and applications](https://mlsanity.com/paper/1908.02096/) (2019)
- [Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering](https://mlsanity.com/paper/1803.03833/) (2018)
- [Higher-Order Spectral Clustering of Directed Graphs](https://mlsanity.com/paper/2011.05080/) (2020)
- [Cheeger Inequalities for Submodular Transformations](https://mlsanity.com/paper/1708.08781/) (2017)
- [Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms](https://mlsanity.com/paper/1408.2425/) (2014)
- [Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs](https://mlsanity.com/paper/1611.00755/) (2016)
- [Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap](https://mlsanity.com/paper/1301.5584/) (2013)
- [Spectral Hypergraph Sparsifiers of Nearly Linear Size](https://mlsanity.com/paper/2106.02353/) (2021)
- [Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More](https://mlsanity.com/paper/1608.03270/) (2016)
- [Near-linear Size Hypergraph Cut Sparsifiers](https://mlsanity.com/paper/2009.04992/) (2020)
- [Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues](https://mlsanity.com/paper/2203.06168/) (2022)
- [Hermitian Laplacians and a Cheeger inequality for the Max-2-Lin problem](https://mlsanity.com/paper/1811.10909/) (2018)
- [Routing under Balance](https://mlsanity.com/paper/1603.09009/) (2016)
- [Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain](https://mlsanity.com/paper/2203.03858/) (2022)

## Built on by (most cited first, 3 of 3)

- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues](https://mlsanity.com/paper/2306.09128/) (2023)
- [Self-Attention as Transport: Limits of Symmetric Spectral Diagnostics](https://mlsanity.com/paper/2605.04893/) (2026)

## Abstract (arXiv)

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 vecpsi(G) of a directed graph G to the vertex-capacitated maximum reweighted second eigenvalue vecλ2v*: [ vecλ2v* lesssim vecpsi(G) lesssim √vecλ2v* · log (Delta/vecλ2v*). ] 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λ2e*: [ vecλ2e* lesssim vecφ(G) lesssim √vecλ2e* · log (1/vecλ2e*). ] 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.