# Fast and Simple Densest Subgraph with Predictions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 19 May 2025.

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

- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Learning-Augmented Streaming Algorithms for Approximating MAX-CUT](https://mlsanity.com/paper/2412.09773/) (2024)
- [k-center Clustering under Perturbation Resilience](https://mlsanity.com/paper/1505.03924/) (2015)
- [Densest Subgraph in Dynamic Graph Streams](https://mlsanity.com/paper/1506.04417/) (2015)
- [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)
- [Faster Global Minimum Cut with Predictions](https://mlsanity.com/paper/2503.05004/) (2025)
- [Flowless: Extracting Densest Subgraphs Without Flow Computations](https://mlsanity.com/paper/1910.07087/) (2019)
- [Applications of Uniform Sampling: Densest Subgraph and Beyond](https://mlsanity.com/paper/1506.04505/) (2015)
- [Distributed Dense Subgraph Detection and Low Outdegree Orientation](https://mlsanity.com/paper/1907.12443/) (2019)
- [Fast and Accurate Triangle Counting in Graph Streams Using Predictions](https://mlsanity.com/paper/2409.15205/) (2024)
- [Bilu-Linial stability, certified algorithms and the Independent Set problem](https://mlsanity.com/paper/1810.08414/) (2018)

## Abstract (arXiv)

We study the densest subgraph problem and its NP-hard densest at-most-k subgraph variant through the lens of learning-augmented algorithms. We show that, given a reasonably accurate predictor that estimates whether a node belongs to the solution (e.g., a machine learning classifier), one can design simple linear-time algorithms that achieve a (1-ε)approximation. Finally, we present experimental results demonstrating the effectiveness of our methods for the densest at-most-k subgraph problem on real-world graphs.