  Recently, hypergraphs have attracted a lot of attention due to their ability
to capture complex relations among entities. The insurgence of hypergraphs has
resulted in data 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
capture the local structure are the local hypergraph clustering problem and
related seed set expansion problem. In this work, we propose the first local
diffusion method that achieves edge-size-independent Cheeger-type guarantee for
the problem of local hypergraph clustering 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 $\ell_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.
