# Faster Streaming and Scalable Algorithms for
Finding Directed Dense Subgraphs in Large Graphs

Slobodan Mitrović UC Davis<EMAIL_ADDRESS>Theodore Pan UC Davis,
<EMAIL_ADDRESS>
###### Abstract

Finding dense subgraphs is a fundamental algorithmic tool in data mining,
community detection, and clustering. In this problem, one aims to find an
induced subgraph whose edge-to-vertex ratio is maximized.

We study the directed case of this question in the context of semi-streaming
and massively parallel algorithms. In particular, we show that it is possible
to find a $(2+\epsilon)$ approximation on randomized streams even in a single
pass by using $O(n\cdot{\rm poly}\log n)$ memory on $n$-vertex graphs. Our
result improves over prior works, which were designed for arbitrary-ordered
streams: the algorithm by Bahmani et al. (VLDB 2012) which uses $O(\log n)$
passes, and the work by Esfandiari et al. (2015) which makes one pass but uses
$O(n^{3/2})$ memory. Moreover, our techniques extend to the Massively Parallel
Computation model yielding $O(1)$ rounds in the super-linear and $O(\sqrt{\log
n})$ rounds in the nearly-linear memory regime. This constitutes a quadratic
improvement over state-of-the-art bounds by Bahmani et al. (VLDB 2012 and WAW
2014), which require $O(\log n)$ rounds even in the super-linear memory
regime.

Finally, we empirically evaluate our single-pass semi-streaming algorithm on
$6$ benchmarks and show that, even on non-randomly ordered streams, the
quality of its output is essentially the same as that of Bahmani et al. (VLDB
2012) while it is $2$ times faster on large graphs.

##  1 Introduction

Given a directed graph $G=(V,E)$, the directed _densest subgraph problem_ asks
to find two vertex subsets $S,T\subseteq V$ such that the number of edges from
$S$ to $T$ scaled by $\sqrt{|S|\cdot|T|}$ is maximized. When $S=T$, this
problem is equivalent to finding the densest subgraph in undirected graphs.
Dense subgraph discovery is a fundamental algorithmic tool in data mining
[KP05, WLFV+19, FLM22], community detection [CS10, HBG+14], spam detection
[LSIKK11, ZLZL16], fraud discovery [ZZY+17, RZZ+21], clustering [KKSZ11,
BM21], graph compression [BC08], and many other applications. Given its
importance, this problem has been studied in various computational settings,
including semi-streaming [BKV12, MTVV15, BHNT15], dynamic [ELS15, SW20],
distributed [SV19], and parallel [BKV12, GLM19], with the first study of its
undirected version dating back to the eighties [Gol84].

A directed densest subgraph can be found in polynomial time [Cha03]. However,
the corresponding algorithm solves a family of $O(|V|^{2})$ linear programs,
making it impractical for execution on large graphs. Nevertheless, much faster
approximation algorithms have been developed. For instance, there exists a
simple greedy algorithm running in near-linear time that yields a
$2+\varepsilon$ approximation for any arbitrary constant $\varepsilon>0$
[BKV12, Cha03]. The prevalence of large graphs has motivated researchers to
study the approximate densest subgraph problem in settings for processing big
data, such as _streaming_ and _massively parallel computation (MPC)_.

There has been a significant interest in designing semi-streaming algorithms
for finding dense subgraphs, e.g., [BKV12, EHW15, BHNT15, MTVV15] and
references therein. Esfandiari et al. [EHW15] designed a single-pass semi-
streaming algorithm for finding $(1+\varepsilon)$-approximate densest subgraph
in _undirected_ graphs. For $n$-vertex graph $G$, this algorithm uniformly at
random samples $O(n\cdot\log(n)/\varepsilon^{2})$ edges from $G$ in the
streaming fashion. The authors show that the densest subgraph in such a sample
is a $(1+\varepsilon)$-approximate densest subgraph in $G$. This sampling idea
fails in the context of directed graphs. To see that, consider the example in
Figure 1.

Figure 1: An illustration of why uniformly at random sampling applicable to
undirected fails in the context of directed densest subgraph.

In that example, the directed densest subgraph is the star, having density
$\Theta(\sqrt{n})$; each clique has density $\Theta(n^{0.499})$. However,
sampling $O(n\cdot\log n)$ edges from that graph will, in expectation, contain
only $O(n^{0.501})$ edges from the star, which is insufficient to recover the
densest subgraph in Figure 1. To alleviate this, [ELS15] propose a single-pass
semi-streaming algorithm that requires $O(n^{1.5}\operatorname{poly}\log n)$
memory. In another line of work, Bahmani et al. [BKV12], the memory
requirement is kept at $O(n\operatorname{poly}\log n)$ at the expense of
making $O(\log n)$ passes. It is unknown whether these techniques can be
extended to achieve the best of both worlds, i.e., a single pass and
$O(n\operatorname{poly}\log n)$ memory.

Finding dense subgraphs in MPC has also received significant attention. For
undirected graphs, the sampling strategy devised in [EHW15] for the streaming
setting readily transfers to an $O(1)$ MPC round algorithm in the near-linear
memory regime. For the sublinear memory regime, Bahmani et al. [BGM14]
developed an algorithm that in $O(\log(n)/\varepsilon^{2})$ rounds outputs a
$(1+\varepsilon)$ approximation. This was improved to $O(\sqrt{\log
n}\cdot\log\log n)$ rounds by Ghaffari et al. [GLM19]. However, state-of-the-
art algorithms for densest subgraphs have significantly higher round
complexity for directed than for undirected graphs. The works [BKV12] and
[BGM14] also design an algorithm for finding $(2+\varepsilon$)- and
$(1+\varepsilon)$-approximate densest subgraphs in directed graphs in
$O(\log(n)/\varepsilon)$ and $O(\log(n)/\varepsilon^{2})$ MPC rounds,
respectively. To the best of our knowledge, this is the most efficient MPC
approach, even for the super-linear memory regime, leaving a considerable gap
between the case of directed and undirected graphs: $O(\log n)$ vs. $O(1)$
round complexity. Given that many modern graphs are directed – examples
include Twitter and Instagram ” following ” relationships, networks of sent
emails, and even links on the Web – _it is natural to wonder whether faster
algorithms for finding directed densest subgraphs can be developed_.

###  1.1 Our contributions

As our first result, we make progress in the semi-streaming setting.

######  Result 1 (Theorem 4.8 rephrased).

Given an $n$-vertex graph, there exists a single-pass semi-streaming algorithm
that, with high probability, over randomized streams outputs a
$(2+\varepsilon)$-approximate directed densest subgraph while using
$O(n\operatorname{poly}(\log(n)/\varepsilon))$ memory.

We build on ideas we develop for Result 1 and improve the state-of-the-art in
the context of MPC as well.

######  Result 2 (Theorems 5.1 and 5.2 summarized).

Given an $n$-vertex graph, there exists an MPC algorithm that, with high
probability, outputs a $(2+\varepsilon)$-approximate directed densest and

  * •

when the memory per machine is $n^{1+\delta}$ for an arbitrary constant
$\delta>0$, the algorithm runs in $O(1)$ rounds;

  * •

when the memory per machine is $n\operatorname{poly}(\log(n)/\varepsilon)$,
the algorithm runs in $O(\sqrt{\log n})$ rounds.

The fastest previously known MPC algorithms require $O(\log n)$ rounds even
when the memory per machine is $n^{1+\delta}$ [BKV12, BGM14]. So, our approach
makes significant progress toward closing the gap between the undirected and
directed cases.

Moreover, our empirical evaluations show that our semi-streaming algorithm is
at least $2$ times faster than Bahmani et al. [BKV12] while achieving
essentially the same accuracy. It is interesting to note that our algorithm is
by several percent more accurate than [BKV12] on large graphs. These hold even
when the underlying stream is non-randomized.

##  2 Preliminaries

#### Notation.

Given a directed graph $G=(V,E)$, we use $E_{G}$ to denote $E$, the set of
edges specific to graph $G$. We use $n$ to refer to $|V|$. Given two vertex
sets $S,T\subseteq V$, we refer to the edges between them by
$E_{G}(S,T)\stackrel{{\scriptstyle\mathclap{\tiny\mbox{def}}}}{{=}}\\{e=(i,j)\in
E_{G}:i\in S,j\in T\\}$. For the sake of brevity, for $i,j\in V$, we also
write
$E_{G}(i,T)\stackrel{{\scriptstyle\mathclap{\tiny\mbox{def}}}}{{=}}E_{G}(\\{i\\},T)$
and
$E_{G}(S,j)\stackrel{{\scriptstyle\mathclap{\tiny\mbox{def}}}}{{=}}E_{G}(S,\\{j\\})$.
Specific to streams, we use $E_{\rm{stream}}(S,T)$ to denote the subset of
$E_{G}(S,T)$ remaining in the stream. For vertex $v\in V$, we use
$d^{-}_{G}(v)$ to denote the in-degree and $d^{+}_{G}(v)$ to denote the out-
degree of $v$ in $G$.

When we say that an event $A$ happens _with high probability_ , or whp for
short, we imply that $\Pr\left[A\right]\geq 1-n^{-c}$, for a constant $c>0$.
In our algorithms, the constant $c$ can be made arbitrarily large by paying
constant factors in the pass/round or memory complexity.

