Hubert Chan: Revisiting Diffusion Process for Hypergraph Laplacian

Abstract: Hypergraph Laplacian has been defined via a diffusion process [Louis STOC 2015]. The spectral properties of the Laplacian is used to achieve a variant of the Cheeger's inequality for hyperedge expansion and higher-order Cheeger-like inequalities for multi-way expansion.
In this talk, we take a closer look at this diffusion process, in which each hyperedge tries to transfer measure from vertices having maximum measure to those having minimum. In order for the diffusion process to be well-defined, we see that the hyperedges must be coordinated to essentially solve a densest subset problem. Consequently, we can recover the basic Cheeger's inequality, but higher-order spectral properties of the Laplacian do not hold in hypergraphs in general.

This is joint work with Anand Louis, Zhihao Gavin Tang and Chenzi Zhang.

PRACTICALITIES
The presentation starts at 13:15 pm and ends slightly after 2 pm.