Please note: This PhD seminar will take place online.
Shenghao Yang, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Kimon Fountoulakis
Due to their ability to model complex relations among entities, hypergraphs have received renewed interests in machine learning and applied mathematics. The insurgence of relational data has resulted in hypergraphs of increasing size and complexity that exhibit interesting small-scale and local structure, e.g., small-scale communities and localized node-ranking around a given set of seed nodes. Popular and principled ways to extract the local structure are the local clustering problem and related seed set expansion problem.
In this talk, I will introduce the first hypergraph diffusion method that achieves edge-size-independent Cheeger-type guarantee for the problem of local clustering in hypergraphs, while applying to a rich class of higher-order relations that covers many previously studied special cases. Our method is based on a primal-dual optimization formulation where the primal problem has a natural network flow interpretation, and the dual problem has a cut-based interpretation using the 2-norm penalty on associated cut-costs. We demonstrate the new technique is significantly better than state-of-the-art methods on both synthetic and real-world data for semi-supervised local community detection and node ranking problems.
Based on the paper Local Hyper-Flow Diffusion, K. Fountoulakis, P. Li, S. Yang. NeurIPS 2021