# A New Dynamic Algorithm for Densest Subhypergraphs

arXiv: https://arxiv.org/abs/2204.08106 · HTML: https://mlsanity.com/paper/2204.08106/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2022.

## Built on by (most cited first, 2 of 2)

- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Hypergraph Node Representation Learning with One-Stage Message Passing](https://mlsanity.com/paper/2312.00336/) (2023)

## Abstract (arXiv)

Computing a dense subgraph is a fundamental problem in graph mining, with a diverse set of applications ranging from electronic commerce to community detection in social networks. In many of these applications, the underlying context is better modelled as a weighted hypergraph that keeps evolving with time. This motivates the problem of maintaining the densest subhypergraph of a weighted hypergraph in a em dynamic setting, where the input keeps changing via a sequence of updates (hyperedge insertions/deletions). Previously, the only known algorithm for this problem was due to Hu et al. [HWC17]. This algorithm worked only on unweighted hypergraphs, and had an approximation ratio of (1+ε)r2 and an update time of O(poly (r, log n)), where r denotes the maximum rank of the input across all the updates. We obtain a new algorithm for this problem, which works even when the input hypergraph is weighted. Our algorithm has a significantly improved (near-optimal) approximation ratio of (1+ε) that is independent of r, and a similar update time of O(poly (r, log n)). It is the first (1+ε)-approximation algorithm even for the special case of weighted simple graphs. To complement our theoretical analysis, we perform experiments with our dynamic algorithm on large-scale, real-world data-sets. Our algorithm significantly outperforms the state of the art [HWC17] both in terms of accuracy and efficiency.