Cut-matching Games for Generalized Hypergraph Ratio Cuts

Many social networks and web-based datasets are characterized by multiway interactions (e.g., groups of co-purchased online retail products or group conversations in Q&A forums) and hypergraph clustering is a fundamental primitive for analyzing these types of interactions. We present an O(log n)-approximation algorithm for a broad class of hypergraph ratio cut objectives. This includes objectives involving generalized hypergraph cut functions, which allow a user to penalize cut hyperedges differently depending on the number of nodes in each cluster. Our method generalizes the cut-matching framework for graph ratio cuts, and relies only on solving maximum s-t flow problems in a special reduced graph. It is significantly faster than existing hypergraph ratio cut algorithms, while also solving a more general problem. In numerical experiments on various web-based hypergraphs, we show that it quickly finds ratio cut solutions within a small factor of optimality.

Paper

Similar papers

© 2026 NYSGPT2525 LLC