The Generalized Mean Densest Subgraph Problem
This work addresses the problem of finding dense subgraphs in graph mining for researchers and practitioners, offering a flexible framework to interpolate between existing objectives, but it is incremental as it builds upon and extends known methods like peeling algorithms.
The paper introduces a family of dense subgraph objectives parameterized by p, based on generalized means of degree sequences, which captures standard densest subgraph and maximum k-core as special cases, and shows that for p ≥ 1, it can be minimized in polynomial time via repeated submodular minimization, with a designed peeling algorithm achieving at least 1/2 approximation guarantee converging to 1 as p → ∞, and in practice, it scales to large graphs and provides better approximations than standard peeling.
Finding dense subgraphs of a large graph is a standard problem in graph mining that has been studied extensively both for its theoretical richness and its many practical applications. In this paper we introduce a new family of dense subgraph objectives, parameterized by a single parameter $p$, based on computing generalized means of degree sequences of a subgraph. Our objective captures both the standard densest subgraph problem and the maximum $k$-core as special cases, and provides a way to interpolate between and extrapolate beyond these two objectives when searching for other notions of dense subgraphs. In terms of algorithmic contributions, we first show that our objective can be minimized in polynomial time for all $p \geq 1$ using repeated submodular minimization. A major contribution of our work is analyzing the performance of different types of peeling algorithms for dense subgraphs both in theory and practice. We prove that the standard peeling algorithm can perform arbitrarily poorly on our generalized objective, but we then design a more sophisticated peeling method which for $p \geq 1$ has an approximation guarantee that is always at least $1/2$ and converges to 1 as $p \rightarrow \infty$. In practice, we show that this algorithm obtains extremely good approximations to the optimal solution, scales to large graphs, and highlights a range of different meaningful notions of density on graphs coming from numerous domains. Furthermore, it is typically able to approximate the densest subgraph problem better than the standard peeling algorithm, by better accounting for how the removal of one node affects other nodes in its neighborhood.