New Parallel and Streaming Algorithms for Directed Densest Subgraph

Finding dense subgraphs is a fundamental problem with applications to community detection, clustering, and data mining. Our work focuses on finding approximate densest subgraphs in directed graphs in computational models for processing massive data. We consider two such models: Massively Parallel Computation (MPC) and semi-streaming. We show how to find a (2 + ε)-approximation in Õ( √ log n) MPC rounds with sublinear memory per machine. This improves the state-of-theart results by Bahmani et al. [BGM14, WAW 2014] andMitrović & Pan [MP24, ICML 2024]. Moreover, we show how to find an O(log n)-approximation in a single pass in semi-streaming. This is in stark contrast to prior work, which implies Ω(n 1/6 ) approximation for a single pass; a better approximation is known only for randomized streams (Mitrović & Pan). This is the first deterministic single-pass semi-streaming algorithm for the densest subgraph problem, both for undirected and directed graphs. Our semi-streaming approach is also an insertion-only dynamic algorithm, attaining the first directed densest subgraph algorithm with O(log 2 n) worst-case update time while using sub-linear memory. We empirically evaluate our approaches in two ways. First, we illustrate that our single-pass semi-streaming algorithm performs much better than the theoretical guarantee. Specifically, its approximation on temporal datasets matches the (2 + ε)-approximation of an O(log n)-pass algorithm by Bahmani et al. [BKV12, VLDB 2012]. Second, we demonstrate that our MPC algorithm requires fewer rounds than prior work. This improves on [BGM14], which uses O(log n) rounds, and on [MP24], which uses O( √ log n) MPC rounds but requires near-linear memory per machine. Additionally, Result 1 matches the state-of-the-art round complexity of Õ( √ log n) for undirected graphs from [GLM19], bridging the gap between the directed and undirected DS problems in MPC.

Result 2 (Theorem 5.1 rephrased). Given an n-vertex graph and ε > 0, there exists a single-pass deterministic semi-streaming algorithm that outputs an O(log n)-approximate directed DS. This is the first single-pass semi-streaming algorithm for the directed DS problem on arbitrary streams.

[MP24] attains a (2 + ε)-approximation but only for randomized streams. [EHW15] attains a (1 + ε)approximation when additional memory, i.e., O(n 1.5 poly log n), is allowed. If we were to extend the ideas of using uniform sampling from prior works, a generalization of the construction in [MP24] shows that it will result in at least a Ω(n 1/6 )-approximation. We also note that this is a deterministic algorithm and can be easily adapted to undirected graphs, leading to the first deterministic single-pass semi-streaming algorithm for the DS problem in both undirected and directed cases.

Result 2 is also an insertion-only dynamic algorithm. Its worst-case update time is O(log n) for undirected and O(log 2 n) for directed graphs. To our knowledge, no previous algorithm maintains an approximate directed DS in semi-streaming. [BHNT15] shows how to maintain a (4+ε)-approximate undirected DS with Õ(1) amortized update time and Õ(n) memory but may have Ω(n) worst-case update time. [SW20] shows how to maintain a (1 + ε)-approximate directed DS with O(log 5 n) worst-case update time but requires linear memory.

Empirical evaluation suggests that, in practice, our semi-streaming algorithm yields an approximation much better than log n. On temporal datasets specifically, it matches the approximation of [BKV12].