HyDRA framework shrinks hypergraphs 80-93% with lossless summarization

Hypergraphs, which model higher-order interactions, are notoriously difficult to manage at scale due to their complexity and size. While summarization techniques exist for simple graphs, lossless summarization for hypergraphs has been an open problem. Enter HyDRA, a new framework from researchers Giulia Preti, Aris Anagnostopoulos, and Francesco Bonchi. HyDRA compresses weighted hypergraphs by grouping nodes into supernodes and hyperedges into superhyperedges, then storing a compact correction table that enables exact reconstruction. The approach draws a conceptual link to co-clustering, allowing it to simultaneously optimize both node and hyperedge groupings to minimize storage cost.

What sets HyDRA apart is its efficiency and practicality. The greedy algorithm is parameter-free, meaning no manual tuning required, and uses an incremental update strategy to avoid costly recomputation of the correction table at each merge step. Experiments show storage reductions of 80% to 93%, depending on hypergraph characteristics. Critically, the summaries remain hypergraphs themselves, so they can be directly queried for approximate answers to connectivity and centrality queries with high accuracy. This makes HyDRA a powerful pre-processing tool for downstream tasks like influence maximization, where speed and scale are paramount.