#### Directed densest subgraph.

Given directed graph $G=(V,E)$ and vertex sets $S,T\subseteq V$, the density
$\rho(S,T)$ is defined as
$\rho(S,T)\stackrel{{\scriptstyle\mathclap{\tiny\mbox{def}}}}{{=}}|E_{G}(S,T)|/\sqrt{|S|\cdot|T|}$.
A densest subgraph is sets $S^{*}$, $T^{*}$ such that
$(S^{*},T^{*})\in\arg\max_{S,T\subseteq V}\rho(S,T)$.

#### Semi-streaming.

In the semi-streaming model, an algorithm scans input data, e.g., scans edge
by edge of an input graph. After all the edges are scanned, we say that the
algorithm made a _pass_. When the edges of the graph are presented to the
algorithm in a random permutation, we say that the stream is _randomized_.
Throughout the process, for $n$-vertex graph, the algorithm is typically
allowed to use $O(n\operatorname{poly}\log n)$ memory. The complexity measure
in this setup is the number of passes the algorithm makes and the memory it
requires; as discussed for [EHW15], some approaches require polynomially more
than memory $n$. After all the passes are performed, the algorithm outputs a
solution.

#### Massively Parallel Computation (MPC).

The Massively Parallel Computation (MPC) model has become a standard in the
theoretical study of practical large-scale frameworks [KSV10, GSZ11, BKS17]
such as MapReduce, Hadoop, Spark, and Flume. In MPC, the computation is
performed in synchronous rounds across $N$ machines. Each machine has $S$
words of memory. Originally, input data is partitioned arbitrarily across the
machines. During a round, each machine performs computation on its data
locally. At the end of a round, machines exchange messages. The communication
topology among the machines is a clique. During a round, a machine can, in
total, send (receive) at most $S$ bits of data. There are three important
memory regimes with respect to $S$ relative to data size. Let the input be an
$n$-vertex graph, and let $\delta\in(0,1)$ be an arbitrary constant: _sub-
linear_ corresponds to $S=n^{\delta}$; _near-linear_ corresponds to
$S=n\operatorname{poly}\log n$; and, $S=n^{1+\delta}$ corresponds to _super-
linear_.

#### Probability tools.

In our analysis, we extensively apply the following well-known tool from
probability.

######  Theorem 2.1 (Chernoff bound).

Let $X_{1},\ldots,X_{k}$ be independent random variables taking values in
$[0,1]$. Let $X\stackrel{{\scriptstyle\text{\tiny\rm
def}}}{{=}}\sum_{i=1}^{k}X_{i}$ and $\mu\stackrel{{\scriptstyle\text{\tiny\rm
def}}}{{=}}\mathbb{E}\left[X\right]$. Then,

  1. (A)

For any $\delta\in[0,1]$ it holds $\Pr\left[|X-\mu|\geq\delta\mu\right]\leq
2\exp\left(-\delta^{2}\mu/3\right)$.

  2. (B)

For any $\delta\in[0,1]$ it holds
$\Pr\left[X\geq(1+\delta)\mu\right]\leq\exp\left(-\delta^{2}\mu/3\right)$.

##  3 The Base Algorithm

Let $c$ be a value such that there exists a densest subgraph $(S,T)$ in $G$
and $c=|S|/|T|$. The starting point of our approach is a classical peeling
algorithm for the directed densest subgraph problem. This method receives $c$
as input and iteratively “peels”, i.e., removes, vertices that are below a
certain degree threshold. Intuitively, the peeling is performed so that the
removed vertices do not significantly affect the densest subgraph. We make
this statement formal by Theorem 4.3. One iteration of this peeling primitive
is given by VSets-Update(Algorithm 1).

Algorithm 1 (VSets-Update)

Input: $G=(V,E)$, $c>0$, $\epsilon\in(0,1)$, and vertex sets $S$, $T$

1:if $|S|/|T|\geq c$ then

2: $A(S)\leftarrow\\{i\in S:|E(i,T)|\leq(1+\epsilon)\frac{|E(S,T)|}{|S|}\\}$

3: $S\leftarrow S\backslash A(S)$

4:else

5: $B(T)\leftarrow\\{j\in T:|E(S,j)|\leq(1+\epsilon)\frac{|E(S,T)|}{|T|}\\}$

6: $T\leftarrow T\backslash B(T)$

7:end if

8:return $(S,T)$

By iteratively peeling and keeping track of the vertex sets that produce the
densest subgraph, we are able to find an approximation of the directed densest
subgraph. VSets-Updatehas two handy features. The first one is that, given two
sets $S$ and $T$, it reduces the size of one of them by $1+\varepsilon$.

######  Lemma 3.1.

Let $G=(V,E)$ be a directed graph. For $i\geq 0$, let $(S_{i},T_{i})$ be a
sequence of set-pairs such that $(S_{0},V_{0})=(V,V)$ and
$(S_{i+1},T_{i+1})=\textsc{VSets-Update}\xspace(G,c,\epsilon,S_{i},T_{i})$.
Then $S_{t}=\emptyset$ or $T_{t}=\emptyset$ for some $t\in
O(\log(n)/\epsilon)$.

###### Proof.

Consider VSets-Updateinvoked with $|S_{i}|/|T_{i}|\geq c$, so vertices are
removed from $S_{i}$. Then, all vertices $u\in S_{i}\backslash A(S_{i})$
satisfy $|E(u,T)|>(1+\epsilon)\frac{|E(S_{i},T_{i})|}{|S_{i}|}$. Since
$S_{i+1}=S_{i}\backslash A(S_{i})$, we have that
$|S_{i+1}|<|S_{i}|/(1+\epsilon)$. Similarly, if $|S_{i}|/|T_{i}|<c$, we have
that $|T_{i+1}|<|T_{i}|/(1+\epsilon)$. So, the size of one of the sets
decreases by at least $1+\epsilon$ times each time VSets-Updateis invoked.
Then, one of the sets becomes empty after
$O(\log_{1+\epsilon}n)=O(\log(n)/\varepsilon)$ invocations of VSets-Update. ∎

The second useful feature of VSets-Updateis that one of the pairs
$(S_{i},T_{i})$, as defined in the statement of Lemma 3.1, is a
$(2+\epsilon)$-approximate densest subgraph. We prove such a statement in
Theorem 4.3.

##  4 $(2+\epsilon)$ Approximation in a Single Pass

###  4.1 A Multi-pass Sampling-based Algorithm

We modify the base algorithm to sample edges to determine which vertices to
peel, instead of using the entire graph for that. By sampling a sufficient
number of edges, the degrees of vertices in the sample are used to estimate
the degrees of vertices in the original graph. For each pass, Algorithm 2
creates a new sample of our graph to apply VSets-Updateto. In our analysis, we
extensively use the following threshold

$\xi\stackrel{{\scriptstyle\text{\tiny\rm def}}}{{=}}\frac{60\log
n}{\epsilon^{2}}.$ (1)

Algorithm 2 A semi-streaming directed densest subgraph algorithm

Input: $G=(V,E)$, $c>0$, and $\epsilon\in(0,1)$
Output: A $(2+\varepsilon)$-approximate directed densest subgraph

1:Initialize each of $S,T,S^{*},T^{*}$ to $V$

2:while $S\neq\emptyset$ and $T\neq\emptyset$ do

3: Let $H$ be a sample of $E_{G}(S,T)$ with each edge sampled independently
with probability
$\min\left\\{\frac{n\xi}{(1-\epsilon)|E_{G}(S,T)|},1\right\\}$

4: $(S,T)\leftarrow\textsc{VSets-Update}\xspace(H,c,\epsilon,S,T)$

5: if $\rho(S,T)>\rho(S^{*},T^{*})$ then

6: $S^{*}\leftarrow S,T^{*}\leftarrow T$

7: end if

8:end while

9:return $S^{*},T^{*}$

Before we begin analyzing Algorithm 2, we prove Lemma 4.1 as a tool that
connects the degrees of vertices of graph $G$ and sampled subgraph $H$.

######  Lemma 4.1.

Let $G=(V,E)$ be a graph, $\epsilon\in(0,1)$, and $p\in(0,1]$. Let $H$ be a
subgraph of $G$ that contains each edge of $G$ independently with probability
$p$. Then, for all $v\in G$, the following hold with probability
$1-\frac{1}{n^{3}}$: (i) if $d^{-}_{G}(v)\geq\xi/p$ then
$pd^{-}_{G}(v)\leq(1+\epsilon)d^{-}_{H}(v)$, (ii) if $d^{-}_{G}(v)<\xi/p$ then
$d^{-}_{H}(v)<2\xi$ (same claims hold for out-degrees $d^{+}_{G}(v)$ and
$d^{+}_{H}(v)$).

###### Proof.

Consider a vertex $v\in V$. Let $X$ be the random variable equal to
$d^{-}_{H}(v)$. Observe that $\mathbb{E}\left[X\right]=pd^{-}_{G}(v)$. Then,
if $d^{-}_{G}(v)\geq\xi/p$, we have

