PhD Seminar • Algorithms and Complexity • Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues

Please note: This PhD seminar will take palce in M3 4206 and online.

Kam Chuen Tung, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Lap Chi Lau

We derive Cheeger inequalities for directed graphs and hypergraphs using the reweighted eigenvalue approach that was recently developed for vertex expansion in undirected graphs. 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 of a directed graph to the vertex-capacitated maximum reweighted second eigenvalue. 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 of a directed graph to the edge-capacitated maximum reweighted second eigenvalue. 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. These are supporting results that this provides a unifying approach to lift the spectral theory for undirected graphs to more general settings.

This work is joint with Lap Chi Lau and Robert Wang.

Paper on arXiv: Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues

To attend this PhD seminar in person, please go to M3 4206. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/93137947070.