# A Survey on the Densest Subgraph Problem and Its Variants

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 63 of its 244 references that are in the map.
- First posted on arXiv 25 Mar 2023.

## Builds on (most cited first, 30 of 63)

- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Clustering and Community Detection in Directed Networks: A Survey](https://mlsanity.com/paper/1308.0971/) (2013)
- [CLIPPER: A Graph-Theoretic Framework for Robust Data Association](https://mlsanity.com/paper/2011.10202/) (2020)
- [Explainable Classification of Brain Networks via Contrast Subgraphs](https://mlsanity.com/paper/2006.05176/) (2020)
- [Recent Advances in Graph Partitioning](https://mlsanity.com/paper/1311.3144/) (2013)
- [AntiBenford Subgraphs: Unsupervised Anomaly Detection in Financial Networks](https://mlsanity.com/paper/2205.13426/) (2022)
- [Hypergraph Cuts with General Splitting Functions](https://mlsanity.com/paper/2001.02817/) (2020)
- [DenseAlert: Incremental Dense-Subtensor Detection in Tensor Streams](https://mlsanity.com/paper/1706.03374/) (2017)
- [Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphs](https://mlsanity.com/paper/2203.14573/) (2022)
- [The Densest k-Subhypergraph Problem](https://mlsanity.com/paper/1605.04284/) (2016)
- [Differentially Private Densest Subgraph Detection](https://mlsanity.com/paper/2105.13287/) (2021)
- [Densest Subgraph in Dynamic Graph Streams](https://mlsanity.com/paper/1506.04417/) (2015)
- [Peeling Bipartite Networks for Dense Subgraph Discovery](https://mlsanity.com/paper/1611.02756/) (2016)
- [No Place to Hide: Catching Fraudulent Entities in Tensors](https://mlsanity.com/paper/1810.06230/) (2018)
- [Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming](https://mlsanity.com/paper/2002.08841/) (2020)
- [Differentially Private Densest Subgraph](https://mlsanity.com/paper/2106.00508/) (2021)
- [FirmCore Decomposition of Multilayer Networks](https://mlsanity.com/paper/2208.11200/) (2022)
- [Spade: A Real-Time Fraud Detection Framework on Evolving Graphs (Complete Version)](https://mlsanity.com/paper/2211.06977/) (2022)
- [Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs](https://mlsanity.com/paper/2211.10887/) (2022)
- [Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams](https://mlsanity.com/paper/1504.02268/) (2015)
- [Near-Optimal Fully Dynamic Densest Subgraph](https://mlsanity.com/paper/1907.03037/) (2019)
- [EnsemFDet: An Ensemble Approach to Fraud Detection based on Bipartite Graph](https://mlsanity.com/paper/1912.11113/) (2019)
- [Statistical and computational thresholds for the planted k-densest sub-hypergraph problem](https://mlsanity.com/paper/2011.11500/) (2020)
- [The Generalized Mean Densest Subgraph Problem](https://mlsanity.com/paper/2106.00909/) (2021)
- [Mining Density Contrast Subgraphs](https://mlsanity.com/paper/1802.06775/) (2018)
- [Finding events in temporal networks: Segmentation meets densest-subgraph discovery](https://mlsanity.com/paper/1808.09317/) (2018)
- [Core Decomposition in Multilayer Networks: Theory, Algorithms, and Applications](https://mlsanity.com/paper/1812.08712/) (2018)
- [Efficient Algorithms for Densest Subgraph Discovery](https://mlsanity.com/paper/1906.00341/) (2019)
- [Online Dense Subgraph Discovery via Blurred-Graph Feedback](https://mlsanity.com/paper/2006.13642/) (2020)
- [Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions](https://mlsanity.com/paper/1411.3312/) (2014)

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

- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Bandits with Abstention under Expert Advice](https://mlsanity.com/paper/2402.14585/) (2024)
- [Jaccard-constrained dense subgraph discovery](https://mlsanity.com/paper/2308.15936/) (2023)
- [Differentially Private and Scalable Estimation of the Network Principal Component](https://mlsanity.com/paper/2505.03858/) (2025)
- [Fast and Simple Densest Subgraph with Predictions](https://mlsanity.com/paper/2505.12600/) (2025)
- [Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming](https://mlsanity.com/paper/2601.03946/) (2026)
- [The CriticalSet problem: Identifying Critical Contributors in Bipartite Dependency Networks](https://mlsanity.com/paper/2604.21537/) (2026)

## Abstract (arXiv)

The Densest Subgraph Problem requires to find, in a given graph, a subset of vertices whose induced subgraph maximizes a measure of density. The problem has received a great deal of attention in the algorithmic literature since the early 1970s, with many variants proposed and many applications built on top of this basic definition. Recent years have witnessed a revival of research interest in this problem with several important contributions, including some groundbreaking results, published in 2022 and 2023. This survey provides a deep overview of the fundamental results and an exhaustive coverage of the many variants proposed in the literature, with a special attention to the most recent results. The survey also presents a comprehensive overview of applications and discusses some interesting open problems for this evergreen research topic.