$\displaystyle\Pr(\mathbb{E}\left[X\right]\geq(1+\epsilon)X)$
$\displaystyle\leq$
$\displaystyle\Pr\left(\mathbb{E}\left[X\right]-X\geq\frac{\epsilon}{2}\mathbb{E}\left[X\right]\right)$
$\displaystyle\leq$ $\displaystyle
3\exp\left(-\epsilon^{2}\mathbb{E}\left[X\right]/12\right)$ $\displaystyle=$
$\displaystyle 3\exp\left(-\epsilon^{2}pd^{-}_{G}(v)/12\right)$
$\displaystyle\leq$ $\displaystyle 3\exp(-5\log(n))$ $\displaystyle=$
$\displaystyle\frac{3}{n^{5}}\leq\frac{1}{n^{4}}$

assuming $n\geq 3$, where we used the Chernoff bound, Theorem 2.1 (A), to
derive (4.1).

Now, if $d^{-}_{G}(v)<\xi/p$, we have

$\displaystyle\Pr\left(X\geq 2\xi\right)$ $\displaystyle\leq$
$\displaystyle\Pr\left(X-\mathbb{E}\left[X\right]\geq\xi\right)$
$\displaystyle\leq$
$\displaystyle\frac{3}{2}\exp(-\xi^{2}/(3\mathbb{E}\left[X\right]))$
$\displaystyle\leq$ $\displaystyle\frac{3}{2}\exp(-\xi/3)$ $\displaystyle\leq$
$\displaystyle\frac{1}{n^{4}}$

where (4.1) follows by the Chernoff bound.

Therefore, using the union bound, the claim holds with probability
$1-\frac{1}{n^{3}}$. The same proof applies to out-degrees. ∎

Now, using Lemma 4.1, we begin analyzing Algorithm 2.

######  Lemma 4.2.

Algorithm 2 uses $O\left(\frac{n\log^{2}(n)}{\epsilon^{3}}\right)$ memory with
probability $1-\frac{\log_{1+\epsilon}n}{n^{4}}$.

###### Proof.

By the Chernoff bound, Theorem 2.1 (B), every pass of Algorithm 2 samples
$O\left(\frac{(1+\epsilon)n\xi}{(1-\epsilon)}\right)=O\left(\frac{n\log
n}{\epsilon^{2}}\right)$ edges with probability $1-\frac{1}{n^{4}}$. From
Lemma 3.1, the algorithm makes $O(\log_{1+\epsilon}n)$ passes. Therefore, by
the union bound over all the passes, the total memory used by Algorithm 2 is
$O\left(n\xi\cdot\log_{1+\epsilon}n\right)=O\left(\frac{n\log^{2}n}{\epsilon^{3}}\right)$
with probability $1-\frac{\log_{1+\epsilon}n}{n^{4}}$. ∎

######  Theorem 4.3.

Algorithm 2 produces a $2\left(1+\epsilon\right)$-approximation of the densest
directed subgraph with probability $1-\frac{\log_{1+\epsilon}n}{n^{2}}$.

###### Proof.

Consider a pass with $|S|/|T|\geq c$. Hence, vertices are removed from $S$ in
that pass. Let $p=n\xi/((1-\epsilon)|E_{G}(S,T)|)$; the same probability is
used on 3 of Algorithm 2. Then, for all vertices $i\in A(S)$, where $A(S)$ is
defined in VSets-Update, we have

$\displaystyle\sqrt{c}|E_{G}(i,T)|$ $\displaystyle\leq$
$\displaystyle\sqrt{c}\cdot\frac{(1+\epsilon)^{2}|E_{H}(S,T)|}{p|S|}$ (4)
$\displaystyle\leq$
$\displaystyle\sqrt{c}\cdot\left(1+\epsilon\right)^{3}\frac{|E_{G}(S,T)|}{|S|}$
(5) $\displaystyle\leq$
$\displaystyle\sqrt{c}\cdot\left(1+\epsilon\right)^{3}\frac{|E_{G}(S,T)|}{\sqrt{c|S||T|}}$
(6) $\displaystyle=$
$\displaystyle\left(1+\epsilon\right)^{3}\frac{|E_{G}(S,T)|}{\sqrt{|S||T|}}$
$\displaystyle=$ $\displaystyle\left(1+\epsilon\right)^{3}\rho(S,T).$

For (4), we either have that $|E_{G}(i,T)|\geq\xi/p$ or $|E_{G}(i,T)|<\xi/p$.
If $|E_{G}(i,T)|\geq\xi/p$, we use Lemma 4.1 to get

$\displaystyle\sqrt{c}|E_{G}(i,T)|$ $\displaystyle\leq$
$\displaystyle\sqrt{c}\cdot\frac{(1+\epsilon)|E_{H}(i,T)|}{p}$
$\displaystyle\leq$
$\displaystyle\sqrt{c}\cdot\frac{(1+\epsilon)^{2}|E_{H}(S,T)|}{p|S|}.$

On the other hand, if $|E_{G}(i,T)|<\xi/p$, (4) follows directly.
Additionally, since $\mathbb{E}\left[|E_{H}(S,T)|\right]=p|E_{G}(S,T)|$, a
direct application of Chernoff bound, Theorem 2.1 (B), yields (5).

Similarly, for a pass with $|S|/|T|<c$, we have that for all vertices $j\in
B(T)$,

$\frac{1}{\sqrt{c}}|E_{G}(S,j)|\leq\left(1+\epsilon\right)^{3}\rho(S,T).$ (7)

We define $d_{\rm out}^{\rm rem}(i)\stackrel{{\scriptstyle\text{\tiny\rm
def}}}{{=}}|E_{G}(i,T)|$ and $d_{\rm in}^{\rm
rem}(j)\stackrel{{\scriptstyle\text{\tiny\rm def}}}{{=}}|E_{G}(S,j)|$ where
$T$ is the respective set during the pass $i$ is removed from $S$ and,
similarly, $S$ is the respective set during the pass $j$ is removed from $T$.
Let $d_{out}^{*}=\max_{i\in V}\\{d_{\rm out}^{\rm rem}(i)\\}$ and
$d_{in}^{*}=\max_{j\in V}\\{d_{\rm in}^{\rm rem}(j)\\}$. Then, for
$\tilde{S},\tilde{T}\subseteq V$ with $|\tilde{S}|/|\tilde{T}|=c$ that
maximizes $\rho(\tilde{S},\tilde{T})=\rho^{*}(G)$, we have that

$\displaystyle\rho^{*}(G)$ $\displaystyle=$
$\displaystyle\frac{|E(\tilde{S},\tilde{T})|}{\sqrt{|\tilde{S}||\tilde{T}|}}\leq\frac{|\tilde{S}|\cdot
d_{out}^{*}+|\tilde{T}|\cdot d_{in}^{*}}{\sqrt{|\tilde{S}||\tilde{T}|}}$ (8)
$\displaystyle=$ $\displaystyle\sqrt{c}\cdot
d_{out}^{*}+\frac{1}{\sqrt{c}}\cdot d_{in}^{*}\leq
2\left(1+\epsilon\right)^{3}\rho(S^{*},T^{*})$

where (8) comes from using (6) and (7). (The last chain of inequalities is
also shown in [Cha03].)

Therefore, the algorithm produces a
$2\left(1+\epsilon\right)^{3}$-approximation. Note that we use Lemma 4.1 on
each vertex for every pass. Therefore, by the union bound, we have a success
probability of
$1-n\cdot\log_{1+\epsilon}n\cdot\frac{1}{n^{3}}=1-\frac{\log_{1+\epsilon}n}{n^{2}}$.
∎

###  4.2 Improved Single-pass Algorithm

Building on Algorithm 2, we develop a single-pass semi-streaming algorithm for
$(2+\varepsilon)$-approximate directed densest subgraph when the stream of
edges is randomized. The main idea behind our algorithm is to leverage the
additional randomization of the stream and avoid performing a new pass to
estimate vertex degrees when $S$ or $T$ gets updated; these degrees are needed
to execute 2 and 5 of VSets-Update.

Let $(S^{\prime},T^{\prime})=\textsc{VSets-
Update}\xspace(H,c,\varepsilon,S,T)$. Observe that $|E(u,T^{\prime})|$ and
$|E(S^{\prime},v)|$, for $u\in S^{\prime}$ and $v\in T^{\prime}$, can be
estimated by uniformly at random sampling $O(n\xi)$ edges from
$E(S^{\prime},T^{\prime})$. _How can those edges be sampled without performing
a new pass?_ If our algorithm has not already seen any edge in
$E(S^{\prime},T^{\prime})$ from the stream, this task would be easy – collect
edges in $E(S^{\prime},T^{\prime})$ from the stream as long as fewer than the
desired many are seen. However, our algorithm already has a subset
$E^{\prime}$ of $E(S^{\prime},T^{\prime})$ in its memory, which should be
considered. Assuming that the sampling probability is known – which is not
known and we discuss it in a moment – then Set-Sample(Algorithm 3) outputs the
desired sample while considering $E^{\prime}$.

Algorithm 3 (Set-Sample)

Input: A set of edges $E^{\prime}\subseteq E_{G}(S,T)$, vertex sets $S$ and
$T$, probability $p$, an estimate $s$ of $|E_{G}(S,T)|$ Output: Uniformly
random sample of edges from the union of the stream and $E^{\prime}$

