# Flowless: Extracting Densest Subgraphs Without Flow Computations

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2019.

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

- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)
- [Fast and Simple Densest Subgraph with Predictions](https://mlsanity.com/paper/2505.12600/) (2025)

## Abstract (arXiv)

We propose a simple and computationally efficient method for dense subgraph discovery, which is a classic problem both in theory and in practice. It is well known that dense subgraphs can have strong correlation with structures of interest in real-world networks across various domains ranging from social networks to biological systems [Gionis and Tsourakakis `15]. For the densest subgraph problem, Charikar's greedy algorithm [Asashiro `00, Charikar `00] is very simple, and can typically find result of quality much better than the provable factor 2-approximation, which makes it very popular in practice. However, it is also known to give suboptimal output in many real-world examples. On the other hand, finding the exact optimal solution requires the computation of maximum flow. Despite the existence of highly optimized maximum flow solvers, such computation still incurs prohibitive computational costs for the massive graphs arising in modern data science applications. We devise an iterative algorithm which naturally generalizes the greedy algorithm of Charikar. Our algorithm draws insights from the iterative approaches from convex optimization, and also exploits the dual interpretation of the densest subgraph problem. We have empirical evidence that our algorithm is much more robust against the structural heterogeneities in real-world datasets, and converges to the optimal subgraph density even when the simple greedy algorithm fails. On the other hand, in instances where Charikar's algorithm performs well, our algorithm is able to quickly verify its optimality. Furthermore, we demonstrate that our method is significantly faster than the maximum flow based exact optimal algorithm. We conduct experiments on datasets from broad domains, and our algorithm achieves ~145× speedup on average to find subgraphs whose density is at least 90% of the optimal value.