# Faster Algorithms for Generalized Mean Densest Subgraph Problem

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 29 references that are in the map.
- First posted on arXiv 17 Oct 2023.

## Builds on (most cited first, 3 of 3)

- [Explainable Classification of Brain Networks via Contrast Subgraphs](https://mlsanity.com/paper/2006.05176/) (2020)
- [Peeling Bipartite Networks for Dense Subgraph Discovery](https://mlsanity.com/paper/1611.02756/) (2016)
- [The Generalized Mean Densest Subgraph Problem](https://mlsanity.com/paper/2106.00909/) (2021)

## Abstract (arXiv)

The densest subgraph of a large graph usually refers to some subgraph with the highest average degree, which has been extended to the family of p-means dense subgraph objectives by~citetveldt2021generalized. The p-mean densest subgraph problem seeks a subgraph with the highest average p-th-power degree, whereas the standard densest subgraph problem seeks a subgraph with a simple highest average degree. It was shown that the standard peeling algorithm can perform arbitrarily poorly on generalized objective when p>1 but uncertain when 0<p<1. In this paper, we are the first to show that a standard peeling algorithm can still yield 21/p-approximation for the case 0<p < 1. (Veldt 2021) proposed a new generalized peeling algorithm (GENPEEL), which for p ≥ 1 has an approximation guarantee ratio (p+1)1/p, and time complexity O(mn), where m and n denote the number of edges and nodes in graph respectively. In terms of algorithmic contributions, we propose a new and faster generalized peeling algorithm (called GENPEEL++ in this paper), which for p ∈ [1, +∞) has an approximation guarantee ratio (2(p+1))1/p, and time complexity O(m(log n)), where m and n denote the number of edges and nodes in graph, respectively. This approximation ratio converges to 1 as p rightarrow ∞.