1:Let $H_{1}$ be a subset of $E^{\prime}$, where each in $E^{\prime}$ is
included in $H_{1}$ with probability $p$.

2:Sample $x$ from the binomial distr. $B(s-|E^{\prime}|,p)$.

3:Set $H_{2}$ to next $x$ edges in $E_{G}(S,T)$ from the stream.

4:return $H_{1}\cup H_{2}$

Set-Sampleas input takes value $p$ where, ideally, $p=n\xi/|E(S,T)|$.
Unfortunately, $|E(S,T)|$ is not known; Set-Samplehas access to
$E^{\prime}\subseteq E(S,T)$ but $E_{\rm{stream}}(S,T)=E(S,T)\setminus
E^{\prime}$ is in the rest of the stream still unseen by the algorithm. To
alleviate this, our algorithm _approximates_ $|E(S,T)|$. By using Set-Sample,
this enables generating samples of the $E(S,T)$ sequence without going through
the entire stream each time. In doing so, we are able to create Algorithm 4,
which uses only a single pass.

Algorithm 4 A single-pass randomized-stream directed densest subgraph
algorithm

Input: $c>0$, and $\epsilon\in(0,1)$
Output: A $(2+\varepsilon)$-approximate directed densest subgraph

1:Initialize each of $S,T,S^{*},T^{*}$ to $V$

2:$E^{\prime}\leftarrow\emptyset$$\triangleright$ The subset of $E_{G}(S,T)$
seen so far

3:while $E_{\rm{stream}}\neq\emptyset$ do

4: $E_{A}\leftarrow$ next $n\xi$ edges from $E_{\rm{stream}}$

5: if $|E_{A}(S,T)|<2\xi$ or $E_{\rm{stream}}=\emptyset$ then

6: $E^{\prime}\leftarrow E^{\prime}\cup E_{A}(S,T)\cup E_{\rm{stream}}(S,T)$

7: If the densest subgraph in $E^{\prime}$ is denser than $(S^{*},T^{*})$,
update $(S^{*},T^{*})$ to be that subgraph.

8: else$\triangleright$ Estimate of $|E_{G}(S,T)|$ based on $E_{A}$.

9:
$s\leftarrow(1-\epsilon)\cdot\frac{|E_{A}(S,T)|}{|E_{A}|}\cdot\left(|E_{\rm{stream}}|+n\xi\right)+|E^{\prime}|$

10: $E^{\prime}\leftarrow E^{\prime}\cup E_{A}(S,T)$

11: $p\leftarrow\frac{n\xi}{(1-\epsilon)s}$

12: $H\leftarrow\textsc{Set-Sample}\xspace\left(E^{\prime},S,T,p,s\right)$

13: if $p>1$ then

14: $H\leftarrow E^{\prime}\cup E_{\rm{stream}}(S,T)$

15: end if

16: $(S,T)\leftarrow\textsc{VSets-Update}\xspace(H,c,\epsilon,S,T)$

17: if $\rho(S,T)>\rho(S^{*},T^{*})$ then

18: $S^{*}\leftarrow S,T^{*}\leftarrow T$

19: end if

20: $E^{\prime}\leftarrow(E^{\prime}\cup E_{H})\cap E_{G}(S,T)$

21: end if

22:end while

23:return $S^{*},T^{*}$

Notice that $E_{A}$ in Algorithm 4 is a sample of $n\xi$ edges taken uniformly
at random from _the rest_ of the stream. Additionally, graph $H$ uses Set-
Sampleto create an approximately uniform sample of edges from graph $E(S,T)$.
In both cases, the edges of the samples are not chosen independently, so the
standard Chernoff bound cannot be applied. Therefore, to still establish some
connection between the degrees of vertices of the sampled graphs and the
original graph, we consider Lemma 4.4, a generalized version of the Chernoff
bound which holds for negatively correlated variables. Boolean random
variables $X_{1},X_{2},\ldots,X_{n}$ are negatively correlated if any subset
$S$ of $\\{X_{1},X_{2},\ldots,X_{n}\\}$ and any element $a\in S$ follows
$\Pr(a=1|\forall_{b\in S-\\{a\\}}b=1)\leq\Pr(a=1)$.

######  Lemma 4.4 (Folklore).

Let $X=\sum_{i=1}^{n}X_{i}$ where $X_{1},X_{2},\ldots X_{n}$ are negatively
correlated boolean random variables. Then, for $\epsilon\in(0,1)$, we have
that

$\Pr(|X-\mathbb{E}\left[X\right]|>\epsilon\mathbb{E}\left[X\right])\leq
3\exp(-\epsilon^{2}\mathbb{E}\left[X\right]/3).$

With Lemma 4.4, we prove Lemma 4.5, which considers sampling using Set-Sample,
and Lemma 4.6, which considers sampling a fixed amount of edges uniformly at
random. These lemmas will be used to analyze Algorithm 4.

######  Lemma 4.5.

Let $G=(V,E)$ be a graph, $\epsilon\in(0,1)$, and $p\in(0,1]$. Let
$H\leftarrow\textsc{Set-Sample}\xspace\left(E^{\prime},S,T,p,s\right)$ be
obtained on 12 of Algorithm 4. Then, for all $v\in G$, the following hold with
probability $1-\frac{1}{n^{3}}$: (i) if $d^{-}_{G}(v)\geq\xi/p$ then
$pd^{-}_{G}(v)\leq(1+\epsilon)d^{-}_{H}(v)$, (ii) if $d^{-}_{G}(v)<\xi/p$ then
$d^{-}_{H}(v)<2\xi$ (same claims hold for out-degrees $d^{+}_{G}(v)$ and
$d^{+}_{H}(v)$).

###### Proof.

Consider a sample $H$ of $G$ obtained by Set-Sample. Number the edges in $E$
from $1$ to $m=|E|$. For each $i=1\ldots m$, define a Boolean random variable
$X_{i}$ which equals $1$ iff $i\in H$ and $0$ otherwise.

Let $S$ be an arbitrary subset of $\\{X_{1},X_{2},\ldots,X_{m}\\}$ and $X_{i}$
be an arbitrary element of $S$. Recall that Set-Sampleuses two sets to output
$H$: one is the input set $E^{\prime}$, and the other one is the rest of the
stream $E_{\rm{stream}}$. To sample from $E_{\rm{stream}}$, Set-Samplefirst
samples $x$ on 2, and then fetches the next $x$ edges from
$E_{\rm{stream}}\cap E_{G}(S,T)$; hence, that edge-sample is correlated as the
number of edges is fixed. If $i\in E^{\prime}$, then $X_{i}$ is independent of
all the other random variables, and therefore, $\Pr(X_{i}=1|\forall_{b\in
S-\\{X_{i}\\}}b=1)=\Pr(X_{i}=1)$. If $i\in E_{\rm{stream}}$ instead, we
observe that if the sample already contains an edge $j$, then it “reduces” the
probability of $i$ appearing in $H$. Overall, the random variables are
negatively correlated.

Now, under the conditions of our lemma, we have that $p\leq 1$. So, when we
use Set-Sample, we see that

$\displaystyle\mathbb{E}\left[d^{-}_{H}(v)\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\frac{p\cdot s}{|E_{G}(S,T)|}\cdot
d^{-}_{G}(v)\right]$ $\displaystyle=$
$\displaystyle\frac{n\xi}{(1-\epsilon)|E_{G}(S,T)|}d^{-}_{G}(v)$

since Set-Sample, in expectation, samples $ps$ edges out of all the edges in
$E_{G}(S,T)$. Notice that the result is the same as
$\mathbb{E}\left[d^{-}_{H}(v)\right]$ in Lemma 4.1. Therefore, following the
proof of Lemma 4.1 but using Lemma 4.4 instead of the Chernoff bound, we prove
Lemma 4.5. ∎

######  Lemma 4.6.

Let $G=(V,E)$ be a graph, $\epsilon\in(0,1)$. Assuming $|E|\geq n\xi$, let $H$
be a sample of $n\xi$ edges from $G$ chosen uniformly at random with
probability $p=\frac{n\xi}{|E|}$. Then, for all $v\in G$, the following hold
with probability $1-\frac{1}{n^{3}}$: (i) if $d^{-}_{H}(v)\geq 2\xi$ then
$|d^{-}_{H}(v)-pd^{-}_{G}(v)|\leq\epsilon d^{-}_{H}(v)$, (ii) if
$d^{-}_{H}(v)<2\xi$ then $d^{-}_{G}(v)\leq\frac{2(1+\epsilon)\xi}{p}$ (same
claims hold for out-degrees $d^{+}_{G}(v)$ and $d^{+}_{H}(v)$).

###### Proof.

Note that we can apply Lemma 4.4 since we perform uniform random sampling with
a fixed number of edges. Therefore, when referencing Lemma 4.1 in this proof,
it will be using Lemma 4.4 instead of the Chernoff bound in the context of
uniform random sampling with a fixed number of edges.

