Flowless: Extracting Densest Subgraphs Without Flow Computations

We propose a simple and computationally efficient method for dense subgraph discovery in graph-structured data, 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 such as social networks, communication systems, financial markets, and biological systems [16] . Consequently, this problem arises broadly in modern data science applications, and it is of great interest to design algorithms with practical appeal. For the densest subgraph problem, which asks to find a subgraph with maximum average degree, Charikar's greedy algorithm [3, 8] is guaranteed to find a 2-approximate optimal solution. Charikar's algorithm 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 [17, 14, 22] . 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 a simple iterative algorithm which naturally generalizes the greedy algorithm of Charikar. Moreover, although our algorithm is fully combinatorial, it 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 real-world 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.