Augmented Sparsifiers for Generalized Hypergraph Cuts
Nate Veldt, Austin R. Benson, Jon Kleinberg; 24(207):1−50, 2023.
Abstract
In this paper, we discuss the use of augmented sparsifiers for generalized hypergraph cuts. Hypergraph generalizations have been introduced to better model data and systems with multiway relationships. These generalizations involve a hypergraph cut function that assigns a penalty to each way of separating the nodes in a hyperedge. By reducing the generalized hypergraph cut problem to a directed graph cut problem, we can solve it more efficiently. However, the resulting graph may be very dense. To address this issue, we propose a framework for sparsifying hypergraph-to-graph reductions. This framework allows us to approximate the hypergraph cut function using a cut on a directed graph with fewer edges. We show that we can reduce any hyperedge with at most O(ε^(-1)|e|log|e|) edges, where ε > 0, and approximate the clique expansion with O(|e|ε^(-1/2)loglog(1/ε)) edges. Our framework leads to improved results for solving cut problems in various applications, including co-occurrence graphs, decomposable submodular function minimization problems, and localized hypergraph clustering problems.
[abs]
[code]