Consider a vertex $v\in V$. Note that if $d^{-}_{H}(v)\geq 2\xi$, then
$d^{-}_{G}(v)\geq\xi/p$ with probability $1-\frac{1}{n^{4}}$ using the
Chernoff bound. Therefore, with Lemma 4.1, we have that
$|d^{-}_{H}(v)-pd^{-}_{G}(v)|\leq\epsilon d^{-}_{H}(v)$.

If $d^{-}_{H}(v)<2\xi$, we split our analysis into two cases. If
$d^{-}_{G}(v)\geq\xi/p$, then

$d^{-}_{G}(v)\leq\frac{(1+\epsilon)d^{-}_{H}(v)}{p}<\frac{2(1+\epsilon)\xi}{p}$

using Lemma 4.1. Otherwise, if $d^{-}_{G}(v)<\xi/p$, then
$d^{-}_{G}(v)<\frac{2(1+\epsilon)\xi}{p}$ holds as well. Therefore, the
statements in Lemma 4.6 hold with probability $1-\frac{1}{n^{3}}$ using the
union bound. The same proof applies to out-degrees. ∎

The following is our analysis of Algorithm 4.

######  Lemma 4.7.

Algorithm 4 uses $O\left(\frac{n\log^{2}n}{\epsilon^{3}}\right)$ memory with
probability $1-\frac{\log_{1+\varepsilon}n}{n^{4}}$.

###### Proof.

First, note that our algorithm takes $O(\log_{1+\epsilon}n)$ iterations.

For the graph $H$, we either have $p\leq 1$ or $p>1$. If $p\leq 1$, we create
a sample of edges with probability $\frac{n\xi}{(1-\epsilon)s}$ using Set-
Sample. Note that $s$ is an approximation of $|E_{G}(S,T)|$ where, with
probability $1-\frac{1}{n^{4}}$, it holds

$s\leq|E_{G}(S,T)|\leq\frac{1+\epsilon}{1-\epsilon}\cdot s$ (9)

using the Chernoff bound, Theorem 2.1 (A). So, for each of the
$O(\log_{1+\epsilon}n)$ iterations, graph $H$ will have
$O\left(\frac{(1+\epsilon)^{2}n\log
n}{\epsilon^{2}(1-\epsilon)^{2}}\right)=O\left(\frac{n\log
n}{\epsilon^{2}}\right)$ edges with probability $1-\frac{1}{n^{4}}$ and
$\epsilon<0.9$. On the other hand, if $p>1$, we must have that

$(1-\epsilon)s<n\xi\implies|E_{G}(S,T)|<\frac{(1+\epsilon)n\xi}{(1-\epsilon)^{2}}$

with probability $1-\frac{1}{n^{4}}$ using (9). Then, in this case, graph $H$
will also have $O\left(\frac{n\log n}{\epsilon^{2}}\right)$ edges.

Note that $E^{\prime}$ only increases by at most $n\xi$ edges each iteration
in addition to edges from graph $H$. Therefore, using the union bound, the
number of edges in $E^{\prime}$ at any point in time is at most
$O\left(\frac{n\log
n\cdot\log_{1+\epsilon}n}{\epsilon^{2}}\right)=O\left(\frac{n\log^{2}n}{\epsilon^{3}}\right)$
with probability $1-\frac{\log_{1+\epsilon}n}{n^{4}}$.

Now, $E_{A}$ is either a uniform random sample of $n\xi$ edges from the
remaining edges in the stream, since the stream is randomized, or is the rest
of the stream. If it is the rest of the stream, then our algorithm reduces to
finding the densest subgraph in $E^{\prime}\cup E_{A}(S,T)$. This uses at most
$O\left(\frac{n\log^{2}n}{\epsilon^{3}}\right)$ memory. However, if $E_{A}$ is
not the rest of the stream, then either $|E_{A}(S,T)|<2\xi$ or
$|E_{A}(S,T)|\geq 2\xi$.

If $|E_{A}(S,T)|<2\xi$, then we add the edges from $E_{A}(S,T)$ and
$E_{\rm{stream}}(S,T)$ to $E^{\prime}$ and find the densest subgraph in
$E^{\prime}$. Using Lemma 4.6, at most $\frac{2(1+\epsilon)\xi}{p}\leq
2(1+\epsilon)n$ edges, where $p=\frac{n\xi}{|E_{\rm{stream}}(S,T)\cup
E_{A}(S,T)|}$, are added to $E^{\prime}$ from $E_{A}$ and the stream. This
uses $O\left(\frac{n\log^{2}n}{\epsilon^{3}}\right)$ memory.

If $|E_{A}(S,T)|\geq 2\xi$, then we have that the number of edges from
$E_{G}(S,T)$ that were in the stream is at least
$\frac{s(1-\epsilon)|E_{A}(S,T)|}{|E_{A}|}$ using Lemma 4.6, allowing us to
calculate $s^{\prime}$ for creating graph $H$.

Therefore, the total amount of memory used by the algorithm is
$O\left(\frac{n\log^{2}n}{\epsilon^{3}}\right)$. ∎

######  Theorem 4.8.

Algorithm 4 produces a $2\left(1+\epsilon\right)$-approximation of the densest
directed subgraph with probability $1-\frac{\log_{1+\epsilon}n}{n^{2}}$.

###### Proof.

The pruning of vertices in our algorithm follows that of Algorithm 2, using
Set-Sampleto create sample graph $H$ and then applying VSets-Update.
Therefore, following the proof of Theorem 4.3 but using Lemma 4.5 instead of
Lemma 4.1, we attain the same approximation of the directed densest subgraph.
∎

###  4.3 Removing the assumption on $c_{\rm OPT}$ being known

Executing Algorithm 4 requires knowing $c_{\rm OPT}$, the ratio between the
two optimal sets. We remove this assumption by using standard techniques.
Namely, it is unclear how to learn $c$ without finding the densest subgraph.
To alleviate this, our algorithm guesses the value of $c$ and runs the
algorithm described above for each guess. Since there are $O(n^{2})$
candidates for $c$, i.e., values $a/b$ for $a,b\in\\{1,\ldots,n\\}$, our
algorithm guesses the value of $c$ in the multiplicative increments of
$\delta>1$. More precisely, we run our algorithm for values of $c$ ranging
from $1/n$ to $n$ and of the form $\delta^{i}/n$. As Lemma 4.9 shows, this
approach incurs an additional factor of $\sqrt{\delta}$ in our approximation.

######  Lemma 4.9.

The best density of Algorithm 4 ran on values of $c=1/n$ through $n$,
multiplying by a constant factor of $\delta$, is a
$2(1+\epsilon)\sqrt{\delta}$-approximation of the densest directed subgraph
with probability $1-\frac{\log_{1+\epsilon}n}{n^{2}}$.

###### Proof.

Consider $c$ where $c_{\rm OPT}/\delta\leq c\leq\delta c_{\rm OPT}$. Drawing
from the proof of Theorem 4.3, consider $\tilde{S},\tilde{T}$ with
$|\tilde{S}|/|\tilde{T}|=c_{\rm OPT}$ that maximizes
$\rho(\tilde{S},\tilde{T})=\rho^{*}(G)$. Then,

$\displaystyle\rho^{*}(G)$ $\displaystyle=$
$\displaystyle\frac{|E(\tilde{S},\tilde{T})|}{\sqrt{|\tilde{S}||\tilde{T}|}}\leq\frac{|\tilde{S}|\cdot
d_{out}^{*}+|\tilde{T}|\cdot d_{in}^{*}}{\sqrt{|\tilde{S}||\tilde{T}|}}$
$\displaystyle=$ $\displaystyle\sqrt{c_{\rm OPT}}\cdot
d_{out}^{*}+\frac{1}{\sqrt{c_{\rm OPT}}}\cdot d_{in}^{*}$ $\displaystyle\leq$
$\displaystyle\sqrt{\delta c}\cdot d_{out}^{*}+\sqrt{\delta/c}\cdot
d_{in}^{*}$ $\displaystyle\leq$ $\displaystyle
2\left(1+\epsilon\right)^{3}\sqrt{\delta}\cdot\rho(S^{*},T^{*})$

Therefore, this gives a $2(1+\epsilon)\sqrt{\delta}$-approximation of the
densest directed subgraph. ∎

##  5 MPC Algorithms

In this section, we extend our approach developed in Section 4 to two memory
regimes of the MPC model. We present the ideas gradually. First, we show that
slightly adjusting Algorithm 4 yields an $O(1)$ MPC round algorithm in the
super-linear memory regime. To achieve this round complexity, we prove a
certain edge-size progress that was not required for the semi-streaming
analysis. Second, in Section 5.2 we show that, by further building on the MPC
super-linear memory algorithm, it is possible to find an approximate directed
densest subgraph in only $O(\sqrt{\log n})$ rounds in the near-linear memory
regime.

###  5.1 Super-linear Memory Regime

