Accelerated Coordinate Descent for Directed Densest Subgraph Discovery

Given a directed graph G, the directed densest subgraph (DDS) problem refers to finding a subgraph from G, whose density is the highest among all subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fake follower detection and community mining. However, existing DDS solutions often provide weaker theoretical guarantees. To tackle these issues, we present a theoretically efficient (1+ε) approximate DDS discovery algorithm in this paper. Specifically, we first introduce a novel LP formulation for the DDS problem and then propose an efficient approximation algorithm based on the accelerated random coordinate descent method (ACDM) to solve it efficiently. We theoretically prove that our algorithm requires fewer iterations to achieve the same solution accuracy compared to state-of-the-art approximation DDS algorithms. We have performed an extensive empirical evaluation of our approaches on 15 real large datasets. The results show that our proposed algorithms are up to 1000× faster than the current state-of-the-art.