Minimizing Localized Ratio Cut Objectives in Hypergraphs -
Minimizing Localized Ratio Cut Objectives in Hypergraphs
Aug 13, 20203 views
Nate Veldt
Hypergraphs are a useful abstraction for modeling multiway relationships in data, and hypergraph clustering is the task of detecting,groups of closely related nodes in such data.,Graph,clustering has,been studied extensively, and there are numerous methods for detecting small, localized clusters without having to explore an entire,input graph. However, there are only a few specialized approaches,for localized clustering in hypergraphs. Here we present a framework for local hypergraph clustering based on minimizing localized,ratio cut objectives. Our framework takes an input set of reference,nodes in a hypergraph and solves a sequence of hypergraph minimum,s,t,cut problems in order to identify a nearby well-connected,cluster of nodes that overlaps substantially with the input set.,Our methods extend graph-based techniques but are significantly,more general and have new output quality guarantees. First, our,methods can minimize new generalized notions of hypergraph,cuts, which depend on specific configurations of nodes within each,hyperedge, rather than just on the number of cut hyperedges. Second, our framework has several attractive theoretical properties in,terms of output cluster quality. Most importantly, our algorithm is,strongly-local, meaning that its runtime depends only on the size,of the input set, and does not need to explore the entire hypergraph,to find good local clusters. We use our methodology to effectively,identify clusters in hypergraphs of real-world data with millions of,nodes, millions of hyperedges, and large average hyperedge size,with runtimes ranging between a few seconds and a few minutes.