Fast and Simple Densest Subgraph with Predictions

We study the densest subgraph problem and its variants through the lens of learning-augmented algorithms. We show that, given a reasonably accurate predictor that estimates whether a node belongs to the densest subgraph (e.g., a machine-learning classifier), one can design simple and practical linear-time algorithms that achieve a $(1-ε)$-approximation to the densest subgraph. Our approach also extends to the NP-Hard densest at-most-$k$ subgraph problem and to the directed densest subgraph variant. Finally, we present experimental results demonstrating the effectiveness of our methods.