Recall that in Algorithm 4, $E_{\rm{stream}}$ is the _remaining_ edges in the
stream. In developing a super-linear regime MPC algorithm, our main idea is to
implement $E_{\rm{stream}}$ efficiently in MPC. More concretely, assume that a
machine $\mathcal{M}$ aims to simulate Algorithm 4. Then, $\mathcal{M}$ first
samples $n^{1+\delta}$ edges from the graph – let that set be $X_{1}$ – and
presents $X_{1}$ to Algorithm 4 as a prefix of $E_{\rm{stream}}$. Once
Algorithm 4 makes a pass over $X_{1}$, $\mathcal{M}$ needs to fetch another
set $X_{2}$ of $n^{1+\delta}$ edges from $E\setminus X_{1}$ and continue
Algorithm 4 with $X_{2}$. This process continues until there are edges to feed
to Algorithm 4; the samples $X_{1},X_{2},\ldots$ represent $E_{\rm{stream}}$.
Clearly, this simulation corresponds to Algorithm 4 executed on a stream.
Unfortunately, fetching sets $X_{i}$ can happen $m/n^{1+\delta}$ times, which
for $m\gg n^{1+\delta}$ is highly inefficient.

Our main idea is that after processing $X_{1}$, it suffices if $\mathcal{M}$
takes a random sample from $E_{G}(S,T)\cap(E_{\rm{stream}}\setminus X_{1})$ as
opposed from $E_{\rm{stream}}\setminus X_{1}$. The main question here is: “
_How does this translate to round complexity?_ ” As the primary measure of
progress, we show the following. Let $(S^{\prime},T^{\prime})$ be the vertex
set pair in Algorithm 4 just before our simulation of Algorithm 4 exhausted
$X_{1}$. Then, we show that, up to low-order terms,
$|E_{G}(S^{\prime},T^{\prime})|<m/n^{\delta}$. More generally, we show that
whenever our simulation needs to fetch fresh $X_{i}$ from the remaining unused
edges, the number of _relevant_ remaining edges reduces by a factor of
$n^{\delta}$. Hence, after $O(1/\delta)$ many such steps, the number of
remaining relevant edges fits in the memory of a single machine, at which
point the rest of the problem can be solved locally. We dive into the details
of this argument in our proof of the following claim.

######  Theorem 5.1.

There exists an algorithm that runs in $O(1/\delta)$ rounds with probability
$1-\frac{\log_{1+\epsilon}n}{n^{4}}$.

###### Proof.

We first describe the algorithm and then an analysis of its round complexity.

#### Algorithm description.

Let $\mathcal{A}_{\textsc{MPC}}$ be our MPC algorithm.

  * •

$\mathcal{A}_{\textsc{MPC}}$ maintains the set of _relevant_ edges, denoted by
$E_{\rm{rel}}$. Initially, $E_{\rm{rel}}=E_{G}$.

  * •

This algorithm simulates an instance of Algorithm 4, and only that instance.
Let the instance be simulated on a machine $\mathcal{M}$; the simulation
proceeds in phases as follows:

    * –

Let $(S_{i+1},T_{i+1})$ be the vertex sets of Algorithm 4 at the end of phase
$i$ of $\mathcal{A}_{\textsc{MPC}}$.

    * –

At the beginning of phase $i+1$, $\mathcal{A}_{\textsc{MPC}}$ updates
$E_{\rm{rel}}\leftarrow E_{\rm{rel}}\cap E_{G}(S_{i+1},T_{i+1})$.

    * –

Then, $\mathcal{A}_{\textsc{MPC}}$ places on $\mathcal{M}$ a set $X_{i+1}$ of
$n^{1+\delta}$ edges chosen uniformly at random from $E_{\rm{rel}}$ and
updates $E_{\rm{rel}}\leftarrow E_{\rm{rel}}\setminus X_{i+1}$.

    * –

The rest of phase $i+1$ consists of continuing the Algorithm 4 instance with
the set $X_{i+1}$.

  * •

$\mathcal{A}_{\textsc{MPC}}$ stops when $E_{\rm{rel}}$ fits entirely on
$\mathcal{M}$.

All the steps of $\mathcal{A}_{\textsc{MPC}}$, except updating $E_{\rm{rel}}$
and sampling $X_{i+1}$, are done on a single machine. Removing $X_{i}$ from
$E_{\rm{rel}}$ can be done by first sorting $E_{\rm{rel}}$ and $X_{i}$
together and then removing that edge that has a duplicate in the sorted list.
Sorting can be done in $O(1)$ rounds [GSZ11]. Performing $E_{\rm{rel}}\cap
E_{G}(S_{i+1},T_{i+1})$ can be done again by sorting $E_{\rm{rel}}$, $S_{i+1}$
and $T_{i+1}$ altogether. Those edges incident to $S_{i+1}$ or $T_{i+1}$ are
the only ones kept in $E_{\rm{rel}}$. To sample $X_{i+1}$, first, each edge in
$E_{\rm{rel}}$ samples a random integer in the range $[1,n^{8}]$. Whp, all the
integers sampled by the edges are distinct. Second, all the edges are sorted
with respect to the sampled integers; effectively, this creates a random
permutation of $E_{\rm{rel}}$. Third, the first $n^{1+\delta}$ edges in that
sorted list are $X_{i+1}.$

#### Algorithm analysis.

Consider a phase $i$ of $\mathcal{A}_{\textsc{MPC}}$ and let $(S_{i},T_{i})$
be our vertex sets before the pruning starts. Now consider some pair of vertex
sets $(S^{\prime},T^{\prime})$ while running Algorithm 4 during phase $i$. We
define $E_{\rm{rem}}$ as the union of $E_{\rm{rel}}$ and the remaining edges
in $X_{i}$ that the algorithm has not inspected so far. There are
$|E_{G}(S^{\prime},T^{\prime})|-|E^{\prime}|$ edges in
$E_{G}(S^{\prime},T^{\prime})$ remaining in $E_{\rm{rem}}$.

Algorithm 4 needs at most $\frac{2n\xi}{1-\epsilon}$ edges in
$E_{G}(S^{\prime},T^{\prime})$ from the stream in order to start peeling. Let
$k$ be the number of edges taken from the stream to perform one iteration of
peeling. Therefore, using the Chernoff bound, Theorem 2.1 (A), we see that

$k\leq\frac{2n\xi|E_{\rm{rem}}|}{(1-\epsilon)^{2}(|E_{G}(S^{\prime},T^{\prime})|-|E^{\prime}|)}.$

with probability $1-\frac{1}{n^{4}}$, assuming that
$|E_{G}(S^{\prime},T^{\prime})|-|E^{\prime}|$ is at least
$\Omega\left(n\log^{2}n/\epsilon^{2}\right)$. If
$|E_{G}(S^{\prime},T^{\prime})|-|E^{\prime}|$ is
$O\left(n\log^{2}n/\epsilon^{2}\right)$, then all the edges in $E_{\rm{rel}}$
for the next phase fit on $\mathcal{M}$.

Now, if $k\geq\frac{n^{1+\delta}}{2\log_{1+\epsilon}n}$, then we have that

$\displaystyle\frac{n^{1+\delta}}{2\log_{1+\epsilon}n}$ $\displaystyle\leq$
$\displaystyle\frac{2n\xi|E_{\rm{rem}}|}{(1-\epsilon)^{2}(|E_{G}(S^{\prime},T^{\prime})|-|E^{\prime}|)}$
$\displaystyle\implies|E_{G}(S^{\prime},T^{\prime})|$ $\displaystyle\leq$
$\displaystyle\frac{4\xi\log_{1+\epsilon}n}{(1-\epsilon)^{2}n^{\delta}}\cdot|E_{\rm{rem}}|+|E^{\prime}|.$

Recall from Lemma 4.7 that $E^{\prime}$ contains at most
$O\left(\frac{n^{\prime}\log^{2}n}{\epsilon^{3}}\right)$ edges. So, if
$|E_{\rm{rem}}|\leq|E^{\prime}|$, then in the next phase $E_{\rm{rel}}$ fits
entirely on $\mathcal{M}$. On the other hand, if
$|E_{\rm{rem}}|>|E^{\prime}|$, then whp $E_{G}(S^{\prime},T^{\prime})$ has
$O\left(\frac{\log^{2}n}{\epsilon^{3}n^{\delta}}\cdot|E_{\rm{rem}}|\right)$
edges for $\epsilon<0.9$. Therefore, since $E_{\rm{rem}}$ is a subset of
$E_{G}(S_{i},T_{i})$, this phase causes the number of edges between vertex
sets $S$ and $T$ to reduce by a factor of $\Omega(n^{\delta})$. Then,
$\mathcal{A}_{\textsc{MPC}}$ takes $O(1/\delta)$ rounds if every phase has at
least one pair of vertex sets with
$k\geq\frac{n^{1+\delta}}{2\log_{1+\epsilon}n}$.

Consider now that $k<\frac{n^{1+\delta}}{2\log_{1+\epsilon}n}$ for all pairs
of vertex sets in a phase. Observe that Algorithm 4 takes at most
$2\log_{1+\epsilon}n$ iterations, meaning that the entire algorithm will be
finished this phase entirely on $\mathcal{M}$.

Combining these two cases with respect to $k$, $\mathcal{A}_{\textsc{MPC}}$
takes $O(1/\delta)$ rounds. ∎

###  5.2 Near-linear Memory Regime

In this section, we improve the efficiency of our MPC algorithm for the super-
linear memory regime, enabling us to obtain a quadratically faster algorithm
for the near-linear memory regime than currently known [BKV12, BGM14]. Our
approach stems from two ideas. The first idea is an observation: instead of
sampling $n\xi$ edges, our algorithm requires sampling only
$(|S|+|T|)\cdot\xi$ edges. Hence, once $|S|+|T|$ become sufficiently small,
then the memory per machine becomes significantly larger than our sample
sizes, and we can use ideas similar to those from the proof of Theorem 5.1 to
improve the $O(\log n)$ round complexity. Unfortunately, this alone is not
sufficient. To see that, consider an example in which $|S|/|T|=\Theta(n)$,
e.g., the densest subgraph has a star-like structure. In that case, it is
potentially needed to peel $T$ for $O(\log n)$ times. Since
$|S|+|T|=\Theta(n)$ during those peeling steps, our observation does not yield
any improvement.

The second idea is that as long as our algorithm peels only $T$ or only $S$,
no fresh sampling is required. To elaborate, assume that the peeling process
produces sets $(S,T_{1}),(S,T_{2}),\ldots,(S,T_{j})$. Since $S$ remains the
same, the estimated degree between $S$ and a vertex $v\in T_{j}$ is the same
in all the sets $T_{1},T_{2},\ldots,T_{j}$. Hence, once $|E_{G}(S,v)|$ is
estimated, no new sample is needed until $S$ changes. In other words, the
star-like example we pointed to above can be handled with a single sample.
_Nevertheless, what does happen when $S$ changes?_ In that case, the algorithm
might need a new round to obtain a fresh sample. Fortunately, the size of $S$
reduces by at least a factor of $(1+\varepsilon)$, increasing the gap between
the memory per machine and $|S|+|T|$, which our algorithm utilizes in a way
similar to described in Section 5.1. We formalize these ideas in the proof of
the following claim.

######  Theorem 5.2.

There exists an algorithm that runs in $O(\sqrt{\log_{1+\epsilon}n})$ rounds
with probability $1-\frac{\log_{1+\epsilon}n}{n^{4}}$.

###### Proof.

Let $\mathcal{A}_{\textsc{MPC}}$ be the algorithm described in the proof of
Theorem 5.1. We extend $\mathcal{A}_{\textsc{MPC}}$ this algorithm to obtain
the desired round complexity. In this proof, we only describe the extension.

#### Algorithm description.

In a phase $i$, we calculate $E_{G}(u,T_{i})$ and $E_{G}(S_{i},v)$ for all
$u\in S_{i},v\in T_{i}$. Then, if $|S_{i}|/|T_{i}|\geq c$, we peel from set
$T$ using VSets-Updateuntil the resulting sets
$(S_{i}^{\prime},T_{i}^{\prime})$ satisfy
$|S_{i}^{\prime}|/|T_{i}^{\prime}|<c$. Similarly, if $|S_{i}|/|T_{i}|<c$, we
peel from set $S$ using VSets-Updateuntil the resulting sets
$(S_{i}^{\prime},T_{i}^{\prime})$ satisfy
$|S_{i}^{\prime}|/|T_{i}^{\prime}|\geq c$. Finally, we do what
$\mathcal{A}_{\textsc{MPC}}$ does every phase except that the edge samples now
have size $(|S|+|T|)\cdot\xi$.

#### Algorithm analysis.

Consider a phase $i$ of our algorithm and let $(S_{i},T_{i})$ be our vertex
sets before the peeling starts. Without loss of generality, assume that
$|S_{i}|/|T_{i}|\geq c$. Note that calculating the degrees of vertices and
peeling from set $T$ can all be done in a constant number of rounds.
Afterwards, we have that the resulting sets $(S_{i}^{\prime},T_{i}^{\prime})$
satisfy $|S_{i}^{\prime}|/|T_{i}^{\prime}|<c$. This guarantees that both
vertex sets are peeled from.

Now, let $n^{\prime}=|S_{i}^{\prime}|+|T_{i}^{\prime}|$. We consider some pair
of vertex sets $(S^{\prime},T^{\prime})$ while running Algorithm 4 during
phase $i$. With samples of $n^{\prime}\xi$ edges, we follow a similar proof of
Theorem 5.1 to see that if
$k\geq\frac{n\operatorname{poly}(\log(n)/\varepsilon)}{2\log_{1+\epsilon}n}$,
either $E_{\rm{rel}}$ fits entirely on $\mathcal{M}$ in the next phase or
$E_{G}(S^{\prime},T^{\prime})$ has
$O\left(\frac{n^{\prime}\log^{2}n}{\epsilon^{3}n\operatorname{poly}(\log(n)/\varepsilon)}\cdot|E_{\rm{rem}}|\right)$
edges. With the latter, the number of edges between vertex sets $S$ and $T$
reduces by a factor of
$x=\Omega\left(\frac{\epsilon^{3}n\operatorname{poly}\log
n}{n^{\prime}\log^{2}n}\right)$. Since both vertex sets are peeled from,
$n^{\prime}$ reduces by at least a factor of $1+\epsilon$ every phase. Then,
the algorithm takes $O(\sqrt{\log_{1+\epsilon}n})$ rounds if every phase has
at least one pair of vertex sets with
$k\geq\frac{n\operatorname{poly}(\log(n)/\varepsilon)}{2\log_{1+\epsilon}n}$
because $x$ reduces by at least a factor of $1+\epsilon$ every phase as well
due to $n^{\prime}$.

With $k<\frac{n\operatorname{poly}(\log(n)/\varepsilon)}{2\log_{1+\epsilon}n}$
for all pair of vertex sets in a phase, the entire algorithm can be finished
in this phase entirely on $\mathcal{M}$. So, the algorithm takes
$O(\sqrt{\log_{1+\epsilon}n})$ rounds. ∎

##  6 Experiments

We now demonstrate the practical performance of Algorithm 4, comparing it to
Algorithm $3$ from [BKV12].

###  6.1 Data

We use $4$ data sets from the Stanford Large Network Dataset Collection
([LK14]): Slashdot, Berkeley-Stanford Web Graph, LiveJournal, and Twitter. In
addition, we generate two synthetic graphs, PrefAttach $1$ and $2$, using the
preferential attachment scheme [Sim55]. This scheme is popular in the
scientific analysis of graphs as it can generate the power-law distribution
[BA99, JM15, WWDR17] and, as such, it models the vertex-degree distribution of
many important graphs, including World Wide Web [KBM13] and Wikipedia [CSC+06,
GCDA15].

Graph | Nodes | Edges
---|---|---
Slashdot | 82,168 | 948,464
Berk-Stan Web | 685,230 | 7,600,595
LiveJournal | 4,847,571 | 68,993,773
PrefAttach 1 | 100,000 | 100,051,302
PrefAttach 2 | 1,000,000 | 999,999,375
Twitter | 41,652,230 | 1,468,364,884
Table 1: Datasets we use in the evaluation.

Figure 2: Density and running-time as a function of $c$ for LiveJournal with
$f=1/150,1/300,1/450$.

Figure 3: Density and running-time as a function of $c$ for PrefAttach $2$
with $f=1/30,1/450$.

Figure 4: Density and running-time as a function of $c$ for Twitter with
$f=1/100$.

###  6.2 Experimental Setup

As a baseline, we use [BKV12]. Both algorithms, the one from [BKV12] and ours,
are implemented in C++ on a M1 machine running macOS Monterey 12.5.1 with 4
cores, 8 GB of RAM, 256 KB of L2 Cache, and 2.5 MB of L3 Cache (per core). We
run the algorithms for values of $c$ ranging from $1/n$ to $n$ with constant
$\delta=2$ and $\epsilon=0.2$. Then, we study the algorithms in terms of how
close their approximation of the densest subgraph is and their runtime. Plots
of density and runtime are created with respect to the constant $c$.

An important note about Algorithm 4 is that it cannot calculate $\rho(S,T)$
for each iteration without seeing the whole graph. However, when implementing
the algorithm, we approximate that density through our sampled graph by
multiplying the density in the sampled graph, $\rho_{H}(S,T)$, by $1/p$.

Algorithm 4 creates samples of size $n\xi=\frac{f\cdot n\log
n}{\epsilon^{2}}$. In the theoretical analysis, we set $f=60$. In our
evaluations, we also investigate the effect of $f$ on the performance of our
approach, expecting that $f$ significantly smaller than $60$ would also result
in accurate and fast execution of Algorithm 4. To that end, in our
implementation of Algorithm 4, we consider
$f\in\\{1/10,1/20,1/30,1/100,1/150,1/300,1/450\\}$.

Although our guarantees for Algorithm 4 require randomized streams, to perform
a faithful comparison to [BKV12], we also execute Algorithm 4 _on arbitrarily
ordered streams_. In many cases, these arbitrarily ordered streams are edges
sorted by their endpoints, i.e., these streams are far from being randomized.

###  6.3 Results

Our algorithm finds subgraphs with densities very close to those output by our
baseline Bahamani et al. (VLDB 2021). For each graph, the densities with the
best corresponding $f$ are within $3\%$ of each other. Interestingly, this is
the case even for relatively small values of $f$, such as $f=1/450$,
suggesting that relatively sparse samples can be leveraged in extracting dense
subgraphs. Moreover, our algorithm attains higher accuracy for large graphs
than Bahamani et al. (VLDB 2021). For example, our algorithm’s density is
better by $1.5\%$ for Twitter (Figure 4) and by $5.5\%$ for LiveJournal
(Figure 2).

In addition to the maximum density of our algorithm being similar to Bahamani
et al. (VLDB 2021), the shapes of the density plots with respect to $c$ are
incredibly similar. This further solidifies that, in terms of accuracy,
Algorithm 4 matches Bahamani et al. (VLDB 2021) even on non-randomized
streams.

In the cases of denser graphs, our algorithm is around $2$ times faster than
the baseline. For PrefAttach $2$, it reaches around $4$ times faster (Figure
3) and for Twitter, around $2.5$ times faster (Figure 4). There is a balance
between using smaller constants for our sample size, leading to the algorithm
becoming faster, and the accuracy of the algorithm’s density approximation.

Note that the stream randomization does not affect our algorithm’s
performance, as illustrated in all the figures with randomized data. In
Appendix A, we provide results of additional evaluations, including results
for $\epsilon=0.1$ which are similar to those described here.

##  7 Conclusion and Future Work

We studied the approximate directed densest subgraph problem. We developed
sampling strategies that enabled us to design efficient algorithms for finding
dense subgraphs in semi-streaming and MPC. Moreover, our approach appears to
be highly practical – we showed empirically that these sampling strategies
yield faster algorithms even on non-randomized streams.

Our work was largely inspired by a discrepancy between state-of-the-art
efficiency of finding undirected and directed dense subgraphs. Even though we
made significant progress in bridging this gap, many interesting questions
remain. We mention three that we find the most exciting. (1) Is it possible to
find a $\Theta(1)$-approximate directed densest subgraph in a non-randomized
semi-streaming setting in $o(\log n)$ passes? As an intermediate question,
studying the trade-off between the number of passes and the memory requirement
would be interesting, e.g., interpolating between $1$ pass and $n^{3/2}$
memory, and $O(\log n)$ passes and $O(n\operatorname{poly}\log n)$ memory. (2)
For the same problem, does a $o(\log n)$ MPC round algorithm exist in the
sublinear memory regime? (3) Our MPC algorithm for the near-linear memory
regime outputs a $2+\varepsilon$ approximation. Is it possible to achieve a
$1+\varepsilon$ approximation with the same round complexity?

## Acknowledgements

We are grateful to Rishabh Bhaskaran for many insightful discussions on the
empirical portion of our work. S. Mitrović was supported by the Google
Research Scholar Program.

## References

  * [BA99] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  science, 286(5439):509–512, 1999.
  * [BC08] Gregory Buehrer and Kumar Chellapilla.  A scalable pattern mining approach to web graph compression with communities.  In Proceedings of the 2008 international conference on web search and data mining, pages 95–106, 2008.
  * [BGM14] Bahman Bahmani, Ashish Goel, and Kamesh Munagala.  Efficient primal-dual graph algorithms for mapreduce.  In International Workshop on Algorithms and Models for the 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.
  * [BKS17] Paul Beame, Paraschos Koutris, and Dan Suciu.  Communication steps for parallel query processing.  Journal of the ACM (JACM), 64(6):1–58, 2017.
  * [BKV12] Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii.  Densest subgraph in streaming and mapreduce.  Proceedings of the VLDB Endowment, 5(5), 2012.
  * [BM21] Panthadeep Bhattacharjee and Pinaki Mitra.  A survey of density based clustering algorithms.  Frontiers of Computer Science, 15:1–27, 2021.
  * [Cha03] Moses Charikar.  Greedy approximation algorithms for finding dense components in a graph.  In Approximation Algorithms for Combinatorial Optimization: Third International Workshop, APPROX 2000 Saarbrücken, Germany, September 5–8, 2000 Proceedings, pages 84–95. Springer, 2003.
  * [CS10] Jie Chen and Yousef Saad.  Dense subgraph extraction with application to community detection.  IEEE Transactions on knowledge and data engineering, 24(7):1216–1230, 2010.
  * [CSC+06] Andrea Capocci, Vito DP Servedio, Francesca Colaiori, Luciana S Buriol, Debora Donato, Stefano Leonardi, and Guido Caldarelli.  Preferential attachment in the growth of social networks: The internet encyclopedia wikipedia.  Physical review E, 74(3):036116, 2006.
  * [EHW15] Hossein Esfandiari, MohammadTaghi Hajiaghayi, and David P Woodruff.  Applications of uniform sampling: Densest subgraph and beyond.  arXiv preprint arXiv:1506.04505, 2015.
  * [ELS15] Alessandro Epasto, Silvio Lattanzi, and Mauro Sozio.  Efficient densest subgraph computation in evolving graphs.  In Proceedings of the 24th international conference on world wide web, pages 300–310, 2015.
  * [FLM22] Yixiang Fang, Wensheng Luo, and Chenhao Ma.  Densest subgraph discovery on large graphs: Applications, challenges, and techniques.  Proceedings of the VLDB Endowment, 15(12):3766–3769, 2022.
  * [GCDA15] Yérali Gandica, Joäo Carvalho, and F Sampaio Dos Aidos.  Wikipedia editing dynamics.  Physical Review E, 91(1):012824, 2015.
  * [GLM19] Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrović.  Improved parallel algorithms for density-based network clustering.  In International Conference on Machine Learning, pages 2201–2210. PMLR, 2019.
  * [Gol84] Andrew V Goldberg.  Finding a maximum density subgraph.  1984\.
  * [GSZ11] Michael T Goodrich, Nodari Sitchinava, and Qin Zhang.  Sorting, searching, and simulation in the mapreduce framework.  In International Symposium on Algorithms and Computation, pages 374–383. Springer, 2011.
  * [HBG+14] Steve Harenberg, Gonzalo Bello, La Gjeltema, Stephen Ranshous, Jitendra Harlalka, Ramona Seay, Kanchana Padmanabhan, and Nagiza Samatova.  Community detection in large-scale networks: a survey and empirical evaluation.  Wiley Interdisciplinary Reviews: Computational Statistics, 6(6):426–439, 2014.
  * [JM15] Emmanuel Jacob and Peter Mörters.  Spatial preferential attachment networks: Power laws and clustering coefficients.  2015\.
  * [KBM13] Jérôme Kunegis, Marcel Blattner, and Christine Moser.  Preferential attachment in online networks: Measurement and explanations.  In Proceedings of the 5th annual ACM web science conference, pages 205–214, 2013.
  * [KKSZ11] Hans-Peter Kriegel, Peer Kröger, Jörg Sander, and Arthur Zimek.  Density-based clustering.  Wiley interdisciplinary reviews: data mining and knowledge discovery, 1(3):231–240, 2011.
  * [KP05] Hans-Peter Kriegel and Martin Pfeifle.  Density-based clustering of uncertain data.  In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 672–677, 2005.
  * [KSV10] Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii.  A model of computation for mapreduce.  In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 938–948. SIAM, 2010.
  * [LK14] Jure Leskovec and Andrej Krevl.  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data, June 2014.
  * [LSIKK11] Yutaka I Leon-Suematsu, Kentaro Inui, Sadao Kurohashi, and Yutaka Kidawara.  Web spam detection by exploring densely connected subgraphs.  In 2011 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, volume 1, pages 124–129. IEEE, 2011.
  * [MTVV15] Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa T Vu.  Densest subgraph in dynamic graph streams.  In Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, pages 472–482. Springer, 2015.
  * [RZZ+21] Yuxiang Ren, Hao Zhu, Jiawei Zhang, Peng Dai, and Liefeng Bo.  Ensemfdet: An ensemble approach to fraud detection based on bipartite graph.  In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pages 2039–2044. IEEE, 2021.
  * [Sim55] Herbert A Simon.  On a class of skew distribution functions.  Biometrika, 42(3/4):425–440, 1955.
  * [SV19] Hsin-Hao Su and Hoa T Vu.  Distributed dense subgraph detection and low outdegree orientation.  arXiv preprint arXiv:1907.12443, 2019.
  * [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.
  * [WLFV+19] Jimmy Ming-Tai Wu, Chun Wei Lin, Philippe Fournier-Viger, Youcef Djenouri, Chun-Hao Chen, and Zhongcui Li.  The density-based clustering method for privacy-preserving data mining.  2019\.
  * [WWDR17] Phyllis Wan, Tiandong Wang, Richard A Davis, and Sidney I Resnick.  Fitting the linear preferential attachment model.  2017\.
  * [ZLZL16] Xianchao Zhang, Zhaoxing Li, Shaoping Zhu, and Wenxin Liang.  Detecting spam and promoting campaigns in twitter.  ACM Transactions on the Web (TWEB), 10(1):1–28, 2016.
  * [ZZY+17] Si Zhang, Dawei Zhou, Mehmet 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 570–578. SIAM, 2017.

##  Appendix A Additional empirical evaluation

In this section, we provide empirical evaluation in addition to those given in
the main paper. We refer a reader to Section 6 for details on the baselines,
datasets, and computational setup.

Figure 5: Density and running-time as a function of $c$ for remaining graphs

Figure 6: Density and running-time as a function of $c$ for remaining graphs
with randomization

Figure 7: Density and running-time as a function of $c$ for some graphs with
$\epsilon=0.1$