New Parallel and Streaming Algorithms for Directed Densest Subgraph
Authors: Slobodan Mitrović
Theodore Pan
Mahdi Qaempanah
Mohammad Amin Raeisi
Venue: NeurIPS 2025 poster ()
Keywords: semi-streaming
massively parallel computation
directed densest subgraph
approximation algorithms
Primary area: optimization
TL;DR: We develop new MPC and semi-streaming algorithms for approximating the directed densest subgraph.

Abstract: 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+\varepsilon)$-approximation in $\tilde{O}(\sqrt{\log n})$ MPC rounds with sublinear memory per machine. This improves the state-of-the-art results by Bahmani et al. (WAW 2014) and Mitrovic \& Pan (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 $\tilde{\Omega}(n^{1/6})$-approximation for a single pass; a better approximation is known only for randomized streams (Mitrovi\'c \& 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+\varepsilon)$-approximation of an $O(\log n)$-pass algorithm by Bahmani et al. (VLDB 2012). Second, we demonstrate that our MPC algorithm requires fewer rounds than prior work.

New Parallel and Streaming Algorithms for Directed Densest Subgraph
Slobodan Mitrović
Theodore Pan* University of California, Davis thipanducdavis.edd
University of California, Davis
smitrovicQucdavis..
Mahdi Qaempanah Sharif University of Technology
Mohammad Amin Racisi
Yale University amin. raeisi@leee edu
mahdi mahdi.ghaempanantt Saaddh.ghheemaaah11@@ttuuc sharif. edu
Abstract
Finding dense subgraphs is fundamental problem with applications to community detection, clustering, and data mining. Our work focuses finding approximate densest subgraphs in directed graphs in computational models for processing mas- sive data. We consider such models: Massively Parallel Computation (MPC) and semi-streaming. We show how find (2 + aapproximatioon in Ó(Vlog n) MPC rounds with sublinear memory per machine. This improves the -tate-of-the- art results by Bahmani al. [BGM14, WAW 2014] and Mitrović Pan [MP24, ICML 2024]. Moreover, we show how to find an Ollog n2) approximation in a single pass in cemi-streaming. This stark contrast to prior work, which implies (2(n//0) approximation for a single pass; better approximation 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 Ollog" n) worst-case update time while using sub-linear memory. We empirically evaluate our approaches in two ways. First, we illustrate that our single-pas. -psle semi-streaming algorithm performs much better than the theoretical guarantee. Specifically, its approximation on temporal datasets matches the (2 + apaprooxiittionn of an Ologg n) -pas algorithm by Bahmani et al. [BKV12, 12, VLDB 2012]. Second, we demonstrate that our MPC algorithm requires fewer rounds than prior work.
1 Introduction
Computing dense subgraphs in directed graphs is classical optimization task where we are interested in subgraphs with a large edge-to-vertex ratio. In particular, given a directed graph G = (V, E). the densest subgraph (DS) problem asks to find two vertex subsets S,T C V such that the ratio (SI, /ISI- [T'] is maximized, where E(S, T) is the set of directed edges from S to T. This problem has found a wide range of applications in graph mining, including the analysis social networks [LRJA10, For 10, CS C0], bioinformatics [FNBB06, SHK + 10), visualization [ZP12, ZT12), and finance IZZY+ 17, FRM19, CT22, 1 22].
With the constant increase in the size and prevalence of large datasets, it has become crucial to develop algorithms that solve fundamental optimization problems with limited constraints, such
'Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Massively Parallel Computation model
Approximation
Memory per machine
Round complexity
Reference
Undirected
(1 +)
O(n')
Ö(ylog n)
[GLM19]
(1 +)
(nn))
( n.)
[BGM14]
Directed
(2 ()
O(n))
OVVog m)
Our work
(2 6)
((n)
O (Voog
[MP24]
Semi seem-stre model
Approximation
# of passes
Deterministic or randomized
Reference
(1+ E)
Randomized
[EHW155
Undirected
O(logn) m2)
Deterministic
Our work
(2 +)
O(logn)
Deterministic
[BKV12]
12(n//6
1
Randomized
[EHW 15]
(2 +)
1
Random order stream
[MP24]
Directed
O(logn)
1
Deterministic
Our work
(2 +++ E)
O n)
Deterministic
[BKV12]
Dynamic model
Approximation
Memory usage
Update time
Reference
(4
(nn)
O() amortized
[BHNTI5]
Undirected
O(logn)
O(n)
O(1) worst-case
Our work (insertion-only)
(1+E)
((m)
O(1) worst-case
[SW20]
O(logn)
(nn)
((1) worst-case
Our work (insertion-only)
Directed
+
((m)
Ó(1) worst-case
[SW20]
Table 1: summary of state-of-the-ard results on the DS problem MPC, semi-streaming. and dynamic models for constants > 0 and 5 E (0, 1), and graphs with n vertices and m edges.
memory per computing unit data access. While it is known how to find DS in polynomial time [Cha00], it is unclear how to efficiently implement this algorithm in the context of large-scale modern computation. It inspired several research groups to study DS computation in distributed, parallel, and streaming settings under various memory constraints and approximation guarantees.
In Massively Parallel Computation (MPC), which is theoretical abstraction of popular large-scale frameworks such as MapReduce and Hadoop, [BGM14] proposed an Olog n/=²) MPC round algorithm for constructing (1 appprrxxmmae DS for directed and undirected graphs, where > is a precision parameter and = |. For undirected DS, this complexity was improved by [GLM19] to O( ( Vlog n log log n) rounds. Recently, in the setting where each machine in MPC has ((n) memory, [MP24] designed algorithm for (2 22+ (2++))-appooxxt -aproxximation of directed DS that takes O( O(Vlog rounds.
In the context of semi-streaming, [BKV12] proposed an elegant peeling-based algorithm that com- putes (2 + ->approximation of directed DS in Olog n/e) passes. If the goal is to compute undirected DS, [EHW15] provide a single-pass algorithm that guarantees a (1 + apaapooximatioon > aappprxximation Better approxi- mations are only known if the underlying stream is randomized [MP24] or if 2(n 1.5) memory can be used the semi-streaming setting [EHW15].
Interestingly, the same technique for directed DS attains a Ū(n 1/6
Motivated by this disparity between the state-of-ther the-art results for directed and undirected DS, we ask: What algorithmic techniques help narrow the gap in computing directed versus undirected DS?
1.1 Our contributions
Table 1 provides a summary of previous state-of-the-ar results in comparison to ours.
Result (Theorem 4.2 rephrased). Given n-vertex graph and 0, there exists sublinear MPC algorithm that outputs (2 + =)-approximate directed DS in Ö ((Vlonn) rounds. The algorithu uses O(n') memory per machine and O(n m) total memory for 8 (0, 1).

---

This improves on [BGM14], which uses Oloo n) rounds, and on [MP24], which uses O(ylog MPC rounds but requires near-linear memory per machine. Additionally, Result matches the state-of-the-arr round complexity of Ó( Vlog 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 & > O. there exists a single-pass deterministic semi-streammin algorithm that outputs an Olog n) -apprxximate directed DS.
This is the first single-pass semi-streaminn algorithm for the directed DS problem on arbitrary streams. [MP24] attains a (2 + + >approximationn but only for randomized streams. [EHW 15] attains (1 =)- approximation when additional memory, i.e., O poly logn), is allowed. If we were to extend the ideas of using uniform sampling from prior works, generalization of the construction in [MP24] shows that it will result in at least St(n 1/6 -approximation. We also note that this is deterministic algorithm and can be easily adapted to undirected graphs, leading to the first deterministic single-past streamin algorithm for the DS problem 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 Ologg" n) for directed graphs. To our knowledge, no previous algorithm maintains an approximate directed DS in semi-streaming. [BHNT15] shows how maintain 3 -approxxmiie undirected DS with (1) amortized update time and Ó(n) memory but may have (2()) worst-case update time. [SW20] shows how maintain a (1 + -aaaproxximate directed DS with Olog" n) worst-case update time but requires linear memory.
Empirical evaluation suggests that, in practice, our semi-streaming algorithm yields approximation much better than log n. On temporal datasets specifically, it matches the approximation [BKV12] 12].
2 Preliminaries
Transformation: General directed to bipartite undirected graph. Given a directed graph Gair = (Vair, Eair), we represent it as a bipartite graph G = (Vi, V22 E) where: (i) V1 and V/2 are two copies of Várr. and (ii) there is an edge in E between u E Vi and v E V22 iff there is a directed edge from u to in Edi- All directed graphs will be treated bipartite with this representation.
Notation. For bipartite graph G (S,T,), we use n refer to |S] + [T', the total number of vertices. Given two vertex sets A S S and B S T, we refer to the edges between them by EG B) def {e (i.j) iie A,j
E B}. We use do(v) to denote the degree of vertex in G. Directed densest subgraph. Given bipartite graph G = (V, V, E) and vertex sets S,T S V, the density p(S,TT T) is defined p(S, T) def |EOSS T)/ VisI 17]. A directed densest subgraph is sets , such that (S*,T*) E arg max p(S, T)
Massively Parallel Computation (MPC). In MPC, synchronous rounds of computation are per- formed across N machines. Each machine has words memory and, initially, the input data is arbitrarily distributed across the machines. During round, each machine computes its local data. Then, after the round, machines exchange messages synchronously. Each machine can send messages to any other machine, but each machine objective is to perform computation in as few rounds as possible. With respect to S, three regimes primarily studied: given å E (0, 1), sub-linear (S n²), near-linear (S n poly log n), and super-linear (S n +5). In this work, Even though the rumning time in definition of the MPC model allowed to be arbitrarily large, the running time of our MPC algorithm is near-linear per round.
send and receive at most S words of data. The primary
focus the most restrictive sub-linear memory regime.
Semi-streaming. In the semi- streaming setting, an input graph = (V, E) given as a stream of edges. That is, an algorithm receives one edge e E E at time, and updates its internal memory based on e. This internal memory constrained to O(n poly log n). After all edges are presented as a stream, we say the algorithm made pass over the graph. An algorithm can make multiple passes over data, During a pass, the algorithm can perform arbitrarily large polynomial-time computations. We remark that our algorithm spends Oppoly log time to update its memory per edge.
3

---

3 The base algorithm
In this section, deseribe the base of approach. Then, in Sections and 5, we develop new insights enabling us to extend this approach to the MPC and semi- seri-streaming model.
As reminder, we use S* and T to denote the vertex subsets corresponding to the densest subgraph Additionally, we view the input graph as a bipartite undirected rather than a directed graph; details of this transformation are described in Section 2. We assume that our algorithm is given the density v / / Then, leveraging the knowledge of D and 2, the
D p( ] and the ratio main idea of this base algorithm is to construct a pair of vertex subsets (S,T) S V x V such that approximates (S*, T in the following sense:
Each vertex in S has least D/(22) neighbors in T.
Each vertex in T has at least Dz/2 neighbors in S.
We show that such pair (S, T) must exist and that it is 2-approximation of the directed densest subgraph. The proofs of the following lemmas can be found in Appendix and Appendix B. Lemma 3.1 (Subgraph existence). Ler
) be directed densest subgraph. Let D = -PSSS, be its density and 2 = [/T There exists an induced subgraph H on vertex sets (S, T) which it holds that (v) D/(2s)
f for all v E S and d (v) 2 Dz/2 for all v E T.
Lemma 3.2 (Sufficient condition for 2-approximation). Let (S*,T*) be a directed densest subgraph. Let D = =(S TT) be its density and =V/ /SS*///T Then, any induced subgraph H on vertex sets (S, which satisfies (v) 2 D/(2z) for all S and d# 2 Dz 2 for all TI has density at least D/2. In other words, it is a 2-approximation of the directed densest subgraph.
Lemma 3.2 provides sufficient conditions under which given subgraph is 2-approximate densest one. These conditions inspire a simple peeling procedure for constructing such a subgraph, c.g., Algorithm 1. Let S and I denote the two bipartite sides of that maintained subgraph. Each S and i' initialized to V. Then, iteratively removes vertices that do not satisfy the degree conditions stated by Lemma 3.2. More precisely, the algorithm iteratively removes vertices from S with degrees less than D22) and vertices from T with degrees less than Dz/2. If only these two steps were performed without any extra stopping rule, this algorithm could execute too many peeling iterations before terminating. To see that, consider the construction in Figure! 1.
KD densest subgraph
KeD+1y/2
Each vertex has edges to previous D 3
2 vertices
Figure I: An illustration of the construction that requires ((n) iterations of peeling. We observe that the added vertices (black vertices) can extend as far desired and will be removed one by one from right left.
We construct an undirected graph; obtain its directed version by considering each undirected edge as two directed ones. Let the densest subgraph be the complete graph KD, which has density D - and 1, start with D+1 -complete subgraph with vertices labeled 1, ... D+1 We continually add vertex with edges vertices D-3 i, D-1 + 2,...,i
will peel vertices with degree less than (D 1)/2. Then, disjoint to this subgraph,
for D-1, This disjoint subgraph and all of its subgraphs have smaller density than Kp. and the number of iterations of peeling is linear with the number of vertices we add, resulting in Q(n) iterations of peeling.
We make a crucial observation that enables us to avoid this behavior a set S or T does not decrease in size by factor of (+)) at least, the current (S, subgraph already achieves the desired
Our final algorithms do require knowledge of D and Those details discussed in Section 4.

---

approximation (see the proof of Theorem 3,4 for details). This stopping criterion - implemented by Lines 5 and 6 enables us ensure sufficient progress in each peeling iteration.
Algorithm 1 Computes 2(1 a)appoxxiea directed densest subgraph assuming that D p(S", and V|5*//17*
Input: bipartite graph G (S, 1, B), parameters e > 0, D and
1: kg (2()), kr Dz/2
2: while true do
3:
A all vertices
with (v) kg
4:
B + all vertices v E T with (v(
< kr
5:
|s [T) and |A|| - T
then return (S,T)
6:
if|S| S = and [B| S
e [T]
then return (S, T)
1+;
7:
Remove A from S and B from T
3.1
Comparison to prior work
The idea of gradually peeling vertices based on their degrees has appeared in prior works on densest subgraphs, e.g., see [BKV12, GLM19, MP24]. Nevertheless, we are unaware peeling-based algorithm that uses stopping rules akin to those on Lines 5 and 6 of Algorithm 1. On the one hand, a typical peeling iteration for computing densest subgraphs removes vertices whose degree less than + & times the average degree. This immediately implies Ologg n) peeling steps and has no need for stopping rules. However, the average degree changes as the graph changes; so, the degree threshold above which to peel vertices evolves. On the other hand, Algorithm uses the same degree thresholds, i.e., kg and ky, throughout the entire execution. Then, the advantage of fixed degree thresholds is that they do not need to be recomputed in distributed and streaming settings. This is one of the key properties enabling us to design our algorithms in the coming sections.
3.2 Analysis of Algorithm
We use peeling iteration to refer to a single while-loop iteration of Algorithm 1. During a peeling iteration, all vertices in S or T with degree below the respective threshold are removed, implying:
Lemma 3.3. Algorithm I executes Ollogtte n) peeling iterations.
Proof. After peeling iteration, either T decreases in size by a factor of least (1 + E), or the algorithm outputs the current vertex sets and terminates (Lines 5 and 6). Once S and T are empty, Algorithm finishes. Hence, there are O(log1+= n)) iterations of peeling.
Theorem 3.4. Let (S* be directed densest subgraph of G. For D =(S" and z = v V Algorithm outputs 2(1 + aapppriiiimatte directed densest subgraph.
Proof. Let H be the subgraph from Lemma 3.1. Since, D -(S,TT"" and 2
I/T"
Algorithm will not remove any vertex from H. Hence, and T produced by Algorithm are not empty sets. Therefore, there must exist iteration of Algorithm in which A (resp. B) is at most e/(1+)) +)) (resp. () That is, this iteration, S and T would decrease size by a factor less than + e. Observe that when such an iteration occurs, the algorithm terminates. Therefore, we have the following two cases.
meaning that at least T4E 18] vertices in have degree at least ks. This allows us to lower bound the density, giving us
Case Algorithm terminates at Line 5. We have that A <
T+ce
ks-
|S| I+s
D
S ITI
D 2(1
((S,T)
>
Z
S
2(1+))
where we used |S|| 2 2T Therefore, the produced subgraph is 2 =paaroxximaaion.
5

---

Case Algorithm terminates at Line 6. Similarly, we have that [B|
S
- IT') meaning that at least
T4c [T] vertices in T' have degree at least kr. This gives
kT
T
D
T
D
P(S,T) Z
1+e
S
2(++))
S
2(1 +
using the |S| S T constraint. Therefore, this also produces 2(1 + -)-aprooximation
Ó (Vlog) MPC rounds in the sublinear memory regime
In this section, extend Algorithm I to the MPC sublinear memory regime. Directly translating Algorithm I into an MPC is straightforward - standard MPC algorithmic primitives, e.g., see [GSZI] ASS+ + 18], enable
perform one iteration of peeling in O(1) MPC rounds. Since Algorithm takes (log n) iterations, this direct MPC implementation results in an Ollog n) MPC round algorithm in the sublinear memory regime. However, we aim obtain a quadratically faster algorithm.
4.1 Our improved approach
On high level, we execute the O(log n) iterations of (a variant of) Algorithm in Ö (llogn MPC rounds. We present the intuition behind this approach in two steps: (i) Recall known framework for simulating (log n) iterations in Ó Plo n) MPC rounds; and (ii) Describe a modified variant of Algorithm that fits into that simulation framework.
Known simulation techniques. Consider T-iteration algorithm ALOCAL such that: (1) ALOCAL maintains state of each vertex, e.g., a vertex v is removed or not, and (2) the state of v in iteration i depends only on the states of v and its neighbors in iteration should be removed in iteration based on the number of v's non-removed neighbors in iteration i 1. The output of ALoCAL is the state each vertex in each the iterations.
1, e-g.. ALOCAL. decides whether
Remark: Algorithm does not have the properties of ALOCAL. e.g., evaluating the conditions on Lines and requires "global" computation. However, we note that these lines can be simulated through post-processing, constructing sets S and ' for each iteration and comparing their sizes using the states of vertices. The remaining steps of Algorithm
be phrased in the language of ALOCAL
In how many MPC rounds can we execute ALOCAL. Based on our description, observe that the state of vertex v any moment during the execution of ALoCAL is function of the v's T-hop neighborhood. Let (v) denote the j-hop neighborhood of v. This observation gives rise to the following idea:
(1) Gather (1) of each vertex V.
(2) Place (e) on single machine in MPC; Nr (v) for different u are placed on different machines.
(3) In a single MPC round, execute ALOCAL within (T) to learn the state of v.
Assuming that (T) fits in the memory of single machine, significant advantage of this approach that it takes only O(log T) MPC rounds. Namely, Item can be implemented using a well-known technique graph exponentiation [LW10, 10, Ghal7]. In this technique, No. (u) is gathered for each E V and for each i = 0.. log. T, using the following relation:
N
U
(w).
(v)
Namely, each iteration of the graph exponentiation technique doubles the radius of the neighborhood collected around vertex. To implement this technique in MPC, it is necessary address: Can Ny (v) fit into the memory of single machine in MPC? This takes us to the second part of our approach.
Graph sparsification (Algorithm 2) A modified variant of Algorithm 1. We alter the recipe above to simulate ALOCAL in MPC while still aiming for o(T') rounds. Namely, (i) we can split those T iterations into T/k groups, each consisting of & consecutive iterations, (ii) execute group after group sequentially, such that (ii)) each group is executed as described above by using graph exponentiation. Setting aside memory constraints. this method uses O ( log k) MPC rounds. The larger l is, the fewer MPC rounds are needed. However, a larger k implies bigger Ny(v) which might not fit in

---

Algorithm 2 Finds partial (2 + e) approximation of directed densest subgraph
Input: bipartite graph G = (S. T. E), (0,1), (0, 1). D and
1: ky (/2)), Ky Dz/2, a =1+ loooo
2: Freeze all vertices in of degree greater than kşa
3: Freeze all vertices in I' of degree greater than ky
4: Mark as frozen each edge with both endpoints frozen
5: fi number of frozen vertices in 5
6: f2 f number of frozen vertices in T
V
7: if fi Z
f2
then return (S,
8: P1 min (1. 18 log
9: P2 min
[. 18 logn
Vōlog
10: t
2
11: for steps do
12:
G1 < sample of each non-frozen edge of G with probability p
13:
G2 < sample of each non-frozen edge of G with probability p2
14:
A { all non-frozen vertices S with de, (v) pkg
15:
B 4 all non-frozen vertices v E with dG. (b) < pkr
16:
if S|| =²[T] and ||| T+g f1 then return (S,
17:
if S $ (T and |B] S - f2 then return (S,T)
18:
Remove A from S and B from T
return (S,T)
machine's memory. It turns out that k = @ (vv (vlog n2) is the largest k our approach can tolerate after performing certain graph sparsification from [GU19] described next.
Fix = ( ((Vloon), Ignoring the memory-pere -ee---er-aaaaee per-machine constraint, (V( can be collected in Olog log n) MPC rounds. However, cannot guarantee that these neighborhoods fit on a single machine with (nn²) memory, as some vertices can have large degrees. For example, vertices with degree of (nz²) cannot even store their entire neighborhood on single machine. Inspired by this, Algorithm 2 temporarily "ignores" these high-degree vertices when performing graph exponentiation. We call this process freezing high-degree vertices, seen on Line 2 and Line 3. Intuitively. freezing enables to transform the current graph into one having sufficiently small degrees, and hence the graph exponentiation can be executed with O (n²) memory per machine. On Line 4, we also ignore the edges between frozen vertices since they do not affect the peeling of non-frozen vertices.
samples the graph on top of freezing high-degree vertices on Line 12 and Line 13. Combining both freezing and sampling, the graph becomes sparse enough so that (tt)-hop neigh- borhoods fit within sublinear memory and peeling is simulated with high probability. Therefore, if ((t) iterations of peeling can be simulated in (log log rounds, then we can simulate the entirety of Algorithm in O OVVlog
Algorithm 2
log log n.) rounds. Between these phases of simulating O (VVlog n) iterations of peeling, frozen vertices are updated based on their new degrees. However, these frozen vertices are not peeled during these phases, and therefore our peeling does not quite match O /Toloo n) iterations of peeling in Algorithm 1. Nevertheless, our final algorithm uses Ó ((vTog n) rounds. We show that the fraction frozen vertices too small to affect the entire peeling process.
4.2 Analysis of Algorithm
When trying to simulate Algorithm 1, it important to note that our stopping rules are affected since we have limited information the degrees of frozen vertices. So, weaken our rules and this is reflected in the differences between Line and Line Algorithm 2. Algorithm 2 simulates t O @(vlog n. iterations of peeling as described above, but due to frozen vertices, not obvious how much the sizes vertex sets decrease by. Nevertheless, establish the following claim about the number of frozen vertices. The proof of Lemma 4.1 is deferred to Appendix C.
Algorithm and Line 16 and Line 17 of
7

---

Lemma 4.1. Let G = (S be bipartite graph and (5*, be its directed densest subgraph.
Let ( be the output of Algorithm 2 ran on G given pl .T)
(1+E)a D
p(""
and
1/7"/
(1+E)
(1+6)
S v 1/8- Then, with probability least */2 it holds that:
Good approximation. (S',T) is 2(1 + -eleaaappoiiimae densest subgraph of G,
Size reduction. , T') contains a 2(1 + - "ap--apppmaateee densest subgraph of G and
S
|S 2 or T
7
where = + 8)
Following the ideas described before, we invoke Algorithm 2 e ((vlog n.) times to simulate all iterations of peeling, resulting in the following theorem, whose proof is deferred to Appendix D.
Theorem 4.2. There exists a sublinear MPC algorithm that runs in Ō Ö(Vlog n) rounds and attains 2(1 + =) approximation of the directed densest subgraph with probability at least 1 - 4.4 The algorithm uses (π²) memory per machine and ( + m) total memory for E (0,
5 Single-pass semi-streaming algorithm
In this section, extend Algorithm 1 to the single-pass semi-streaming setting. unelear how to adapt the sampling used for the MPC algorithm since the number of edges sampled could be w(n poly log n), surpassing the memory limit of the semi-streaming model. Nonetheless, we show that an ( nt) apprrxxmmttee directed densest subgraph can be obtained by maintaining only vertex degrees throughout the stream. This directly results in Ó(n) memory requirement, vertex's 's degree can be maintained using simple integer counter. To the best our knowledge, this the first semi-streaming single-pas, pass algorithm for the directed densest subgraph problem that achieves better than poly n approximation.
5.1 Our approach
Algorithm 3 Finds Ollog n) approxxmmaiai of directed densest subgraph
Input: bipartite graph G (S, T, E), > 0, and
1: ki = (2(2)), ky = Dz/2
2: 1s(u),(7(1) <
for all V
stands for level > d stands for vertex degree in its current level
3: ds(v) + for all v E V
4: while stream empty do
5: (u,v) f- next edge from stream
6:
iflg(u) S (r(()) then ds(u) < ds(u) +1
7:
ifls(w) 2 (r(w) then (v) < dr(v) +1
8:
if (ds(u) 2 kş then
9:
1s(u) < ls(u) +1
10:
ds(u) + 0
if drd) kr then
12:
(1( t lr(v) +1
dr(v) <
14: S. - (v:ls(u) 2 i for all
0 < i log nl logi+e 7
T: (w:lr(v)
21 for all 0
i
16: for 1...=22.22 1...2200114 n do
if 22|T] and |S||
2
18:-1l then return (S,,
1+c
if [ S TT and [T, N
T.
then return T;)
Itc
How can vertex degrees leveraged to (approximately) simulate Algorithm /? We observe that Algorithm I implicitly computes vertex-vector 1, where ((v) is the pecling iteration after which

---

vertex U was removed from the graph. We refer to 1(v) as the level of v. Having I suffices to recover (S, ()) in each iteration of the while-loop. Our approach approximates ((v) for each vertex by using the evolution of vertex degrees as the stream is read. We now discuss details.
As reminder, we think of an input graph as bipartite with the bipartitions S and T; details described in Section 2. As our algorithm scans the edges in a stream, the maintained vertex degrees increase. Initially, each vertex level and vertex degree O. A vertex's 's level ((v) increases when the algorithm is certain that v will not be deleted from the graph within the first (()) peeling iterations.
On a high level, once vertex degree reaches (22)) if it is in S or Dz/2 if is in T. it will not be removed during the first peeling iteration. Therefore, we can confidently increase its level to 1. For a vertex in S to move to level of at least 2, its degree must be at least D/(2z) after the 1st peeling iteration. Unfortunately, before reading the entire stream, our single-pass algorithm cannot say with certainty that vertex will be peeled in the 1st peeling iteration. However, if vertex is not peeled in the 1tt iteration, an algorithm learns that information about e potentially before reading the entire stream. Inspired by this, we estimate the levels of vertices as follows.
For an edge (u, v) on the stream, we increase d((u) only if ((v)= 2 ((u). This guarantees we only count edges where the other vertex has not been removed yet. Once vertex moves to higher level, we need to determine its degree at that level. However, it is not obvious how to calculate this degree without maintaining the edges in the subgraphs of each level. Therefore, in Algorithm 3, we assume the worst case and reset the degree of the vertex to when it moves to a higher level. This poses challenges in analyzing whether these degree estimates are accurate enough to output an approximation of the directed densest subgraph, especially when the stream of edges is adversarial. Fortunately, we show that Algorithm 3 ran for specific input of D and produces an Ollgg appaaproxiimttion. Precisely, we show the following result, whose proof is deferred to Appendix E.
Theorem 5.1. There exists a single-pas, semi- stni-streaming algorithm that attains an Ollog n)- approximation of the directed densest subgraph.
Remark. To adapt the algorithm to finding the undirected densest subgraph, we no longer need z. All other ideas remain the same, resulting in a single-pass semi-streaming algorithm for approximating the undirected densest subgraph as well. We also have a dynamic algorithm with O(1) update time for each guess on D and z. We can maintain sets (S; T;) throughout the algorithm without increasing the update time, resulting in Ologg)) update time and O(log" n) update time for directed graphs. We can output our approximation of the densest subgraph anytime in (poly log n) time.
6 Experiments
Baselines. We empirically evaluate the performance of our semi-streaming algorithm, comparing it to the (2++) ---=)-appoxiimttoon O(log n) pass comi-streaming algorithm from [BKV12]. We also compare it to the single-pass semi-streaming algorithm from [MP24], but the density plots of [MP24] follow very similarly to [BKV12]. So, we only include [BKV12) in our approximation plots Figure 2. As discussed in the introduction, [MP24] can have a quite high worst-case update time per edge on stream, while the update time of our work is Ollog n). We illustrate this empirically in Figure 3.
To these experiments, of RAM, 256 KB of L2 Cache, and 2.5 MB of L3 Cache (per core).
an M1 machine running macOS Sequoia 15.3.2 with 4 cores, 8 GB
Data. We use 10 datasets from the Stanford Large Network Dataset Collection [LK14]. 5 of these datasets (Slashdot, Berkeley-Stanfool Web, Google Web, Pokec, LiveJournal) are general directed graphs; most consist of edges sorted by endpoints. The other 5 datasets (Ask Ubuntu, Super User, Wikipedia, Twitter, Stack Overflow) are temporal directed graphs where edges are in sorted time order of when interactions happened. These temporal graphs reflect a stream of edge updates.
Results. We run the algorithms on temporal directed graphs with E = 0.2. These datasets present events/edges in the order they occurred, making them an excellent benchmark for practical applica- tions of dynamic algorithms. In Figure 2, we see that our algorithm matches [BKV12] for the largest density. We also observe that it is significantly less sensitive to error in =2, making it better in practice than [BKV12] when our approximation of z may not be as precise. Overall, we demonstrate that in practice our algorithm performs much better than the log theoretical guarantee would imply.

---

Graph
Nodes
Edges
Graph
Nodes
Edges
Slashdot
82,168
948,464
Ask Ubuntu
159,316
964,437
Google Web
875,713
5,105,039
Super User
194,085
1,443,339
Berk-Stan Web
685,230
7,600,595
Wikipedia
1,140,149
7,833,140
Pokec
1,632,803
30,622,564
Twitter
456,631
14,855,875
Live.Jurnaa
4,847,571
68,993,777
Stack Overflow 2,601,977
63,497,050
(a) General directed graphs
(b) Temporal directed graphs
Saper benotee
Out S.
62
20000
50000
80
127
Figure 2: Density as a function of x² for various temporal datasets.
Butticy Stanbord Web Tomesfore
Google Web Timma 3200
Pokac Tima 10000
<0j4 02
01.01-10
2.14
8.14
0L.0122
8.12
0.6
Figure 3:
Update time between processing edges of the stream for various general datasets.
We also compare the update time of our algorithm to IMP24], using their threshold f 1 1/450, in Figure 3. The plot contains update times of the algorithms for batches of 10,000 edges. The chosen c where the largest densities are attained, and the chosen are based maximizing densities. Note that E does not significantly affect the running time of our algorithm. As we can see, the worst-case update time of our algorithm is significantly more stable and lower compared to [MP24].
Experimental results for the remaining datasets can be found in Appendix F. Additionally, we provide experiments for our MPC algorithm in Appendix G which show that our algorithm not only improves the theoretical upper bound on round complexity but also uses fewer rounds in practice.
7 Conclusion and future work
We study the directed densest subgraph problem MPC and semi-streaming models. Our MPC algo- rithm bridges the gap between known algorithms for computing undirected and directed approximate DS. We also develop a simple deterministic single-pas poggle-passaae cemi-streaming algorithm. This the first single-pass algorithm for the directed DS problem to achieve sub sub-polynomial approximation.
Our work leaves a few intriguing questions. First, even though our MPC algorithm is able to match the round complexity of the wtate-of-theart undirected DS algorithm, there is still gap between their approximation factors, + compared 2 + E. possible to improve the approximation guarantee for the directed DS problem while not increasing the round complexity? Second, can this upper bound of ((TTog MPC rounds in the sublinear memory regime be broken for either undirected or directed graphs? Third, our semi-streaming algorithm attains an O appaoopxxiiaaoonn. Can we develop a single-pass remiistreaming algorithm with approxxmxoinn for directed graphs?
10

---

Acknowledgments and Disclosure of Funding
S. Mitrović and T. Pan were supported by NSF CAREER award, No. 2340048. We are grateful to anonymous reviewers for their valuable feedback.
References
[ASS+18] Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel graph connectivity in log diameter rounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 685- IEEE, 2018.
[BGM14] Bahman Bahmani, Ashish Goel, and Kamesh Munagala. Efficient primal-dua -ual graph algorithms for mapreduce. In International Workshop on Algorithms and Models for the Web- Web-Graph, pages 59-78. Springer, 2014.
[BHNT15] Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 173-182, 2015.
[BKV12] Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and mapreduce. Proceedings of the VLDB Endowment, 5(5), 2012.
[Cha00] Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In International workshop on approximation algorithms for combinatorial optimization, pages 84-95. Springer, 2000.
[CS10] Jie Chen and Yousef Saad. Dense subgraph extraction with application to community detection. IEEE Trunsactions on knowledge and data engineering, 2217):121--1230, 2010.
[CT22] Tianyi Chen and Charalampos Tsourakakis. Antibenford subgraphs: Unsupervised anomaly detection in financial networks. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2770, 2022.
[EHW15] Hossein Esfandiari, MohammadTaghh Hajiaghayi, and David P Woodruff. Applications of uniform sampling: Densest subgraph and beyond. arXiv preprint 150.
2015.
[FNBB06] Eugene Fratkin, Brian T Naughton, Douglas L Brutlag, and Serafim Batzoglou. Motifcut: regulatory motifs finding with maximum density subgraphs. Bioinformatics, 22(14):110-- e157, 2006.
[For10] Santo Fortunato. Community detection graphs. Physics reports, 486(3-5):55-174, 2010.
[FRM19] András Faragó and Zohre R. Mojaveri. In search of the densest subgraph. Algorithms, 12(8):157, 2019.
[Gha17] Mohsen Ghaffari. Distributed mis via all-to-all communication. In Proceedings of the ACM symposium on principles of distributed computing, pages 141-149, 2017.
[GLM19] Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrović. Improved parallel algorithms for density-based network clustering. In International Conference Machine Learning, pages 2201-2211 PMLR, 2019.
[GSZ11] Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and sim- ulation in the mapreduce framework. In International Symposium Algorithms and Computation, pages 374-383. Springer, 2011.
[GU19] Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1636-1653.
SIAM, 2019.

---

22Z Yingsheng Ji, Zheng Zhang, Xinlei Tang, Jiachen Shen, Xi Zhang, and Guangwen Yang. Detecting cash-out users via dense subgraphs. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 687-697, 2022.
[LK14] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. attt:://snap: stanford............ edu/data, June 2014.
[LRJA10] Victor E Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. A survey of algorithms for dense subgraph discovery. Managing and mining graph data, pages 303-336, 2010.
[LW10] Christoph Lenzen and Roger Wattenhofer. Brief announcement: Exponential speed-up local algorithms using non-local communication. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 295-296, 2010.
[MP24] Slobodan Mitrovic and Theodore Pan. Faster streaming and scalable algorithms for finding directed dense subgraphs in large graphs. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 35876-35891. PMLR, 2024.
[SHK+ 10] Barna Saha, Allison Hoch, Samir Khuller, Louiqa Raschid, and Xiao-Ning Zhang. Dense subgraphs with restrictions and applications to gene annotation graphs. In Annual International Conference on Research in Computational Molecular Biology, pages 456- 472. Springer, 2010.
[SW20] Saurabh Sawlani and Junxing Wang. Near-optimal fully dynamic densest subgraph. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. pages 181-193, 2020.
[ZP12] Yang Zhang and Srinivasan Parthasarathy. Extracting analyzing and visualizing triangle k-core motifs within networks. In 2012 IEEE 28th international conference on data engineering, pages 1049-1060. IEEE, 2012.
[ZT12] Feng Zhao and Anthony KH Tung. Large scale cohesive subgraphs discovery for social network visual analysis. Proceedings of the VLDB Endowment, 6(2):85-96, 2012.
iZZY 17] Si Zhang, Dawei Zhou, Mchmet Yigit Yildirim, Scott Alcorn, Jingrui He, Hasan Davulcu, and Hanghang Tong. Hidden: hierarchical dense subgraph detection with application to financial fraud detection. In Proceedings of the 2017 SIAM international conference on data mining, pages 778.78. SIAM, 2017.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state our theoretical and experimental results well as the assumptions of the algorithms.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should elearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals not attained by the paper.
12

---

2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations are clearly stated in the statement of our results and discussed the conclusion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Our proofs of our theoretical results are written clearly and are all mathemati- cally rigorous.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
13

---

Answer: [Yes]
Justification: The parameters used for our algorithms are provided and the data ran for experiments are cited. The implemented algorithms are the same the pseudocode provided.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide access to the data and code in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ce)
lublic/guides Seaideee/ooeuuubisseeee wom.iisssooooicyyy.. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips. cc/ wtcppppllcc//ccceccccccccc.lltll httpc/ggidde/oeeduuiiieeeeeeeeee http///eeuuiiiiiiiooooooiooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
14

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All parameters used in our algorithms are provided. Also, the context and source of our data are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our implemented algorithms are deterministic and their results are completely determined by the input data, so there are no reportable errors in the results. We emphasize its statistical significance through using multiple data sets.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
15

---

Answer: [Yes]
Justification:
Our experiments compare approximation guarantees and time of execution of algorithms. We used a standard laptop whose characteristics are provided the experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: httppp::///eripp.... cc htc//ublic/BBeeeee eettee/EEsshtieeeeee crrbiicssueeenneee dine??
Answer: [Yes]
Justification: There no apparent harmful consequences of the results in this paper. Experi- ments are carried out in an ethical manner (no illegal data usage, etc.).
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: It is not obvious how the algorithms can be misused. Our results are more foundational research and we don't any direct path negative applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
16

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
There is no risk of misuse as data used was already publicly released and safe.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We credit the Stanford Large Network Dataset Collection where we got our data to run experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We are not releasing any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
17

---

Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our research does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our research does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLMs were used for the results in this paper.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: : /tt////een..p//e/ee wcc/oonffrencee///00 for what should or should not be described.
18

---

A Proof of Lemma 3.1
Lemma 3.1 (Subgraph existence). Let (S", T*) ) be a directed densest subgraph. Let D p(S", T be its density and & = |/ There exists an induced subgraph on vertex sets (S.T) for which it holds that dæ (v) D2 for all E S and dh (v) 2 D all u E T.
Proof. We claim that the directed densest subgraph satisfies the constraints of such subgraph H. Consider any vertex E S Since H is the directed densest subgraph, removing v does not increase the density. Therefore, we have
15 T 1IS
Ec(S", T*) du (v)
V(|8+ TM
1-1 | -
dH(l)
[E TT)
15t1
[Sa(S" .T') D
du(v)
2
2z
where for the last inequality, we used (1- - 1/155/1)1) 1/2 < 1/(2|5*)). Similarly, can show that for any vertex v E T", it must satisfy (e) 2 Dz/2.
Hence, the pair (S*,T*) T)) satisfies the constraints of the claim.
B Proof of Lemma 3.2
Lemma 3.2 (Sufficient condition for 2-approximation), Let (S*,T"))))) be directed densest subgraph. Let D p(S T*) be its density and /|S*|/|T*|. Then, any induced subgraph H vertex sets (S, which satisfies (v( 2 D/(2z) for all E S and d ( 2 Dz/2 for all v E T has density least D/2. In other words, a 2-approximation of the directed densest subgraph.
Proof. The amount of edges in is lower bounded by max (1s) have
D 22
[T] |T|
D Therefore, we
max
D (IS)
|T|
D 2
25
p(H)
V
D
S
T
max
2
T
D
2
2
since the two parameters in max
are reciprocals of each other, implying one of
7
them is least 1.
C Proof of Lemma 4.1
We will the following lemma connect degrees between the original graph and the sampled graph.
Lemma C.1. Consider graph G, > 0, & E (0, 1). Let be a subgraph of G obtained by sampling
each edge of independently with probability = min (1, 18logn 1 1 for all v G. holds:
Then with probability at least 2²
ifda(v) I r then (v) pk:
19

---

ifdc(u) 2 (1 + E)k, then du(v) > pk.
Proof. If p 1, then the lemma follows immediately. So, let 1og Consider any vertex
2a S k/2, we have
V V. If (v) x k/ + +), then we consider two cases. When da(v)
pk
(r(d 2 pk]
exp
E [d (v)] /3
E8 [d]
pk
E [[der
exp
exp
(-pk/6) s n
and when k/2 < do(v) S k/(1 8), we have
Pr(dn(v) 2 ph] v exp (-
pk
-1)²
[dn(v)]
E
Esd (v)
1
exp (-é² pk/6) S n
Therefore, using the union bound over all vertices, we have that (v) < pk for all v E G, satisfying dv(v) k/(1+ e),, with probability at least # Now, if do(u) 2 (1+e)k, then have
pk
Pr(d=(v) S pk] I
exp
E [dn(v)]
E [dd(v)) /2
exp
(1+
(1+k)p//2
1
1
exp
pk/6) S
n
Similarly, using the union bound over all vertices, we have that dz(()) pk for all v E G, satisfying da(v) 2 (1+ + k),, with probability at least -.
Lemma 4.1. Let (S,T, E) be a bipartite graph and (S*, T*) be its directed densest subgraph. Let (S", T") be the output of Algorithm 2 ran G given ,(S",T")
(1+e) S D < ((S",T') and //8-1//T41
<
(I+e)
(1+c)
S [/Tm Then, with probability at least 1. it holds that:
Good approximation. (S' ( is a 2(1 + 8 approximate densest subgraph of G, or
Size reduction. (S', T') contains a 2(1 + 2) approximate densest subgraph of G and
T
| < or T' <
7
where = (1 + 8) Beo
Proof. Without loss of generality, assume the inputs of Algorithm 2 satisfy [T] cz2 for some
Now, if f *v/S|!T| we use the high degrees of frozen vertices to see that
Jiksa
D
p(S",T*) T*)
p(G)
S
2
+1+
meaning that is 2(1 approximaaion of densest subgraph. similar argument can be made if f2 2 V
assume that both of these conditions not satisfied.
20

---

Now, if we look at the peeling process, it closely simulates Algorithm 1. Using Lemma C.1 and the constraints on and 2, we see that we're removing vertices in S with degree below ks/ + E) and keeping vertices in S with degree at least (1 + E)kis where
p
P T
kg
2(1 + 8)3² IT
2(1 + (11+)) ST
with probability at least 1 xe using the union bound over all iterations of peeling. Similarly, we that we're removing vertices in T with degree below kr/(1 + +) and keeping vertices in 7 with degree at least (1 + k) where
P(S T
P( T 2(1 +)2 2 VIS*IIT*
2(1 E)4 V | kr
also with probability at least 2 Following the same argument behind Theorem 3.4 but using these bounds on ky and kr, we see that returning early will result in a 2(1 + +) apprroooxinitooon in total. Therefore, will assume Algorithm 2 does not return early. Then, consider two cases.
If e S (1 blogit then we see that
fi T
S
(1 + (1+ log
and
S
T
f2
20
(1 + E) / logi++ n/2
Therefore, after iterations peeling, we have that the final returned vertex sets (5', satisfy
S < S - (1++) + (1 (1+E))1 S (1 (1+
Ss
(1 100081114 n/8
or
T [7|
- (1 (1 61+
T
+ ee)
(1+ 2) logio n/8
because of Line 16 and Line 17, using the upper bounds on Si and fz, and sufficiently large
the other hand, if (1 + e) Flog11" then we still see that fi S (1 So,
| 2 2 remains true throughout the whole algorithm, then due to Line 16 we have that the final returned vertex sets (S', T') satisfy
|s < |S| - (1+e)h + +1+E)) (1 (1+ 108844
S
(1+
following a similar argument as above. Otherwise, at some point we have that |S|/|T] < x2 meaning that SS must have decreased by least a factor of As result, we also have that |S Flosteee R/s in this case due to the lower bound on c.
D Proof of Theorem 4.2
Theorem 4.2. There exists sublinear MPC algorithm that runs in Ö(Voo n) rounds and attains a 2(1 + -j-aapprxnnnation of the directed densest subgraph with probability at least 1 - The algorithm uses O(n²) memory per machine and O(n 1-8 + m) total memory for E (0,
Proof. Let AMPC be our MPC algorithm. We first describe AMPC and then provide its analysis.
21

---

Algorithm description. AMPC considers all guesses on 1 S D S n and using powers of For each of these parallel instances of D and 2,
1 vn
2
vn in parallel
The algorithm invokes Algorithm 2 output of the previous invocation, with the edges of the induced subgraph of the new vertex sets, into the new invocation.
000g1t n/ó times, constantly providing back the
If Algorithm 2 ever returns early in any of these invocations, then we call the pair of vertex sets that returned early a pair of potential verlex sets.
AMPC outputs the pair of potential vertex sets with the largest density over all instances of D and
Algorithm memory and round complexity. Using the same application of the graph exponenti- ation technique shown in [GLMI9, Appendix C.2], we see that each machine will only use O(n") memory since neighborhoods will have size bounded by
36 log n (%
.) E O(n))
with high probability and Algorithm 2 will take Oloo log rounds. Including the number of invocations Algorithm we have that AMrC takes (VVlog n log log rounds. Running the algorithm in parallel over all instances of D and adds an Ologg n) factor to the memory per machine.
Algorithm approximation.
Note that there will be guesses D and that satisfy
p(StTT* (1 + e)3
TT) (1+))2 and VIS (1+6)
SDS
S 1T
Using these guesses and the approximation guarantees from Lemma 4.1, guarantee these potential vertex sets to be a 2(1 + =) 3'-approximation with at least probability 1 - =² taking the union bound over the invocations of Algorithm 2. Since AMPC selects the vertex with the largest density, attains at least a 2(1 + e) apprrxxxmmaoo of the directed densest subgraph.
E Proof of Theorem 5.1
Lemma E.1. Let the directed densest subgraph have vertex sets (.), Then, (St, T;) in Algo- plS"
rithm 3 will be non-empty vertex sets for all 0 S i S 2ogg1+e nt given D S (1++))log+4 and
V/S S VIS-I/TT
Proof. Consider (S,, T2) after running Algorithm 3. Then, in the best-case scenario, all the edges in its induced subgraph, E T,), were used to determine the peeling of its vertices for later vertex sets. However, because the degree of a vertex v is reset to 0 every time u moves to a higher level, information about edges incident v up to that point is informally speaking erased; we call such edges ignored. At most i ks incident edges to vertex in S; are ignored, and, similarly, at most kT incident edges to vertex in T; are ignored. Hence, throughout the entire algorithm, each vertex in S210g n ignores at most 2kg log1+e n edges incident to it and each vertex in T2 121og.4. n ignores at most 2kT logits n edges incident to it.
Consider the induced subgraph on that all vertices in S* have degree at least 8kg logi+e n and all vertices in T have degree at least Sky logi+e by following the proof of Lemma 3.1 and using the bounds on D and z. We claim that some non-empty subsets of these vertex sets will remain in (S21og T2 Log n). which is enough to prove the lemma. Rather than letting edges be ignored throughout the algorithm, we assume they're 'r all ignored at the beginning: 2kg logi45 edges incident to each vertex in S* are ignored and 2kr logi+e n edges incident to each vertex T are ignored. Then, we look how vertices within the induced subgraph on (5", """) are peeled over time.
Since (S*,T') I'* is the densest subgraph, observe
22

---

Notice that
1E , 2 (8kg logi+e n)|5*| = (8ky logi+e n)
and so with the edges that are ignored, the number of remaining edges is lower bounded by
EG (T)( (2kg logi+e 2 (4kg log1+= n)]s*| (4kr -
n)]s-| (2ky log +5 n)[T"
When peeling is performed this subgraph, all the vertices that peeled each cause at most ly edges to be removed, if it is from S and at most ky edges to be removed, if from T If we assume that all the vertices are pecled, at most [ |T edges will be removed, and the graph must be empty. However, this is smaller than the lower bound on the number of edges above, so it is impossible peel all the vertices. Therefore, we end up with non-empty subgraph, and the vertices in this subgraph will not be removed throughout the entire algorithm.
Theorem 5.1. There exists a single-pass semi-streaming algorithm that attains an O(log n)- approximation of the directed densest subgraph.
Proof. Let ASTREAM be our remi-streaming algorithm. We now describe it and provide its analysis.
Algorithm description. ASTREAM runs Algorithm 3 on all 1 D n and Vn S = vn in parallel using powers of 1 + e. Then, out of all the outputs of Algorithm 3 where the vertex sets are both non-empty, we pick the one corresponding to the largest D as the final output of ASTREAM-
Algorithm memory. Note that Algorithm 3 does not need to store (S,, for all 1 2 logite n but only needs to store consecutive sets compare their sizes. Therefore, Algorithm uses (nn) memory through this implementation detail. Additionally, we have O(log* n) total guesses on D and z. Each of these guesses is a copy of all the variables in Algorithm 3, resulting in O(n n) memory in total.
Algorithm approximation. Let the directed densest subgraph have vertex sets (S*, ("), Note that because we only update d(u) for edge (u, v) or (v, u) with ((u) < l(v), this ensures that vertex that is not removed must have degree at least D (22), if is in S, and degree at least Dz/2, p(S".T') if it is in T. Therefore, if Algorithm 3 outputs non-empty vertex sets for D 2 ([I+e)=log14> we follow a similar argument as the proof of Algorithm Ollog n) approximation of the directed densest subgraph.
see that these vertex sets would be an
Specifically, there exists a guess on D and such that
O(S",T") 8(1 =)2 logi+e
8(1+E) logite and VIS (1+E)
p(S"T7"
DD
< VI
Using Lemma E. we know that all vertex sets (S,, T,) in Algorithm 3 for this guess on D and will be non-empty and so Algorithm 3 will output non-empty vertex sets. Since ASTREAM outputs the non-empty vertex sets corresponding the largest D, they must satisfy D > 8(1+s) logie. and results in an O(log n) approxxiiaa..
,(S".T"")
F Additional streaming experiments
We run the algorithms on the general directed graphs. We plot the results of our algorithm run on various values of ranging from 0.2 to 2 while we ran [BKV12] on e 0.2. Even though most of these datasets have edges sorted by their endpoints, which can be considered adversarial for our algorithm, we see from Figure that their approximations are not far off from [BKV12]. Our maximum densities are within factor of around 2 from [BKV12], which is much closer than our theoretical guarantees. We also consider a less adversarial order where we randomize the order of the edges. With a randomized order, we also see in Figure 4 that the computed densities increase significantly, almost matching those of [BKV12]. Figure contains the update time plots for the remaining general datasets.
23

---

Stuthdh
028-11
tun
225
259
181
167
14
30
20
25"
257
Bedke Stuteer Donvionsieii bessites
Lieioo andd Roadembbd Drwiittes
235
Google
1480
Dull
3400
2200
2000
Mij
Google Shandemicest
(Randemend Dentto
Eahmari 8.2
Figure 4: Density as a function of 2² for general datasets and remaining temporal datasets.
Sbetise Tree frie
0.50
Figure Update time between processing edges of the stream for remaining general datasets.
G MPC experiments
We compare our MPC algorithm to the MPC algorithm for directed graphs from [BKV12]. Specif- ically, we look at their density plots as well as how many sublinear MPC rounds the algorithms take. We use 0.6, 0.8, where each machine has ne memory, & = 0.6, the approximation parameter for both algorithms. As can see from Figure 6, algorithm attains densities that
24

---

200
30
20
12
227
357
307
Dan
187
1211
Figure 6: Density and number of MPC rounds function of x² for 6 0.4, 0.6, 0.8, 0.6. The used datasets are described in Section 6.
match [BKV12], 12]. Additionally, it does so using less than half the number of rounds when having the same amount of memory. It continues to use significantly less rounds for smaller amounts of memory and only matches the number rounds for the Slashdot dataset where our algorithm uses a quadratically smaller amount of memory per machine compared to what is used by [BKV12] This is a significant improvement the number rounds in practice and reflects our improvement in the algorithm's theoretical upper bound.
Remark. These experiments were not executed on actual large-scale frameworks, but simulated in centralized setting. The rounds in plots correspond to the number of rounds taken in those MPC simulations.
25


Reviews:
[{"review_id": "nMvfHjuor4", "reviewer": "Reviewer_nQ4e", "summary": "This paper studies the problem of approximating the densest subgraph in directed graphs within the MPC and streaming models. There are three main categories of known results for the densest subgraph problem (both directed and undirected) in these computational settings.\n\nFirst, for undirected graphs, Mitrovic and Pan \\cite{MP24} proposed an $O(\\sqrt{\\log n})$-round MPC algorithm that requires $\\tilde{O}(n)$ space per machine, which is linear in the number of nodes.\n\nSecond, in the streaming model, Esfandiari, Hajiaghayi, and Woodruff \\cite{EHW15} (SPAA 2015) developed streaming algorithms that handle both insertions and deletions of edges. Their method samples $\\tilde{O}(n)$ edges uniformly at random and then applies an offline densest subgraph algorithm to the sampled set at the end of the stream.\n\nFor directed graphs, Mitrovic and Pan \\cite{MP24} also presented an MPC algorithm with $O(\\log n)$ rounds. The streaming algorithm of \\cite{EHW15} can be generalized to the directed case, but this requires $O(n^{1.5})$ space, which is no longer near-linear. Alternatively, the method of \\cite{MP24} can produce a streaming algorithm with near-linear space complexity, but only if the input edges arrive in random order (i.e., the stream is randomly permuted).\n\nIn contrast, this paper presents new MPC and streaming algorithms for the directed densest subgraph problem that outperform the prior results of \\cite{EHW15} and \\cite{MP24}. In the MPC model, the authors propose an $O(\\sqrt{\\log n})$-round algorithm. However, throughout the paper (including Result 1 and Theorem 4.2), the authors repeatedly state that their algorithm uses “sublinear” space per machine without specifying the exact bound. This makes it hard to properly evaluate the result, and the exact space complexity should be clearly stated.\n\nThe second main contribution, described in Result 2 and Theorem 5.1, is a single-pass deterministic semi-streaming algorithm achieving an $O(\\log n)$-approximation for the directed densest subgraph. Although the approximation factor is not constant, this result is interesting because it appears to be the first deterministic streaming algorithm for this problem.\n\nHere are two additional suggestions to improve the paper:\n\n- The authors should cite and discuss the work of Monika Henzinger (STOC 2015), which is a pioneering contribution in this area and should be acknowledged.\n\n- The paper introduces a non-standard term for the model where edges arrive in random order; the common name for this setting is random order streams. Using the standard terminology would make the presentation clearer.\n\n**Summary**\n\nOverall, the paper presents interesting and potentially impactful results for the directed densest subgraph problem in MPC and streaming models. However, the presentation could be significantly improved by clearly stating the exact space complexity of the algorithms, structuring the related work discussion more carefully, and aligning terminology with standard usage in the literature. Addressing these points would make the contribution clearer and strengthen the paper.", "questions": "**Questions and Suggestions**\n\n- Could the authors clearly specify the exact space complexity per machine used by the MPC algorithm? Using only the term “sublinear” is too vague; please state the precise asymptotic bound (e.g., $\\tilde{O}(n^\\alpha)$ for some explicit $\\alpha < 1$).\n\n- Can the authors elaborate on the technical novelty compared to prior work, especially \\cite{MP24} and \\cite{EHW15}? What new ideas or analysis allow achieving the improved number of MPC rounds or the deterministic streaming result?\n\n- Please discuss the pioneering work by Monika Henzinger (STOC 2015), and explain how this paper relates to or builds on that contribution.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- The paper studies the directed densest subgraph problem, which is an important and timely topic in streaming and MPC models.\n- Proposes an $O(\\sqrt{\\log n})$-round MPC algorithm, improving over the previous $O(\\log n)$-round result by \\cite{MP24}.\n- Presents what appears to be the first deterministic semi-streaming algorithm for approximating the densest subgraph in directed graphs, which could be of independent theoretical interest.\n\n**Weaknesses**\n\n- The paper does not clearly specify the exact space per machine used in the MPC algorithm, repeatedly describing it only as “sublinear,” which makes the result hard to evaluate and compare.\n\n- The discussion of related work is limited and does not include important prior contributions (e.g., Henzinger STOC 2015).\n\n- The paper uses non-standard terminology for “random order streams,” which could confuse readers.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and detailed reading of our paper. We address the questions/suggestions provided below:\n\n- The value of $\\delta$ provided to Algorithm 2 specifies that each machine will use $O(n^\\delta)$ memory, which is then shown in the proof of Theorem 4.2. We will make this more clear by adding it to our result and theorem statements; thanks for pointing that out.\n\n- The main technical comparison, which is discussed in Section 3.1, is that our algorithm uses new stopping rules compared to other peeling algorithms (BKV12, GLM19, MP24). These rules give us an efficient, simple peeling algorithm, which enables us to improve existing results for MPC and semi-streaming. As for EHW15, their work is limited to a single uniform sample of the entire graph, while our MPC algorithm takes many samples in order to approximate degrees for our base peeling algorithm. This is not exactly novel but combined with our new base algorithm, it gives us the new results presented in our paper.\n\n- From our understanding, Bhattacharya et al. (STOC 2015) is a dynamic algorithm that outputs an $(8+\\epsilon)$-approximation of the density value and does not provide vertex sets for the approximate directed DS. Additionally, it has an amortized update time of $\\tilde{O}(1)$, the worst-case update time that is polynomial in $n$, and uses linear memory $O(m)$, so it does not fit within the memory of the semi-streaming model. Sawlani & Wang (STOC 2020), which we cite in our submission, provides a dynamic algorithm that outputs a $(1+\\epsilon)$-approximation including the vertex sets of the approximate directed DS. Nevertheless, we agree that we should cite and discuss Bhattacharya et al. (STOC 2015); we will do so in our final version by including a refined version of the following paragraph.\n- As for the techniques, the $(\\alpha, \\delta, L)$-decomposition introduced by Bhattacharya et al. (STOC 2015) is an extension of a fixed d-core which is a classical idea for approximating the DS. Our paper revolves around calculating something similar, as reflected in Lemma 3.2, but the way we compute it using peeling is novel because of the stopping conditions described in Section 3.1; in short, it allows us to keep a fixed threshold of peeling while guaranteeing an approximation in a small number of iterations. Bhattacharya et al. (STOC 2015) does not maintain this fixed threshold and actually allows relaxations in the threshold, specified by the $\\alpha$ parameter, in order to keep the number of iterations small. Additionally, our algorithm outputs an approximate DS by comparing vertex set sizes, while Bhattacharya et al. (STOC 2015) only proves an existence of some vertex sets that attain their approximation (their result presented in Corollary 6.7). These reflect some of the major differences between the algorithms that allow us to attain the new results in our paper."}, {"review_id": "G2coYw7MmM", "reviewer": "Reviewer_bSSJ", "summary": "This paper proposes new algorithms for approximating directed densest subgraphs in Massively Parallel Computation (MPC) and semi-streaming models. Specifically, in the MPC model, the paper provides a $(2+\\epsilon)$-approximation in $\\tilde{O}(\\sqrt{\\log n})$ rounds in the sublinear memory regime, which improves the best-known results and bridges the gap between the directed and undirected cases. In the semi-streaming model, the paper provides a (deterministic) $O(\\log n)$-approximation using a single pass, which is the first (deterministic) single-pass semi-streaming algorithm for this problem. Both algorithms are based on an elegant peeling-based algorithm, but its efficient implementation in MPC and streaming models are non-trivial, and involves several novel insights developed in this paper. Last but not least, the paper empirically evaluates the effectiveness of the proposed algorithms on several large real-world datasets.", "questions": "Q1: Algorithm 3 resets the vertex degree to 0 when it moves to a higher level, assuming the worst case. Could this be improved to achieve a better approximation under the assumption that the stream arrives in random order?\n\nQ2: Can the semi-streaming algorithm (i.e. Algorithm 3) be extended to work in dynamic streams, where both edge insertions and deletions are allowed?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1: Computing densest subgraphs in directed graphs is a fundamental problem and would be of interest to the NeurIPS community. The paper is clearly structured and very well written.\n\n2: The paper provides new algorithms in the MPC and semi-streaming models, improving upon the best-known results. The analyses are non-trivial, technically sound, and involve several novel insights.\n\n3: The paper conducts empirical evaluations on several large real-world networks, demonstrating the effectiveness and efficiency of the proposed algorithms.\n\nWeaknesses:\n\n1: The proposed semi-streaming algorithm appears to work only in insertion-only streams. It would strengthen the work to extend it to dynamic streams, which represent a more general setting.\n\n2: More comprehensive evaluations could be conducted in the experiments, e.g. the space usage of the algorithms.\n\n3: Some minor issues:\n\n-- Line 63: show -> shows\n\n-- Line 64: require -> requires\n\n-- In addition, it would be helpful to include a table summarizing existing results and the new results proposed in this paper for clearer comparison.", "was_revised": true, "final_justification": "NA", "rebuttal": "Thank you for the helpful suggestions. After receiving your feedback, we have executed additional experiments for MPC. Our additional experiments show that using less memory per machine slightly increases the number of rounds for our algorithm -- as expected -- but it is still significantly less than the number of rounds used by [BKV12]. The conference rules suggest we do not send a link to those plots, but we will include the plots in our revised version. Additionally, we will add a table of previous results to our final paper in order to allow for clearer comparisons. We also address the questions provided below:\n\nQ1: If the stream arrives in a random order, we would be able to leverage how sets of edges in the stream are uniform samples of the entire graph. MP24 already provides a result for this setting, though, attaining a $(2+\\epsilon)$-approximation using this random order stream property.\n\nQ2: Thank you for this excellent question! That is something we considered, but the ways of extending our algorithm to allow edge deletions makes it difficult to prove that the $O(\\log n)$-approximation still holds. For example, edge deletions should be able to decrease the level of a vertex, but then it is unclear how to set its degree within this lower level. Handling this by resetting the degree back to 0 would result in losing too much information about vertex’s neighbors. So, a different idea is necessary. This is one of the many complications that arise if we still want to maintain the simplicity of our semi-streaming algorithm. Nevertheless, we find this to be a fantastic direction for future work!"}, {"review_id": "a2ZWxz6AfF", "reviewer": "Reviewer_o9zx", "summary": "This paper presents new algorithms for finding approximate densest subgraphs in directed graphs within Massively Parallel Computation (MPC) and semi-streaming models. The proposed approaches achieve a $(2+\\varepsilon)$-approximation in $\\tilde{O}(\\sqrt{\\log n})$ MPC rounds with sublinear memory per machine and an $O(\\log n)$-approximation in a single pass in the semi-streaming setting, significantly improving upon prior results. Empirical evaluations demonstrate that the algorithms are efficient in practice, with the semi-streaming method achieving better-than-theoretical guarantees on temporal datasets and the MPC algorithm requiring fewer rounds than existing methods.", "questions": "Q1. Please add more experiments regarding the MPC case.\nQ2. Please add more explaination regarding the proposed algorithms to improve the readability.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "S1. The paper introduces novel algorithms for the directed densest subgraph problem that significantly improve upon existing methods, particularly in the Massively Parallel Computation and semi-streaming models, offering better approximation guarantees and efficiency.\nS2. It provides strong theoretical results, including a $(2+\\varepsilon)$-approximation in $\\tilde{O}(\\sqrt{\\log n})$  MPC rounds and an $O(\\log n)$-approximation in a single pass for semi-streaming, which bridge the gap between directed and undirected densest subgraph problems.\nS3. The empirical evaluations show that the proposed algorithms perform well in practice, often exceeding theoretical expectations, especially in the semi-streaming context.\n\nW1. Some steps in Algorithm 2 involve complex sampling and degree-thresholding mechanisms, and the explanations—although sufficiently technical—could benefit from more intuitive discussion, especially regarding relation to graph sparsification and the effect of 'freezing' high-degree vertices.\nW2. Most experimental comparisons are offered for the semi-streaming algorithm. While this supports the main claims, the MPC algorithm’s empirical performance is only briefly mentioned and detailed results are relegated to the appendix, limiting the main-paper evidence for the MPC improvements.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns.", "rebuttal": "Thank you for the helpful suggestions. We address the suggestions provided below:\n\nQ1: We have executed additional experiments for MPC. Our additional experiments show that using less memory per machine slightly increases the number of rounds for our algorithm -- as expected -- but it is still significantly less than the number of rounds used by [BKV12]. The conference rules suggest we do not send a link to those plots, but we will include the plots in our final version.\n\nQ2: We do realize that Algorithm 2 involves technical tools, and we will add more intuitive explanations of these tools in the final version of the paper. In particular, we will expand more on the idea of “freezing” high-degree vertices and how that goes hand in hand with our sampling scheme."}, {"review_id": "gsLj2dO0vf", "reviewer": "Reviewer_jvHZ", "summary": "This paper studies the directed densest subgraph (DS) problem under the MPC model and the semi-streaming model. In this problem, given a directed graph $(V, E)$, the goal is to find subsets S, T of V that maximize $\\frac{|E(S, T)|}{\\sqrt{|S| \\cdot |T|}}$. The algorithms for both models are built on top of a simple \"base\" DS algorithm, which combines the standard iterated peeling procedure with a new stopping rule. In the MPC, the base algorithm is simulate via graph exponentiation. To apply the known simulation techniques, the authors design graph sparsification steps (e.g., freezing high-degree vertices and sampling edges) to control the neighborhood size of the graph. In semi-streaming, the authors make a key observation that the base algorithm can be simulated by maintaining a state vector recording how many peeling iterations each vertex survives. The MPC algorithm achieves $(2+\\varepsilon)$-approximation in $\\tilde{O}(\\sqrt{\\log n})$ rounds, using sublinear memory per machine. This matches the undirected bound and improves over the previous directed memory bound of $\\tilde{\\Theta}(n)$. The semi-streaming algorithm provides the first bound for arbitrary streams.", "questions": "1. It seems that the factor 2 in the (2+eps)-approximation MPC comes from the fact that the subgraph condition gives only 2-approximation. \n- Is this relates to the fact that to handle directed graph, this paper ''duplicates'' the vertices to produce an undirected bipartite graph? \n- Does the existing (1+eps)-approximation algorithm for *directed* graph use a similar subgraph condition?\n\n2. In the context of semi-streaming, for undirected DS, [EHW15] provide a single-pass algorithm that guarantees a $(1+\\varepsilon)$-approximation. The authors mention that their algorithm for directed DS can also be adapted to approximating the undirected DS. I assume this results in worse approximation factor compared to [EHW15], but do the authors observe any other advantage over them?", "limitations": "Yes, the limitations are clearly discussed. The authors also point out multiple potential future directions.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**:\n\n1. I like the general presentation of this paper: it starts with giving a simple ''base algorithm'' that is later used as a skeleton for both the MPC and the semi-streaming algorithm. \n\\\nAlthough most proofs are delayed to the appendix due to the page limit, I think the high-level ideas of both algorithms and analysis are explained clearly in the main body of the paper. When describing the algorithms the authors carefully discuss the intuition behind each ingredient of the algorithm. And when outlining the analysis, they detailedly explain how lemmas interlock with each other and together lead to the main result.\n\n2. While both algorithms are derived from the simple \"base algorithm\", lifting it to the MPC / semi-streaming settings involves ideas that feels nice and non-trivial.\n\n- In the MPC case, to apply the graph exponentiation technique for simulation, the authors carefully control the size of neighborhoods by designing steps to freeze high-degree vertices and sample edges appropriately.\n\n- In the semi-streaming case, I find the observation of reducing the simulation to computing a vertex-vector which records the peeling iteration for each vertex interesting. And I'm particularly surprised by how the algorithm contains a seemingly crude ''degree resetting'' procedure but still manage to achieve a log(n)-approximation.\n\n**Weakness**:\n\n- The main weakness that I can think of is both approximation factors achieved by this paper, $(2+\\epsilon)$ and $O(\\log n)$, can be a bit unsatisfying. However, as mentioned in the **Summary** above, these factors are already noteworthy improvements over states of the arts. So I find the contribution of this paper clear.", "was_revised": true, "final_justification": "I didn't have major questions previously. My questions were mostly for curiosity, and the authors' answers are satisfying. So I will maintain my score.", "rebuttal": "Thank you for your comments. We address the questions provided below:\n\n1. The factor of 2 in the approximation purely comes from the subgraph condition and is not related to the duplication of vertices to produce an undirected bipartite graph. The existing $(1+\\epsilon)$-approximation algorithms do not use a similar subgraph condition. [EHW15] entirely uses one large uniform sample of the graph in order to approximate the directed DS. [BGM14] uses a technique called the multiplicative weights update method to approximately solve the directed DS LP. Both of these $(1+\\epsilon)$-approximation algorithms use different techniques than our subgraph condition.\n\n2. Yes, our approximation factor would be $O(\\log n)$ compared to their $(1+\\epsilon)$. However, their algorithm uses $\\tilde{\\Theta}(n^{1.5})$ memory, which is more than our $\\tilde{O}(n)$ memory. So, their algorithm doesn’t fit within the memory constraints of the semi-streaming setting. Additionally, as mentioned in the paper, our algorithm is the first deterministic single-pass algorithm for approximating the undirected or directed DS as far as we know. These are the main advantages over [EHW15]."}, {"review_id": "piVjEyDGmR", "reviewer": "Reviewer_hKXC", "summary": "This paper studies the directed densest-subgraph (DS) problem in the Massively Parallel Computation (MPC) model and the streaming model. Let $n$ and $m$ be the numbers of vertices and edges of the input directed graph, respectively.\n\n- In the MPC model, the authors present a $\\tilde{O}(\\sqrt{\\log n})$-round algorithm that returns a $(2+\\epsilon)$-approximation while using sub-linear (i.e., $O(n^{\\delta})$ for some $\\delta<1$) memory per machine. This result improves previous works which needs either $\\Omega(\\log n)$ rounds or $\\tilde{\\Omega}(n)$ memory, but at the cost of a looser approximation ratio.\n- In the streaming model, this paper introduces the first single-pass deterministic streaming algorithm for directed DS on arbitrary streams. It uses $\\tilde{O}(n)$ memory and achieves an $O(\\log ⁡n)$-approximation.", "questions": "See \"weaknesses\"", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**: This is a theoretical paper. These results are well-motivated, and strengthen existing bounds in meaningful ways. Moreover, the paper is clearly structured and well written.\n\n**Weaknesses  and suggestions:** Please provide more specifics in the Introduction about the MPC algorithm, including the total number of machines used and the scheme used to partition the graph across them. In addition, I recommend adding two summary tables: one for existing MPC algorithms and another for streaming algorithms for tackling directed DS. Each table should list the key metrics for every algorithm (e.g., round complexity, memory per machine, and approximation ratio).", "was_revised": true, "final_justification": "This paper provides new algorithms with theoretical guarantees for the DS problem in the MPC setting and streaming setting. These results will be of interest to the theory and big-data processing communities. That said, I do not consider this paper a must-accept for an AI&ML-focused conference.", "rebuttal": "Thank you for your feedback. For the introduction about the MPC algorithm, we will mention that the total number of machines is $n$, the number of vertices in the graph, and the edges are arbitrarily partitioned across the machines. As for your suggestion on the tables, we agree that it would make comparisons with previous works more clear and will add them in the final version of our paper."}]

Author rebuttal:

Meta-review: This paper studies the densest subgraph problem for directed graphs in various big data models, achieving a $(2+\varepsilon)$-approximation in $\tilde{O}(\sqrt{\log n})$ MPC rounds and a $O(\log n)$-approximation in the semi-streaming model, i.e., using $\tilde{O}(n)$ space. By comparison, a previous work achieves $O(n^{1/6})$-approximation in the semi-streaming model. Although there were concerns about both the scale and the presentation of the experiments, all reviewers agreed that the theoretical results are interesting for both MPC and the streaming model. 

I believe the reviewer feedback has resulted in a number of actionable items that would improve the quality of the paper and thus I would encourage the authors to incorporate these comments to strengthen the potential impact of the work.
Decision: Accept (poster)