you're reading...

SACT Seminar

Time: 1:00 pm Tuesday, 15th August 2017.

Location: SIT 459

Speaker: Hubert Chan, The University of Hong Kong

Title: Revisiting Diffusion Process for Hypergraph Laplacian


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.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: