#  Near Uniform Triangle Sampling Over Adjacency List
Graph Streams

Arijit Bishnu 111Indian Statistical Institute, Kolkata, India. Email:
<EMAIL_ADDRESS>Arijit Ghosh 222Indian Statistical Institute, Kolkata,
India. Email<EMAIL_ADDRESS>Gopinath Mishra 333National
University of Singapore, Singapore. Email<EMAIL_ADDRESS>Sayantan
Sen444Centre for Quantum Technologies, National University of Singapore,
Singapore. Email<EMAIL_ADDRESS>
###### Abstract

Triangle counting and sampling are two fundamental problems for streaming
algorithms. Arguably, designing sampling algorithms is more challenging than
their counting variants. It may be noted that triangle counting has received
far greater attention in the literature than the sampling variant. In this
work, we consider the problem of _approximately sampling triangles_ in
different models of streaming with the focus being on the _adjacency list_
model.

In this problem, the edges of a graph $G$ will arrive over a data stream. The
goal is to design efficient streaming algorithms that can sample and output a
triangle from a distribution, over the triangles in $G$, that is _close_ to
the uniform distribution over the triangles in $G$. The distance between
distributions is measured in terms of $\ell_{1}$-distance. The main technical
contribution of this paper is to design algorithms for this triangle sampling
problem in the _adjacency list_ model with the space complexities matching
their counting variants. For the sake of completeness, we also show results on
the vertex and edge arrival models.

##  1 Introduction

The primary goal of this paper is to initiate a systematic study of _sampling
almost uniformly_ a triangle over a data stream, denoted as $\mathcal{M}$. Our
setting is the usual streaming models (namely Adjacency List (AL) model, Edge
Arrival (Ea) model and Vertex Arrival (Va) model) with single or multi-passes
[32, 28] over a graph $G=(V,E)$ with the set of vertices $V$ and the set of
edges $E$ such that $\left|V\right|=n$ and $\left|E\right|=m$. Let us start
with a brief description of the streaming models.

  * •

Adjacency List (Al): The set of vertices $V$ of $G$ are revealed in an
arbitrary order. When a vertex $v\in V$ is revealed, all the edges that are
incident to $v$, arrive one by one in an arbitrary order. Note that in this
model each edge arrives twice, once for each endpoint.

  * •

Edge Arrival (Ea): The stream consists of the edges of $G$ in an arbitrary
order.

  * •

Vertex Arrival (Va): The set of vertices $V$ of $G$ are revealed in an
arbitrary order. When a vertex $v\in V$ is revealed, all the edges between $v$
and the neighbors of $v$ that are already revealed, arrive one by one in an
arbitrary order.

The contribution of this paper is in designing triangle sampling algorithms in
all the three models with the primary focus being on the Al model as we can
show that the existing triangle counting algorithms in the Ea and Va models
can be extended to triangle sampling. For a graph $G$ having at least one
triangle, let $t(G)$ denote the set of triangles present in $G$, and
$\mathcal{U}$ denote the uniform distribution over the set $t(G)$. The formal
description of the problem that we study in this work is as follows:

Triangle Sampling over Data Streams Input: A graph $G(V,E)$ with its edges as
a stream over $p$ pass(es), and a proximity parameter $\varepsilon\in(0,2)$.
Output: A triangle sampled almost uniformly, that is, from a distribution
$\mathcal{D}$ over $t(G)$ such that the $\ell_{1}$-distance between
$\mathcal{D}$ and $\mathcal{U}$ is at most $\varepsilon$. 555For two
distributions $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ over a (non-empty) set
$S$, the $\ell_{1}$-distance between $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$
is denoted and defined as
$|\left|\mathcal{D}_{1}-\mathcal{D}_{2}\right||_{1}:=\sum_{x\in
S}\left|\mathcal{D}_{1}(x)-\mathcal{D}_{2}(x)\right|.$

In this work, we determine the space complexities of Triangle Sampling in Al,
Va, and Ea models that match the space complexity of the counting variants of
the problems.

In terms of applications, triangle counting as well as triangle sampling have
found wide applications across multiple disciplines such as computational
biology [36, 38], databases [15, 11, 2], social network analysis [40], to name
a few. In particular, sampling over triangle queries and general join queries
as well as sampling over join-project queries are studied in the database
community (see [12, 42] and the references therein). Moreover, this is also
used in the analysis of huge graphs as well as for community detection in
large networks [7, 31].

##### The complexity of sampling may be more than that of counting.

It may be pertinent to mention here that though counting triangles over a data
stream has received wide attention for a long time now [5, 24, 8, 10, 13, 9,
21, 25, 27, 30, 33, 34], to the best of our knowledge, the only work prior to
ours that dealt with sampling triangle over a data stream (in the $1$-pass
Ea/Va model) is the work by Pavan et al. [34]. Though triangle counting has
been a challenging as well as an important problem in the streaming
literature, it seems that designing algorithms for triangle sampling is
possibly harder than its counting variant. To count triangles or any other
implicit structures, like cycles, cliques, etc., that are aggregating
measures, one works on random samples of different types. But there is no
guarantee that those random samples would serve the purpose of figuring out a
uniformly random sampled triangle or such an implicit structure. Here, it may
be instructive to see what happened in the “other” sublinear world, i.e. in
the property testing models pertaining to query complexity.

It is interesting to note that in the local query model, where we have only
_degree_ , _edge existence_ and _neighborhood_ query access to a graph, 666In
degree query, given a vertex $v$, the oracle returns $deg(v)$. For edge-
existence query, given two vertices $u$ and $v$, the oracle returns $1$ if
there is an edge between $u$ and $v$. Finally, in the neighborhood query,
given a vertex $v$ and an integer $i$, the oracle returns the $i$-th neighbor
of $v$ if it exists, or a special symbol if $deg(v)<i$. the query complexity
of sampling triangles is more compared to its counting counterparts [17].
However, the addition of _random edge_ query access to the graph makes the
query complexities of triangle counting and sampling the same ignoring
polynomial terms in $1/\varepsilon$ and $\log n$ [19]. So, it is interesting
to understand the status of Triangle Sampling in the streaming setting in the
following sense: are the space complexities of Triangle Sampling the same as
their counting counterparts ignoring polynomial terms in $1/\varepsilon$ and
$\log n$? In this work, we answer this question in the affirmative for Al, Ea
and Va models.

###  1.1 Our Results

The main technical contribution of the paper is designing optimal algorithms
for Triangle Sampling in the Al model.

######  Theorem 1.1.

(Main Result: Informal Statement). Triangle Sampling can be solved in Al model
using: (i) $\widetilde{\Theta}\left(m/T^{2/3}\right)$ space in $3$-passes and
(ii) $\widetilde{\Theta}\left(m/\sqrt{T}\right)$ space in $1$-pass. Here $T$
is a promised lower bound on the number of triangles in $G$. 777The promise
$T$ on the number of structures is a standard assumption for estimating
substructures (such as triangles) in the world of graph streaming algorithms
[22, 26, 24, 30, 5]. Here we have cited a few. However, there are huge amount
of relevant literature. Moreover, $\widetilde{\Theta}(\cdot)$ hides a
polynomial in $\log n$ and $1/\varepsilon$ in the upper bound.

Let us discuss about the complexity of Triangle Sampling in Ea/Va model. It is
known that Triangle Sampling can be solved in Ea/Va model in $1$-pass by using
$\widetilde{{\mathcal{O}}}\left(\min\\{m,m^{2}/T\\}\right)$ space [34]. 888In
Appendix B, we also present a new algorithm of Triangle Sampling in $1$-pass
Ea/Va model with space complexity
$\widetilde{\Theta}\left(\min\\{m,m^{2}/T\\}\right)$ which we believe has a
unifying structure with our other algorithms in different settings. We observe
that multi-pass triangle counting algorithms in Ea/Va model [3] can be
extended directly to solve Triangle Sampling in Ea/Va model using
$\widetilde{\Theta}\left(m^{3/2}/T\right)$ space in $3$-passes. The details of
the algorithms in Ea/Va models are discussed in Appendix B. Our algorithm
pertaining to Theorem 1.1 is inspired from the counting algorithms in Al model
[24, 30]. However, our sampling algorithms undergo a significantly different
and subtle analysis compared to their counting counterparts. We believe that
the detailed analysis constitutes the primary contribution of our paper.

The proof of the two upper bounds in Theorem 1.1, presented in Section 3 and
Section 4, respectively form the main technical component of this paper. The
lower bounds in Theorem 1.1 and the lower bounds in Ea/Va model follow from
the lower bounds for counting version of the problems [24, 8, 5]. The details
are discussed in Appendix A and Appendix C.

##### Notations.

As in other works in streaming, we use a parameter $T$ to denote a guaranteed
lower bound on the total number of triangles in $G$, i.e.,
$\left|t(G)\right|\geq T$. To make the exposition simple while describing our
algorithms, we assume that we know the exact values of $m$ and
$\left|t(G)\right|=T$. However, the assumptions can be removed by using
standard techniques in graph streaming. The details are discussed in Appendix
A. We will use $\widetilde{\mathcal{O}}(\cdot)$ to hide polynomial factors in
$1/\varepsilon$ and $\log n$. For an event $\mathcal{E}$ and
$\alpha,p\in(0,1)$, we write $\mathbb{P}(\mathcal{E})=(1\pm\alpha)p$ to denote
that the probability of the event $\mathcal{E}$ lies between $(1-\alpha)p$ and
$(1+\alpha)p$. When we say that event $\mathcal{E}$ holds with high
probability, we mean $\mathbb{P}(\mathcal{E})\geq 1-1/\mathsf{poly}(n)$. Let
$S$ be a non-empty set and $\mathcal{D}$ be a probability distribution over
$S$. For $x\in S$, $\mathcal{D}(x)$ denotes the probability of sampling $x$
when one draws a random sample from $\mathcal{D}$. For two distributions
$\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ over a (non-empty) set $S$, the
$\ell_{1}$-distance between $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ is denoted
and defined as $|\left|\mathcal{D}_{1}-\mathcal{D}_{2}\right||_{1}:=\sum_{x\in
S}\left|\mathcal{D}_{1}(x)-\mathcal{D}_{2}(x)\right|.$ _Reservoir sampling_ is
a widely used randomized algorithmic framework in streaming that samples $k$
uniformly random elements from a stream where $k$ is known before the start of
the stream [41]. The space complexity of the algorithm is $\mathcal{O}(k)$. We
denote a reservoir sampler by RS and explicitly mention whether we are
considering sampling with or without replacement. In a similar fashion, one
can consider _weighted reservoir sampler_ , denoted by WRS, to sample elements
proportional to their weights.

###  1.2 Related Works

Alon et al. [1] studied the problem of counting triangles in directed as well
as undirected graphs in the RAM model. The problem of triangle counting in the
streaming model was first considered by Bar-Yossef et al. [4] where the
authors studied the problem of approximately counting triangles in a graph $G$
where the edges of $G$ appear as a stream. Subsequently, there have been
several interesting works in several variants [8, 10, 13, 9, 21, 25, 27, 30,
33, 34, 24, 20]. For an exhaustive list of results, and several techniques,
see the surveys of Muthukrishnan [32] and McGregor [28]; also see Bera and
Chakrabarti [5] for a nice summary of relevant results.

A close cousin of counting is the problem of sampling. However, in the field
of streaming algorithms, sampling implicit graph structures like triangle,
clique, and cycles have not been very well studied before. In the field of
property testing, where sublinear number of query accesses to the graph is
important, uniform sampling of edges has been considered [18, 39, 16]. Later
there have been results on sampling cliques [17] and sampling arbitrary
subgraphs [19, 6].

As seen from the preceding discussions, although triangle counting has been
studied extensively in the streaming model, sampling triangles uniformly from
a graph stream has not been well studied before, excepting for a work or two.
Sampling works in property testing setting is also of recent vintage. In this
work, we progress towards closing this gap between the study of counting and
sampling triangles over a graph stream.

Now, we discuss briefly relevant triangle counting literature. For single pass
Ea/Va model, Braverman et al. [8] proved that even for distinguishing
triangle-free graphs from graphs with $T$ triangles, $\Omega(m)$ space is
required. Pavan et al. [34] studied the problem of triangle counting and
sampling in $1$-pass Ea/Va model, where they designed an algorithm that uses
$\widetilde{\Theta}(m^{2}/T)$ space. Note that the work of Pavan et al. [34]
is the only work that studied the triangle sampling problem prior to this
work. Their triangle sampling technique first picks up an edge $e$ uniformly
at random using reservoir sampling. Next they pick up an edge uniformly at
random from the adjacent edges of $e$. This creates a wedge; they now wait for
the arrival of an edge that completes the triangle with the edge $e$. Cormode
and Jowhari [13] studied the triangle counting problem in Ea model and
designed a multi-pass algorithm with space complexity
$\widetilde{\mathcal{O}}(m/\sqrt{T})$. Later McGregor et al. [30] designed two
separate multi-pass algorithms with space complexity
$\widetilde{{\mathcal{O}}}(m^{3/2}/T)$ and
$\widetilde{{\mathcal{O}}}(m/\sqrt{T})$, respectively. Bera and Chakrabarti
[5] also proved a lower bound of $\Omega(\min\\{m^{3/2}/T,m/\sqrt{T}\\})$ for
multi-pass setting, and presented a simpler multi-pass algorithm with space
complexity $\widetilde{\mathcal{O}}(m^{3/2}/T)$. For Al model, McGregor et al.
[30] designed a single pass $(1\pm\varepsilon)$-multiplicative approximation
algorithm for counting the number of triangles in
$\widetilde{\mathcal{O}}(m/\sqrt{T})$ space. The multi-pass algorithm for
triangle counting in Al model was first studied by the same authors in [30]
which was later improved by Kallaugher et al. [24] to
$\widetilde{\mathcal{O}}(m/T^{2/3})$.

##  2 Overview of our algorithms

In this section, we present a technical overview of our upper bound results of
1.1. The corresponding lower bounds follow from a sampling to counting
reduction technique, and are discussed in Appendix C.

###  2.1 Multi-pass triangle sampling algorithm in the Al model

Triangle is an implicit structure derived from edges; so to get to an
uniformly random sampled triangle, we target the triangles via edges in the
following way. We call an edge _heavy_ (_light_) if it has _many_ (_less
number of_) triangles incident on it. Informally speaking, an edge is said to
be heavy if the number of triangles incident on it is at least some threshold
$\tau=\Theta_{\varepsilon}(T^{1/3})$. 999$\Theta_{\varepsilon}(\cdot)$ hides
the dependency on $1/\varepsilon$. Otherwise, the edge is said to be light. A
triangle is said to be heavy if all of the edges of the triangle are heavy.
Otherwise, the triangle is said to be light. One can argue that the total
number of heavy edges is at most $\Theta_{\varepsilon}(T^{2/3})$ and the
number of heavy triangles is $\mathcal{O}(\varepsilon T)$. So, if we can show
that we can sample light triangles uniformly, we are done. To do so, consider
the following algorithm: take an edge $e$ uniformly at random. If $e$ is
light, then choose a triangle $s_{e}$ uniformly at random from the triangles
incident on $e$. Then compute the number of edges of $s_{e}$ that are light,
let it be $i\in\\{1,2,3\\}$ ($i\not=0$ as $e$ itself is a light edge). Report
$s_{e}$ as the sampled triangle with probability
$\frac{1}{i}\cdot\frac{\lambda_{e}}{\tau}$, where $\lambda_{e}$ denotes the
number of triangles incident on $e$. Now, consider a light triangle $\Delta$
such that the number of light edges on it is $j\in\\{1,2,3\\}$. The
probability that $\Delta$ is sampled is
$\frac{j}{m}\cdot\frac{1}{\lambda_{e}}\cdot\frac{1}{j}\cdot\frac{\lambda_{e}}{\tau}=\frac{1}{m\tau}=\Theta_{\varepsilon}(\frac{1}{mT^{1/3}})$.
Since the number of heavy triangles is $\mathcal{O}(\varepsilon T)$, the
number of light triangles is $\Omega(T)$. Thus the probability that the above
procedure reports some light triangle is $\Theta_{\varepsilon}(T^{2/3}/m)$. If
the above process succeeds, we can argue that we get a light triangle
uniformly at random. To boost the success probability, one can repeat the
above procedure $\widetilde{{\mathcal{O}}}{(m/T^{2/3})}$ times.

Here, we would like to emphasize that the above intuition can be formalized
and implemented in streaming model by exploiting the properties of the Al
model. We defer the details to Section 3.

Note that the intuition described above can be worked out to give an
alternative multi-pass algorithm for triangle counting in the Al model with
the same space bound as of [24]. The intuition behind the triangle counting
algorithm of [24] is different from the intuition we described above for our
sampling algorithm. It is not clear to us if the algorithm of [24] can be
extended to sampling.

###  2.2 Single pass triangle sampling algorithm in the Al model

We will use an idea akin to light and heavy edges as described in the 3-pass
algorithm, but to get to a 1-pass algorithm, we will take recourse to running
subroutines in parallel. The idea of the algorithm is to charge each triangle
to a unique edge depending on the order of exposure of vertices in the stream.
An edge is designated to be either _heavy_ or _light_ 101010Here, the
definition of heavy and light are different than that of the 3-pass algorithm.
The exact definitions will be given in the respective section., depending on
the number of triangles charged to it. A triangle is said to be heavy or light
according to the type of the edge to which it has been charged. Over the
stream, our algorithm detects all the heavy edges. For each heavy edge, our
algorithm samples a triangle uniformly at random from all the triangles
incident on that heavy edge. Our algorithm also samples a light triangle with
a _suitable_ probability. Let us discuss the intuition in some more detail.

For two vertices $a,b\in V$, we say $a\prec_{s}b$ (the $s$ in $\prec_{s}$
denotes the order imposed by the streaming order of the vertices) if the
adjacency list of a is revealed before the adjacency list of $b$. Consider a
triangle $\Delta=\\{a,b,c\\}$ such that $a\prec_{s}b\prec_{s}c$. We say
$\Delta$ is _charged_ to the edge $\\{a,c\\}$. For an edge $e=\\{a,c\\}$ such
that $a\prec_{s}c$, $t_{e}$ denotes the number of triangles charged to edge
$e$. Since every triangle is assigned to an unique edge, we can say that
$T=\sum_{e\in E}t_{e}$.

##### Intuition of sampling a light triangle:

For the time being, let us define an edge $e$ to be _light_ if
$t_{e}\leq\tau=\Theta(\sqrt{T})$ 111111As previously noted, the exact
definition is presented in Section 4.2.. Consider a light triangle
$\Delta=\\{u,v,w\\}$ which is charged to the edge $\\{u,w\\}$. Let us sample
an edge $e$ uniformly at random over the stream and take a triangle charged to
$e$ uniformly at random with probability $\frac{t_{e}}{\tau}$ if
$t_{e}\leq\tau$. The probability that $\Delta$ is sampled is
$\frac{1}{m}\cdot\frac{1}{t_{e}}\cdot\frac{t_{e}}{\tau}=\frac{1}{m\tau}$. So,
the probability that some light triangle will be sampled by the above
procedure is $\frac{T_{L}}{m\tau}$, where $T_{L}$ denotes the total number of
light triangles. If $T_{L}=\Omega(T)$, (otherwise, we argue that sampling
light triangles is not necessary) then the success probability of sampling a
light triangle is $\Omega(\sqrt{T}/m)$ and we obtain a light triangle
uniformly at random. If we run the above process
$\widetilde{{\mathcal{O}}}(m/\sqrt{T})$ times independently, we will get a
light triangle uniformly at random with high probability.

##### Intuition of sampling a heavy triangle:

Let us define an edge $e$ to be _heavy_ if $t_{e}>\tau=\Theta(\sqrt{T})$. This
implies that there are at most $\mathcal{O}(\sqrt{T})$ number of heavy edges.
Let $H$ denote the set of heavy edges, and $T_{H}=\sum_{e\in H}t_{e}$.
Consider the following algorithm for sampling a heavy triangle. Take an edge
$e\in H$ with probability $\frac{t_{e}}{T_{H}}$ and report a triangle charged
to $e$ uniformly at random. For any heavy triangle $\Delta$ (charged to $e$),
the probability that $\Delta$ is sampled is
$\frac{t_{e}}{T_{H}}\cdot\frac{1}{t_{e}}=\frac{1}{T_{H}}$.

Here, we would like to emphasize that both of the above intuitions can be
formalized and implemented in the Al streaming model by exploiting its
properties. We defer the details to Section 4.1.

##  3 Multi-pass Triangle Sampling in Al model

######  Theorem 3.1 (Upper Bound of Theorem 1.1(i)).

Triangle Sampling can be solved by using
$\widetilde{{\mathcal{O}}}\left(m/T^{2/3}\right)$ space in Al model in
$3$-passes.

Before proceeding to the algorithm, let us first define the notions of heavy
and light edges as well as heavy and light triangles which will be required in
the proof.

######  Definition 3.2 (Heavy and light edge).

Given a parameter $\tau\in\mathbb{N}$, an edge $e$ is said to be _$\tau$
-heavy_ or simply heavy if $\lambda_{e}\geq\tau$, where $\lambda_{e}$ denotes
the number of triangles incident on $e$. Otherwise, $e$ is said to be a
_$\tau$ -light_ or simply light edge.

We now also define notions of heavy and light triangles.

######  Definition 3.3 (Heavy and light triangle).

Let $i,\tau$ be two integers such that $i\in\\{0,1,2,3\\}$. A triangle
$\Delta$ is said to be _$i$ -light_ if it has $i$ $\tau$-light edges. Note
that $0$-light triangles are _heavy triangles_. A triangle is said to be light
if it is not heavy, that is, $i$-light for some $i\in\\{1,2,3\\}$.

We will use the following result which upper bounds the maximum number of
triangles of a graph $G$ with respect to its number of edges.

######  Lemma 3.4 ([35]).

Given a graph $G(V,E)$ such that $\left|E\right|=m$, the number of triangles
of $G$ is at most $\mathcal{O}(m^{3/2})$.

As earlier, let us denote the stream by $\mathcal{M}$. Below we set
$\tau=12(T/\varepsilon^{2})^{1/3}$, where $T$ is the number of triangles in
$G$. The following observation bounds the total number of heavy edges along
with the total number of heavy and light triangles.

######  Observation 3.5.

Let us assume that in a graph $G$, the total number of triangles is $T$ and
$\tau=12(T/\varepsilon^{2})^{1/3}$. Then the following hold:

  1. (i)

The number of $\tau$-heavy edges is at most $(\varepsilon T/8)^{2/3}$.

  2. (ii)

The number of heavy triangles $T_{H}$ is at most $\varepsilon T/8$.

  3. (iii)

The number of light triangles $T_{L}$ is at least $(1-\varepsilon/8)T$.

###### Proof.

  1. (i)

From the definition of $\tau$-heavy edges (Definition 3.2), an edge $e$ is
$\tau$-heavy, if the number of triangles $\lambda_{e}$ incident on $e$ is at
least $\tau$. Since the total number of triangles in the graph $G$ is $T$, the
total number of $\tau$-heavy edges can be at most $3T/\tau$. As
$\tau=12(T/\varepsilon^{2})^{1/3}$, the result follows.

  2. (ii)

From Lemma 3.4, we know that the total number of possible triangles over $m$
edges is at most $\mathcal{O}(m^{3/2})$. Since from $(i)$, we know that the
total number of $\tau$-heavy edges is at most $\mathcal{O}((\varepsilon
T/8)^{2/3})$, we have the result.

  3. (iii)

Follows directly from $(ii)$ as $T=T_{L}+T_{H}$.

∎

Now let us proceed to describe our $3$-pass algorithm in the Al model. Recall
the intuition described in Section 2.1. We will sample a multi-set of edges
$\mathcal{F}$ uniformly and independently at random with replacement in the
first pass. The edges of $\mathcal{F}$ can be thought of as _candidate light
edges_. Next, we count the number of triangles $\lambda_{e}$ incident on every
edge $e\in\mathcal{F}$ to decide which edges of $\mathcal{F}$ are light.
Additionally, for every edge $e\in\mathcal{F}$, we sample a triangle
$s_{e}=(e,e_{1},e_{2})$ incident on $e$ uniformly. In the third and final
pass, for every edge $e\in\mathcal{F}$ and every sampled triangle
$s_{e}=(e,e_{1},e_{2})$, we count the number of triangles incident on $e_{1}$
and $e_{2}$. In the processing phase, every heavy edge of $\mathcal{F}$ is
ignored. For every light edge $e\in\mathcal{F}$, we consider the triangle
$s_{e}$ further with a suitable probability, depending upon the number of
triangles incident on the edges of $s_{e}$. The triangle $s_{e}$ corresponding
to some light edge $e\in\mathcal{F}$ is the desired output. The formal
algorithm is described in Algorithm 1. In order to prove the correctness of
Algorithm 1, i.e. proving 3.1, we first show the following lemma about
Algorithm 1.

1

2

3Pass 1: Sample a multi-set $\mathcal{F}$ of
$\widetilde{{\mathcal{O}}}(m/T^{2/3})$ edges from $\mathcal{M}$ uniformly and
independently at random with replacement.

4Pass 2: for  _every edge $e\in\mathcal{F}$_ do

5

6 Count $\lambda_{e}$.

7 Sample a triangle $s_{e}$ incident on $e$ uniformly at random.

8Pass 3: for  _every edge $e\in\mathcal{F}$ and sampled triangle $s_{e}$
incident on $e$_ do

9

10 Let $e_{1}$ and $e_{2}$ be the other two edges of $s_{e}$. Compute
$\lambda_{e_{1}}$ and $\lambda_{e_{2}}$.

11 // This information along with $\lambda_{e}$ helps us to determine the
value of $i$ such that $s_{e}$ is a $i$-light triangle.

12Process: Set $\tau\leftarrow 12(T/\varepsilon^{2})^{1/3}$.

13for  _every edge $e\in\mathcal{F}$_ do

14

15 if  _$e$ is $\tau$-heavy_ then

16

17 Ignore $e$.

18

19 else

20 Consider the triangle $s_{e}$ sampled on $e$.

21 Determine $i\in\\{1,2,3\\}$ such that $s_{e}$ is an $i$-light triangle.

22 Mark $s_{e}$ with probability $\lambda_{e}/i\tau$.

23

24Report any marked triangle if there exists at least one such marked
triangle. Otherwise, report FAIL and ABORT the process.

Algorithm 1 Triangle Sampling in $3$-pass Al-Model

######  Lemma 3.6.

With high probability, Algorithm 1 samples a light triangle uniformly.

###### Proof.

From the description of the algorithm, note that the algorithm never reports a
heavy triangle.

Now let us consider an arbitrary $i$-light triangle $\Delta$, where
$i\in\\{1,2,3\\}$. Recall that in Pass 1, we have sampled a multi-set of edges
$\mathcal{F}$. First consider the case when $\left|\mathcal{F}\right|=1$. Note
that to sample the triangle $\Delta$, we need to store one of the $i$-light
edges of $\Delta$ in Pass 1. This happens with probability $i/m$. Moreover,
for the sampled light edge $e$, $\Delta$ needs to be sampled among all the
triangles incident on $e$, which happens with probability $1/\lambda_{e}$.
Finally, Algorithm 1 outputs the sampled triangle with probability
$\lambda_{e}/i\tau$. Combining these arguments, the probability that $\Delta$
is sampled is: $=i/m\times 1/\lambda_{e}\times\lambda_{e}/i\tau=1/m\tau$.

Applying the union bound over all light triangles over $G$, the probability
that the algorithm does not report Fail is $T_{L}/m\tau$, where $T_{L}$
denotes the number of light triangles. Observe that, under the conditional
space that the algorithm does not report Fail, it reports a light triangle
uniformly at random with probability $T_{L}/m\tau$ when
$\left|\mathcal{F}\right|=1$. Under the conditional space that the algorithm
does not report Fail, the probability that it outputs $\Delta$ is $1/T_{L}$.
That is, the algorithm reports a light triangle uniformly at random with
probability $T_{L}/m\tau$ when $|\mathcal{F}|=1$.

Since $\left|\mathcal{F}\right|=\widetilde{{\mathcal{O}}}(m/T^{2/3})$ and
$T_{L}\geq(1-\varepsilon/8)T$, with high probability the algorithm does not
report Fail and reports a light triangle uniformly. ∎

It is important to note that our algorithm does not sample any heavy triangle.
Now we will show that the total error due to not sampling any heavy triangle
is not large as $T_{H}\leq\varepsilon T/8$ (from 3.5).

###### Proof of Theorem 3.1.

From the description of Algorithm 1, the space complexity of the algorithm is
$\left|\mathcal{F}\right|=\widetilde{{\mathcal{O}}}(m/T^{2/3})$. From Lemma
3.6, Algorithm 1 does not report Fail with high probability, never outputs a
heavy triangle and reports a light triangle uniformly. Under the conditional
space that the output satisfies the guarantee by Lemma 3.6, the distribution
$\mathcal{D}$ from which Algorithm 1 samples a triangle $\Delta$ is as
follows. Let us denote the set of heavy and light triangles of $G$ as
$\mathcal{T}_{H}$ and $\mathcal{T}_{L}$. Define

$\mathcal{D}(\Delta)=\begin{cases}1/T_{L}&\Delta\in\mathcal{T}_{L}\\\
0&\Delta\in\mathcal{T}_{H}\end{cases}$

Let $\mathcal{U}$ denote the uniform distribution over the set of all
triangles in $G$. Now we bound the $\ell_{1}$-distance between $\mathcal{D}$
and $\mathcal{U}$ as follows:

$\displaystyle||\mathcal{D}-\mathcal{U}||_{1}$
$\displaystyle=\sum_{\Delta\in\mathcal{T}_{H}}|\mathcal{D}(\Delta)-\mathcal{U}(\Delta)|+\sum_{\Delta\in\mathcal{T}_{L}}\left|\mathcal{D}(\Delta)-\mathcal{U}(\Delta)\right|\leq
T_{H}\cdot{1}/{T}+T_{L}\cdot\left|{1}/{T_{L}}-{1}/{T}\right|.$

From Observation 3.5, $T_{H}\leq\varepsilon T/8$ and
$T_{L}\geq(1-\varepsilon/8)T$. Putting these bounds in the above expression,
we have $||\mathcal{D}-\mathcal{U}||_{1}\leq\varepsilon$. ∎

##  4 One-Pass Triangle Sampling in Al model

In this section, we give our one pass algorithm for triangle sampling in the
Al model, hence proving the following theorem.

######  Theorem 4.1 (Upper bound of Theorem 1.1(ii)).

Triangle Sampling can be solved by using
$\widetilde{{\mathcal{O}}}\left(m/\sqrt{T}\right)$ space in Al model in
$1$-pass.

To prove the above theorem, we define a notion of charging triangles to edges
such that each triangle is charged to only one edge. Based on the number of
triangles charged to an edge, we will define that edge to be either _heavy_ or
_light_. Informally, a triangle is heavy (light) if the edge to which it is
charged is heavy (light) 121212The exact definitions of heavy/light triangles
and edges are based on the stream and the randomness we are using in the
algorithm. The definitions are presented in Section 4.2.. Consider the
vertices of the graph in the order in which they are revealed in the stream.
Let $a\prec_{s}b$ denote that the adjacency list of vertex $a$ is revealed
before the adjacency list of $b$. So, the set of vertices of the graph form a
total order w.r.t. $\prec_{s}$ relation. Consider a triangle
$\Delta=\\{a,b,c\\}$ such that $a\prec_{s}b\prec_{s}c$. We say that $\Delta$
is _charged_ to the edge $\\{a,c\\}$. For an edge $e=\\{a,c\\}$ such that
$a\prec_{s}c$, $t_{e}$ denotes the number of triangles charged to $e$. Since
every triangle is assigned to a unique edge, we have $T=\sum_{e\in E}t_{e}$.

The main algorithm Triangle-Sample-Al-1pass (Algorithm 6) of 4.1 will be
discussed in Section 4.4 and 4.5. We discuss the algorithm Triangle-Sample-
Al-1pass with space complexity
$\widetilde{{\mathcal{O}}}(m/\sqrt{T}+\sqrt{T})$. However, we can make some
modifications to the algorithm to obtain the desired space complexity
$\widetilde{{\mathcal{O}}}(m/\sqrt{T})$. The details are to be discussed in
Section 4.5. To present the main algorithm, we need two streaming subroutines
to be run in parallel when the edges are appearing in the stream:
SampLightHelper (Algorithm 2) and SampHeavyHelper (Algorithm 3) having space
complexities $\widetilde{{\mathcal{O}}}(m/\sqrt{T})$ and
$\widetilde{{\mathcal{O}}}(m/\sqrt{T}+\sqrt{T})$, respectively. These
subroutines are described in Section 4.1. In the post processing phase after
the stream ends, Triangle-Sample-Al-1pass has again two subroutines Sample-
Light-Triangle (Algorithm 4) and Sample-Heavy-Triangle (Algorithm 5) which are
discussed in Section 4.2. Note that Sample-Light-Triangle uses outputs from
SampLightHelper and SampHeavyHelper, where Sample-Heavy-Triangle uses only the
output of SampHeavyHelper 131313One may wonder that why we are using
SampHeavyHelper in Sample-Light-Triangle. But we defer that discussion to
Section 4.2.. Finally, Triangle-Sample-Al-1pass combines the outputs of
Sample-Light-Triangle and Sample-Heavy-Triangle to report the final desired
output.

###  4.1 Descriptions of SampLightHelper and SampHeavyHelper

Here we describe the subroutines SampLightHelper and SampHeavyHelper mentioned
before.

#### Description of SampLightHelper

Recall the intuition discussed to sample a light triangle in the overview in
Section 2.2. To make the intuition work, we use SampLightHelper. It samples
$\widetilde{{\mathcal{O}}}(m/\sqrt{T})$ edges uniformly at random with
replacement. Let $\mathcal{F}_{1}$ be the set of sampled edges. But to count
the number of edges charged to an edge $e=\\{u,v\\}\in\mathcal{F}_{1}$ (such
that $u\prec_{s}v$) and sample a triangle charged to $\\{u,v\\}$, we desire
that $e=\\{u,v\\}$ is sampled when $u$ is exposed. So, by exploiting the fact
that we are in the Al model, one can see all the triangles charged to
$\\{u,v\\}$ in between the exposures of $u$ and $v$. Hence, we can maintain
the value of $t_{e}$ (the number of triangles charged to $e$) and a triangle
charged to $e$ uniformly at random. The pseudocode for SampLightHelper is
presented in Algorithm 2 and its guarantee is stated in 4.2. The formal
discussion about how SampLightHelper will be helpful in sampling a light
triangle will be discussed in Section 4.3.

######  Lemma 4.2.

SampLightHelper (Algorithm 2) uses $\widetilde{{\mathcal{O}}}(m/\sqrt{T})$
space. It reports a multiset $\mathcal{F}_{1}$ of
$\widetilde{{\mathcal{O}}}(m/\sqrt{T})$ edges chosen uniformly at random with
replacement from the stream. For each edge $e\in\mathcal{F}_{1}$, the
algorithm stores the following: a Boolean variable $\mathsf{flag}(e)$, a
counter $t_{e}^{\prime}$, and a triangle $\Delta_{e}$ containing edge $e$ if
$t_{e}^{\prime}\neq 0$ 141414It might be the case that $\Delta_{e}$ is not
charged to $e$.. Moreover, for an edge $e\in\mathcal{F}_{1}$, if
$\mathsf{flag}(e)=1$, then (i) $t_{e}^{\prime}=t_{e}$, i.e., the number of
triangles charged to $e$, and (ii) $\Delta_{e}$ is a triangle chosen uniformly
at random among all triangles charged to $e$.

###### Proof.

As $\left|\mathcal{F}_{1}\right|=\widetilde{{\mathcal{O}}}(m/\sqrt{T})$ and
the algorithm stores $O(1)$ information for each edge $e\in\mathcal{F}_{1}$
(i.e., $\mathsf{flag}(e),t_{e}^{\prime}$, and possibly $\Delta_{e}$), the
space complexity of the algorithm follows.

Now consider the case when $\mathsf{flag}(e)=1$. Let $e=\\{v,w\\}$ and we have
set $\mathsf{flag}(e)=1$ when $w$ is exposed in the stream. From the
description of the algorithm, this implies that $e$ is already present in
$\mathcal{F}_{1}$ before $w$ is exposed, i.e, we have included $e$ into
$\mathcal{F}_{1}$ when $v$ was exposed and we have set $\mathsf{flag}(e)=0$ at
that point of time and it remains $0$ until the exposure of $w$. Consider a
triangle $\\{v,u,w\\}$ such that $v\prec_{s}u\prec_{s}w$, i.e., the triangle
is charged to $e$. When $u$ is exposed, from the description of the algorithm
(Algorithm 2), we encounter the triangle $\\{v,u,w\\}$ and increment the
counter $t_{e}^{\prime}$. Now consider any triangle containing $e$ but not
charged to $e$, say $\\{v,w,u^{\prime}\\}$, either $u^{\prime}$ is exposed
before $v$ or after $w$ in the stream. In the first case, $\mathsf{flag}(e)$
has not been initialized. In the second case, $\mathsf{flag}(e)=1$. In either
of the cases, observe that the algorithm does not consider changing
$t_{e}^{\prime}$. So, when $\mathsf{flag}(e)=1$ for $e\in\mathcal{F}_{1}$,
then $t_{e}^{\prime}$ is in fact $t_{e}$. The fact that the triangle
$\Delta_{e}$ is chosen uniformly at random among all the triangles charged to
$e$ can be argued in a similar fashion. ∎

1

2

3Set $\mathcal{F}_{1}\leftarrow\emptyset$. Initiate a (unweighted) reservoir
sampler RS to store (up to) $\widetilde{{\mathcal{O}}}(m/\sqrt{T})$ edges.

4Note that $\mathcal{F}_{1}$ is the set of edges stored by RS.

5for  _every vertex $u$ when its adjacency list is revealed_ do

6 Perform the following steps in parallel:

7 Step 1: for  _every edge $e=\\{u,v\\}$_ do

8

9 if  _$\\{v,u\\}\in\mathcal{F}_{1}$_ then

10 Set $\mathsf{flag}(e)=1$.

11

12 Give $e=\\{u,v\\}$ as an input to ${\sc RS}$.

13 Step 2: for  _every edge $e=\\{v,w\\}\in\mathcal{F}_{1}$_ do

14

15 if  _$\mathsf{flag}(e)=0$ and $u$ forms a triangle $\Delta_{e}$ with $e$_
then

16

17 $t^{\prime}_{e}\leftarrow t^{\prime}_{e}+1$.

18 Give $\Delta_{e}$ as input to RS that samples a triangle charged to $e$
uniformly at random.

19

20

21

22for  _each edge $e\in\mathcal{F}_{1}$_ do

23 Report $\mathsf{flag}(e),t_{e}^{\prime}$, and $\Delta_{e}$.

Algorithm 2 SampLightHelper

#### Description of SampHeavyHelper

Recall the intuition discussed to sample a heavy triangle in the overview in
Section 2.2. To make the intuition work, we use SampHeavyHelper. Note that it
stores a set $\mathcal{F}_{2}$ of edges where each edge is included in
$\mathcal{F}_{2}$ independently with probability $p=100\log
n/\varepsilon^{2}\sqrt{T}$. First, let us discuss how we essentially detect
all the heavy edges. Consider a heavy edge $e=\\{u,v\\}$ such that
$u\prec_{s}v$. If $\\{u,v\\}$ is included in $\mathcal{F}_{2}$ when $u$ is
exposed, then one can compute $t_{e}$ exactly (as we do in SampLightHelper).
But it may be the case that $e$ is not included in $\mathcal{F}_{2}$ when $u$
is exposed as we are including it in $\mathcal{F}_{2}$ with probability $p$.
However, we can guarantee that a _good fraction_ of edges of the form
$\\{u,w\\}$ are included in $\mathcal{F}_{2}$ (with high probability) such
that $\\{u,v,w\\}$ is a triangle charged to $e$. When $\\{u,v\\}$ arrives in
the stream for the second time (during the exposure of $v$), we can detect the
set $S_{e}$ of such triangles $\\{u,v,w\\}$ such that
$e=\\{u,w\\}\in\mathcal{F}_{2}$. Due to the properties of the Al model, we can
find the set $S_{e}$ for every heavy edge $e$. We can argue that $|S_{e}|/p$
approximates $t_{e}$ with high probability. Moreover, we show that a triangle
taken uniformly at random from $S_{e}$ is essentially similar to a triangle
chosen uniformly at random from all the triangles charged to $e$. The
pseudocode for SampHeavyHelper is presented in Algorithm 3 and its guarantee
is stated in 4.3. The formal discussion about how SampHeavyHelper will be
helpful in sampling a heavy triangle will be discussed in Section 4.3.

1 Set $\mathcal{F}_{2}\leftarrow\emptyset$, and $\kappa=10\log n$,
$H\leftarrow\emptyset$.

2for  _every vertex $u$ when its adjacency list is revealed_ do

3

4 Perform Steps 1 and 2 in parallel:

5 Step 1: for  _every edge $e=\\{u,v\\}$ in the stream_ do

6 Set $x_{e}=0$.

7 $H=H\setminus\\{e\\}$.

8 If $e\in\mathcal{F}_{2}$, Set $\mathsf{flag}(e)=1$.

9 else

10

11 Set $\mathsf{flag}(e)=0$.

12

13 Include $\\{u,v\\}$ in $\mathcal{F}_{2}$ with probability $p=100\log
n/\varepsilon^{2}\sqrt{T}$.

14 Step 2: for  _each edge $e=\\{x,w\\}\in\mathcal{F}_{2}$ such that
$\mathsf{flag}(e)=1$_ do

15

16

17 Determine if $\\{u,x,w\\}$ is a triangle.

18 $x_{e}\leftarrow x_{e}+1$.

19 Processing information obtained from Step 1 and 2:

20 After the adjacency list of $u$ gets exposed, for each edge $e$ revealed
during the exposure of $u$, do the following:

21 if  _${x}_{e}\geq\kappa$_ then

22

23 Include $e$ in $H$.

24 Choose a triangle $\Delta_{e}$ uniformly at random among the set of
triangles charged to $e$ and detected in Step 2.

25

26

27

28for  _each edge $e\in H$_ do

29 report $x_{e}$ and $\Delta_{e}$.

Algorithm 3 SampHeavyHelper

######  Lemma 4.3.

SampHeavyHelper (Algorithm 3) uses
$\widetilde{{\mathcal{O}}}\left({m}/{\sqrt{T}}+\sqrt{T}\right)$ space in
expectation. It reports a set of edges $\mathcal{F}_{2}$ where each $e\in E$
is included in $\mathcal{F}_{2}$ with probability $p={100\log
n}/{\varepsilon^{2}\sqrt{T}}$ independently. The algorithm stores a set of
heavy edges $H$. Also, for each $e\in H$, it stores a random variable $x_{e}$
(to possibly estimate $t_{e}$, i.e, the number of triangles charged to $e$),
and a triangle $\Delta_{e}$ charged to edge $e$ if $x_{e}\neq 0$. Moreover,
$x_{e}/p$ is a $(1\pm\varepsilon/30)$-approximation to $t_{e}$. Also, for any
triangle $\Delta$ (charged to $e$), we have $\Pr(\Delta_{e}=\Delta)$ =
$(1\pm\varepsilon/15)\cdot 1/t_{e}$.

###### Proof of 4.3.

As each edge is included in $\mathcal{F}_{2}$ with probability $p=100\log
n/\varepsilon^{2}\sqrt{T}$, $\left|\mathcal{F}_{2}\right|=100m\log
n/\varepsilon^{2}\sqrt{T}$ in expectation. For each edge $e\in H$, the
algorithm stores $x_{e}$ and possibly $\Delta_{e}$. Later in the proof, we
argue that $|H|=\mathcal{O}({\sqrt{T}})$ with high probability. So, the
expected space complexity is bounded by
$\widetilde{{\mathcal{O}}}(\left|\mathcal{F}_{2}\right|+\left|H\right|)=\widetilde{{\mathcal{O}}}\left({m}/{\sqrt{T}}+\sqrt{T}\right)$.

Now, we argue that for an edge $e=\\{u,v\\}\in H$, $x_{e}/p$ is a
$(1\pm\varepsilon/30)$-approximation to $t_{e}$ with high probability. Assume
the adjacency list of $v$ is revealed before the adjacency list of $u$. Let
$X$ be the set of triangles charged to $e=\\{u,v\\}$ and ${X}^{\prime}\subset
X$ detected in Step 2 of SampHeavyHelper when the adjacency list of $u$ is
revealed. For any triangle $\Delta=\\{u,v,w\\}$ charged to $e=\\{u,v\\}$,
$\Delta\in X^{\prime}$ if the edge $\\{v,w\\}$ has been added to
$\mathcal{F}_{2}$ when the adjacency list of $v$ was revealed. So, the
probability that the triangle $\\{u,v,w\\}$ is in $X^{\prime}$ is $p$. Note
that $x_{e}=\left|X^{\prime}\right|$ and $t_{e}=\left|X\right|$.

Using Chernoff bound, we can show that for any edge $e$, if
$t_{e}\geq\tau=900\sqrt{T}$, then with high probability, $x_{e}\geq\kappa$,
and, if $t_{e}<\tau/10$, then $x_{e}<\kappa$ with high probability.

Consider an edge $e$ with $x_{e}\geq\kappa$. Note that $t_{e}\geq\tau/10$ with
high probability. By Chernoff bound, $\widehat{t}_{e}={x}_{e}/p$ is a
$\left(1\pm\varepsilon/30\right)$-approximation to $t_{e}$ with high
probability.

From the description of the algorithm, we take a triangle $\Delta_{e}$
uniformly at random from the set $X^{\prime}$. Recall that ${X}^{\prime}$ is
the set of triangles charged to $e$ that are detected in Step 2 of
SampHeavyHelper when the adjacency list of $u$ is revealed. For any triangle
$\Delta$ charged to $e=\\{u,v\\}$, we can deduce the following:

$\mathbb{P}(\Delta_{e}=\Delta)=\Pr(\Delta\in
X^{\prime})\cdot\frac{1}{\left|X^{\prime}\right|}.$

Let the other vertex in the triangle $\Delta$ be $x$. So, $\Delta$ is included
in $X^{\prime}$ during the exposure of $u$ if the edge $\\{v,x\\}$ is included
in $\mathcal{F}_{2}$ during the exposure of $v$. So, $\mathbb{P}(\Delta\in
X^{\prime})=p$. Also, note that
$\left|X^{\prime}\right|/p=x_{e}/p=\widehat{t}_{e}$ is a
$(1\pm\varepsilon/30)$-approximation to $t_{e}$ with high probability.

Now, we bound the size of $H$. For each edge $e\in H$, $x_{e}\geq\kappa$, i.e,
$t_{e}\geq\tau/10$ with high probability. As each triangle is charged to a
unique edge, $|H|$ is bounded by $10T/\tau\leq\mathcal{O}(\sqrt{T})$. Hence,
we are done with the proof of the lemma. ∎

###  4.2 Notions of heavy and light edges and triangles

Note that, in the overview in Section 2.2, we defined an edge $e$ to be either
heavy or light based on the value of $t_{e}$, i.e., the exact number of
triangles charged to $e$. For a heavy edge $e$, as SampHeavyHelper does not
determine $t_{e}$ exactly, the notions of heavy and light edges in terms of
actual number of triangles charged to them would not be helpful in the
analysis. To cope up with that, we define an edge $e$ to be heavy or light
based on the value of $x_{e}$ in SampHeavyHelper.

######  Definition 4.4 (Heavy and light edge).

Let $e=(u,v)$ such that $u\prec_{s}v$. $x_{e}$ is the random variable that
denotes the number of triangles that are charged to $e$, and is detected by
SampHeavyHelper (Algorithm 3), when the adjacency list of $v$ is revealed. Let
$\kappa\in\mathbb{N}$ be a parameter. An edge $e\in E$ is said to be _$\kappa$
-heavy_ or simply _heavy_ if $x_{e}\geq\kappa$. Otherwise, $e$ is said to be
_$\kappa$ -light_ or simply _light_.

Now we define the notion of heavy and light triangles.

######  Definition 4.5 (Heavy and light triangle).

Let $\kappa\in\mathbb{N}$ and $\Delta$ be a triangle in the graph $G$, which
is charged to the edge $e$. $\Delta$ is said to be $\kappa$-heavy if $e$ is
$\kappa$-heavy or simply _heavy_. Otherwise, $\Delta$ is $\kappa$-light or
simply _light_.

Let $\mathcal{T}_{L}$ and $\mathcal{T}_{H}$ denote the sets of $\kappa$-light
and $\kappa$-heavy triangles in $G$, respectively, and $T_{L}$ and $T_{H}$ be
the number of $\kappa$-light and $\kappa$-heavy triangles in $G$,
respectively. Thus $T_{L}=\left|\mathcal{T}_{L}\right|$ and
$T_{H}=\left|\mathcal{T}_{H}\right|$ and $T=T_{L}+T_{H}$.

###  4.3 Descriptions of Sample-Light-Triangle and Sample-heavy-Triangle

In this section, we describe the algorithms Sample-Light-Triangle and Sample-
heavy-Triangle that essentially sample a $\kappa$-light edge and
$\kappa$-heavy edge, respectively. The two algorithms (Sample-Light-Triangle
and Sample-heavy-Triangle) are not streaming algorithms in nature, they are
working on the outputs produced by SampLightHelper and SampHeavyHelper (which
are both working on the stream in parallel).

#### Description of Sample-Light-Triangle

1

2

3Let $\mathcal{F}_{1}$ be the set of edges we get from SampLightHelper
satisfying 4.2. Also, let $H$ be the set of heavy edges we get from
SampHeavyHelper satisfying 4.3.

4Set $\tau=900\sqrt{T},\mbox{{\sc Sampled-Triangle}}\leftarrow\emptyset$.

5for  _every edge $e\in\mathcal{F}_{1}$ with $\mathsf{flag}(e)=1$ and $e\notin
H$_ do

6

7 if  _$t_{e}\leq\tau$_ then

8

9 Keep the triangle $\Delta_{e}$ charged to $e$ reported by SampLightHelper.

10 $\mbox{\sc Sampled-Triangle}\leftarrow\mbox{\sc Sampled-
Triangle}\cup\Delta_{e}$.

11

12if  _$\mbox{{\sc Sampled-Triangle}}\neq\emptyset$_ then

13

14 Report one triangle in Sampled-Triangle arbitrarily.

15

16Otherwise, return Fail.

Algorithm 4 Sample-Light-Triangle

######  Remark 1.

Here we would like to discuss why Sample-Light-Triangle uses SampHeavyHelper
along with SampLightHelper. Note that $H$ is the set of $\kappa$-heavy edges,
as determined by the algorithm SampHeavyHelper. Any edge not in $H$ is the set
of $\kappa$-light edges. It may be the case that, for an edge
$e\in\mathcal{F}_{1}$, $t_{e}\leq\tau$. But due to the approximation error in
SampHeavyHelper, $x_{e}\geq\kappa$, i.e., $e\in H$. To take care of the fact,
we consider only those edge $e\in\mathcal{F}_{1}$ such that
$\mathsf{flag}(e)=1$ and $e\notin H$.

In the following lemma, we prove that Algorithm 4 samples a $\kappa$-light
triangle uniformly.

######  Lemma 4.6.

Consider the algorithm Sample-Light-Triangle (Algorithm 4). If
$T_{L}=\Omega(\varepsilon T)$, then with high probability, the algorithm
samples a $\kappa$-light triangle uniformly, that is, with probability
$T_{L}/2m\tau$, where $T_{L}$ denotes the number of $\kappa$-light triangles
of $G$.

###### Proof.

Recall that $\mathcal{F}_{1}$ is the set of edges sampled in SampLightHelper.
Consider an edge $e_{s}$ in $\mathcal{F}_{1}$. For the time being assume that
$\left|\mathcal{F}_{1}\right|=1$. Observe that $\mathsf{flag}(e_{s})=1$ if
$e_{s}$ is included in $\mathcal{F}_{1}$ when $e_{s}$ arrives for the first
time. By 4.2, if $\mathsf{flag}(e_{s})=1$, then $t_{e_{s}}^{\prime}=t_{e_{s}}$
and $\Delta_{e_{s}}$ is a uniform triangle charged to $e$. Consider a
$\kappa$-light triangle $\Delta=\\{a,b,c\\}$ which is charged to $\\{a,c\\}$.

$\displaystyle\mathbb{P}\left(\Delta_{e_{s}}=\Delta\right)$ $\displaystyle=$
$\displaystyle\mathbb{P}(e_{s}=\\{a,c\\}~{}\mbox{and}~{}\mathsf{flag}(e_{s})=1)\times\
\mathbb{P}(\Delta_{e_{s}}=\Delta~{}|~{}e_{s}=\\{a,c\\}~{}\mbox{and}~{}\mathsf{flag}(e_{s})=1)$
$\displaystyle=$ $\displaystyle\frac{1}{2m}\times\frac{1}{t_{e}}$

Let $\Delta_{L}$ be the output of Sample-Light-Triangle. As we include
$\Delta_{e_{s}}$ to Sampled-Triangle with probability $t_{e}/\tau$, we can say
that:

$\mathbb{P}\left(\Delta_{L}=\Delta\right)=\mathbb{P}\left(\Delta_{e_{s}}=\Delta\right)\cdot\frac{t_{e}}{\tau}=\frac{1}{2m\tau}$

The probability that Algorithm 4 reports some $\kappa$-light triangle is
$T_{L}/2m\tau$ which follows by applying the union bound over all light
triangles. Observe that, under the conditional space that Algorithm 4 does not
report Fail, it returns a $\kappa$-light triangle uniformly. Since
$\left|\mathcal{F}_{1}\right|=\widetilde{{\mathcal{O}}}(m/\sqrt{T})$ and
$T_{L}=\Omega(\varepsilon T)$, with high probability, Sample-Light-Triangle
reports a light triangle uniformly at random. ∎

#### Description of Sample-heavy-Triangle

1

2Let $H$ be the set of heavy edges we get from SampHeavyHelper satisfying 4.3.

3if  _$H=\emptyset$_ then

4

5 Report ABORT and return FAIL.

6

7Choose an edge $r\in H$ proportional to its weight, where the weight of an
edge $e\in H$ is defined as $\frac{x_{e}}{\sum\limits_{e^{\prime}\in
H}x_{e^{\prime}}}$.

8Let $\Delta_{r}$ be the triangle charged to the edge $r$, as reported by
SampHeavyHelper.

9Report $\Delta_{r}$ as the output $\Delta_{H}$ (as the sampled heavy
triangle).

10

Algorithm 5 Sample-Heavy-Triangle

Let us begin by showing that the estimate of the number of heavy triangles
$\widehat{T}_{H}$ found by SampHeavyHelper is close to $T_{H}$, the actual
number of heavy triangles of $G$.

######  Corollary 4.7.

With high probability, $\widehat{T}_{H}=\frac{1}{p}\sum\limits_{e\in H}x_{e}$
is a $\left(1\pm\varepsilon/30\right)$-approximation to $T_{H}$.

###### Proof.

From 4.3, we know that for a $\kappa$-heavy edge $e$ (that is when
$x_{e}\geq\kappa$), $\widehat{t}_{e}={x}_{e}/p$ is a
$\left(1\pm\varepsilon/30\right)$-approximation to $t_{e}$. Since
$\widehat{T}_{H}=\sum_{e\in H}x_{e}/p$, this implies that $\widehat{T}_{H}$ is
a $\left(1\pm\varepsilon/30\right)$-approximation to $T_{H}$. ∎

Now we show that Sample-Heavy-Triangle (Algorithm 5) returns a $\kappa$-heavy
triangle almost uniformly.

######  Lemma 4.8.

Consider Algorithm 5. Let us denote the output produced by Sample-heavy-
Triangle as $\Delta_{H}$, unless it returns Fail. Then, with high probability,
$\Delta_{H}$ follows a distribution $\mathcal{D}_{H}$ over the set of
$\kappa$-heavy triangle such that
$\mathcal{D}_{H}(\Delta)=\mathbb{P}(\Delta_{H}=\Delta)=(1\pm\varepsilon/5)/T_{H}$
for any $\kappa$-heavy triangle $\Delta$.

###### Proof.

Consider a $\kappa$-heavy edge $e=\\{u,v\\}$ such that the adjacency list of
$u$ is revealed sometime after the adjacency list of $v$ is revealed. Let
$\mathcal{E}_{e}$ be the event that we report some triangle charged to $e$.
From the description of SampHeavyHelper, we can say that

$\mathbb{P}(\mathcal{E}_{e})=\frac{x_{e}}{\sum\limits_{e\in
H}{x_{e}}}=\frac{x_{e}/p}{\sum\limits_{e\in
H}{x_{e}/p}}=\frac{\widehat{t}_{e}}{\widehat{T}_{H}}=\left(1\pm\frac{\varepsilon}{10}\right)\frac{t_{e}}{T_{H}}.$

This is because $\widehat{t}_{e}$ and $\widehat{T}_{H}$ are
$(1\pm\varepsilon/30)$-approximations of $t_{e}$ and $T_{H}$, respectively,
which follows from 4.3 and 4.7. Now consider a triangle
$\Delta\in\mathcal{T}_{H}$ and let us calculate that our algorithm reports
$\Delta$ as the output $\Delta_{H}$. Let $e$ be the edge to which $\Delta$ is
charged. Observe the following:

$\displaystyle\mathbb{P}(\Delta_{H}=\Delta)$
$\displaystyle=\mathbb{P}(\mathcal{E}_{e})\cdot\mathbb{P}(\Delta_{H}=\Delta~{}|~{}\mathcal{E}_{e})$
$\displaystyle=\left(1\pm\frac{\varepsilon}{10}\right)\frac{t_{e}}{T_{H}}\cdot\mathbb{P}(\Delta_{H}=\Delta~{}|~{}\mathcal{E}_{e})$
$\displaystyle=\left(1\pm\frac{\varepsilon}{10}\right)\frac{t_{e}}{T_{H}}\cdot\mathbb{P}(\Delta_{e}=\Delta~{}|~{}\mathcal{E}_{e})$
$\displaystyle=\left(1\pm\frac{\varepsilon}{10}\right)\frac{t_{e}}{T_{H}}\cdot\left(1\pm\frac{\varepsilon}{15}\right)\cdot\frac{1}{t_{e}}$
$\displaystyle[\mbox{From \lx@cref{creftypecap~refnum}{lem:subroutine2}}]$
$\displaystyle=\left(1\pm\frac{\varepsilon}{5}\right)\cdot\frac{1}{T_{H}}$

∎

###  4.4  One-pass algorithm with space complexity
$\widetilde{{\mathcal{O}}}(m/\sqrt{T}+\sqrt{T})$.

In this section, we discuss Triangle-Sample-Al-1pass (Algorithm 6) as our one-
pass algorithm for Triangle Sampling in the Al model, with space complexity
$\widetilde{{\mathcal{O}}}(m/\sqrt{T}+\sqrt{T})$. Triangle-Sample-Al-1pass
runs SampLightHelper (Algorithm 2) and SampHeavyHelper (Algorithm 3) in
parallel during the stream. In the post processing phase after the stream
ends, Triangle-Sample-Al-1pass has again two subroutines Sample-Light-Triangle
(Algorithm 4) and Sample-Heavy-Triangle (Algorithm 5) which essentially
samples $\kappa$-light and $\kappa$-heavy triangle, as guaranteed in Section
4.3. Finally, Triangle-Sample-Al-1pass combines the outputs of Sample-Light-
Triangle and Sample-Heavy-Triangle to report the final desired output.

1

2Set $p=100\log n/\varepsilon^{2}\sqrt{T}$ and $\kappa=10{\log n}$.

3Call SampLightHelper and SampHeavyHelper in parallel.

4Process at the end of the stream:

5Consider the set $H$ of heavy edges and the value of $x_{e}$ for each edge
$e\in H$, as reported by SampHeavyHelper.

6Compute $\widehat{T}_{H}=\sum\limits_{e\in H}\widehat{t}_{e}$, where
$\widehat{t}_{e}=\frac{1}{p}x_{e}$.

7Call Sample-Light-Triangle. Let $\Delta_{L}$ be the output.

8Call Sample-Heavy-Triangle. Let $\Delta_{H}$ be the output.

9If either Sample-Light-Triangle or Sample-Heavy-Triangle report Fail, then
report Fail and ABORT the process.

10if  _$\widehat{T}_{H}\leq\varepsilon T/10$_ then

11

12 Report $\Delta_{L}$ as the output.

13

14if  _$\widehat{T}_{H}\geq\left(1-\varepsilon/10\right)T$_ then

15

16

17 Report $\Delta_{H}$ as the output.

18

Report $\Delta_{H}$ with probability $\widehat{T}_{H}/T$ and $\Delta_{L}$ with
probability $1-\widehat{T}_{H}/T$.

Algorithm 6 Triangle Sampling in 1-pass Al Model

In 4.9, we show that the space complexity of algorithm 6 is
$\widetilde{{\mathcal{O}}}(m/\sqrt{T}+\sqrt{T})$ and show that algorithm 6
solves Triangle Sampling in Al model with high probability.

######  Theorem 4.9.

Consider Algorithm 6. It uses
$\widetilde{{\mathcal{O}}}\left({m}/{\sqrt{T}}+\sqrt{T}\right)$ space in
expectation. Moreover, it reports a triangle from a distribution $\mathcal{D}$
over the set of triangles in $G$ such that
$||\mathcal{D}-\mathcal{U}||_{1}\leq\varepsilon$, where $\mathcal{U}$ denotes
the uniform distribution over the set of all triangles in $G$.

###### Proof.

The space complexity follows from 4.2 and 4.3. In order to prove the other
part, we break the analysis into three parts.

##### Case 1: $\widehat{T}_{H}\leq\frac{\varepsilon}{10}T$:

In this case, we report the output $\Delta_{L}$ produced by Sample-Light-
Triangle. From Lemma 4.6, for any light triangle $\Delta\in\mathcal{T}_{L},$
$\mathbb{P}(\Delta_{L}=\Delta)=\frac{1}{T_{L}}.$ Note that, in this case the
algorithm never reports a triangle that is not in $\mathcal{T}_{L}$. So,

$\mathcal{D}(\Delta)=\begin{cases}1/T_{L}&\Delta\in\mathcal{T}_{L}\\\
0&\Delta\in\mathcal{T}_{H}\end{cases}$

Thus,

$||\mathcal{D}-\mathcal{U}||_{1}=T_{L}\cdot\left|{1}/{T_{L}}-{1}/{T}\right|+T_{H}\cdot{1}/{T}.$
(1)

As $\widehat{T}_{H}$ is a $\left(1\pm\varepsilon/30\right)$-approximation of
$T_{H}$, in this case
${T_{H}}\leq\frac{\frac{\varepsilon}{10}T}{1-\varepsilon/30}\leq\varepsilon
T/8$. So, $\left(1-\varepsilon/8\right)T\leq T_{L}\leq T$. Combining the
bounds on $T_{L}$ and $T_{H}$ in Equation (1), we conclude that
$||\mathcal{D}-\mathcal{U}||_{1}\leq\varepsilon$.

##### Case 2: $\widehat{T}_{H}\geq\left(1-\frac{\varepsilon}{10}\right)T$:

In this case, we report the output $\Delta_{H}$ produced by Sample-Heavy-
Triangle. From Lemma 4.8, for any triangle $\Delta\in\mathcal{T}_{H}$, we have
$\mathbb{P}(\Delta_{H}=\Delta)=(1\pm\varepsilon/5)/T_{H}$. Note that, here the
algorithm never reports a triangle that is in $\mathcal{T}_{L}$. So,

$\mathcal{D}(\Delta)=\begin{cases}0&\Delta\in\mathcal{T}_{L}\\\
(1\pm\varepsilon/5)/T_{H}&\Delta\in\mathcal{T}_{H}\end{cases}$

Thus,

$\small||\mathcal{D}-\mathcal{U}||_{1}=\frac{T_{L}}{T}+T_{H}\cdot\max\left\\{\left|\left(1-\frac{\varepsilon}{5}\right)\frac{1}{T_{H}}-\frac{1}{T}\right|,\left|\left(1+\frac{\varepsilon}{5}\right)\frac{1}{T_{H}}-\frac{1}{T}\right|\right\\}.$
(2)

As $\widehat{T}_{H}$ is a $\left(1\pm\varepsilon/30\right)$-approximation of
$T_{H}$,
${T_{H}}\geq\frac{(1-\varepsilon/10)}{1+\varepsilon/30}T\geq(1-\varepsilon/5)T$.
So, $T_{L}\leq\varepsilon T/5$. Putting the bounds on $T_{L}$ and $T_{H}$ in
Equation 2, we have $||\mathcal{D}-\mathcal{U}||_{1}\leq\varepsilon$.

##### Case 3:
$\frac{\varepsilon}{10}T<\widehat{T}_{H}<\left(1-\frac{\varepsilon}{10}\right)T$:

In this case, we report $\Delta_{H}$ produced by Sample-Heavy-Triangle with
probability $\widehat{T}_{H}/T$ and $\Delta_{L}$ produced by Sample-Light-
Triangle with probability $1-\widehat{T}_{H}/T$. Let $\Delta_{s}$ be the
triangle reported by the algorithm. So, for any light triangle
$\Delta\in\mathcal{T}_{L}$, we get

$\mathbb{P}(\Delta_{s}=\Delta)=\left(1-\frac{\widehat{T}_{H}}{T}\right)\times\frac{1}{T_{L}}$

From Lemma 4.8, for any heavy triangle $\Delta\in\mathcal{T}_{H}$, we have:

$\mathbb{P}(\Delta_{s}=\Delta)=\frac{\widehat{T}_{H}}{T}\cdot(1\pm\frac{\varepsilon}{5})\frac{1}{{T_{H}}}.$

$\mathcal{D}(\Delta)=\begin{cases}\left(1-\frac{\widehat{T}_{H}}{T}\right)\cdot\frac{1}{T_{L}}&\Delta\in\mathcal{T}_{L}\\\
\frac{\widehat{T}_{H}}{T}\cdot(1\pm\frac{\varepsilon}{5})\frac{1}{{T_{H}}}&\Delta\in\mathcal{T}_{H}\end{cases}$

So,

$\displaystyle||\mathcal{D}-\mathcal{U}||_{1}$
$\displaystyle=T_{L}\cdot\left|\frac{1}{T}-\left(1-\frac{\widehat{T}_{H}}{T}\right)\frac{1}{T_{L}}\right|$
$\displaystyle\;\;\;\;\;\;\;\;+{T_{H}}\cdot\max\left\\{\left|\left(1-\frac{\varepsilon}{5}\right)\frac{1}{T_{H}}\cdot\frac{\widehat{T}_{H}}{T}-\frac{1}{T}\right|,\left|\left(1+\frac{\varepsilon}{5}\right)\frac{1}{T_{H}}\frac{\widehat{T}_{H}}{T}-\frac{1}{T}\right|\right\\}.$

As $\widehat{T}_{H}$ is a $\left(1\pm\varepsilon/30\right)$-approximation of
$T_{H}$, in this case $\frac{\varepsilon
T/10}{1+\varepsilon/30}\leq{T_{H}}\leq T$. Also, $T_{L}\leq T$. Combining
these bounds in the above expression, we conclude that
$||\mathcal{D}-\mathcal{U}||_{1}\leq\varepsilon$. ∎

###  4.5 Improving the space complexity of Algorithm 6 to
$\widetilde{{\mathcal{O}}}(m/\sqrt{T})$

The space complexity $\widetilde{{\mathcal{O}}}(m/\sqrt{T}+\sqrt{T})$ of
Algorithm 6 (as stated in 4.9) is due to the same space complexity of
SampHeavyHelper (as stated in 4.3). The space complexity
$\widetilde{{\mathcal{O}}}(m/\sqrt{T}+\sqrt{T})$ of SampHeavyHelper is due to
the fact that we store the set of heavy vertex $H$ in SampHeavyHelper and we
argue that $|H|=\mathcal{O}(\sqrt{T})$. Here, we argue that we do not need to
store the set $H$ explicitly. By Line 17–19 of SampHeavyHelper (Algorithm 3),
an edge $e$ is included to $H$ if $x_{e}\geq\kappa$. Also, we choose a
previously detected triangle $\Delta_{e}$ uniformly at random among the set of
triangles charged to $e$. By 4.3, with high probability, ${x_{e}}/{p}$ is
$(1+\varepsilon/30)$-approximation to $t_{e}$, and for any triangle $\Delta$
(charged to $e$), we have $\Pr(\Delta_{e}=\Delta)$ is
$(1\pm\varepsilon/15)\cdot 1/t_{e}$. So, instead of storing $H$ explicitly, we
can initiate a weighted reservoir sampler WRS (to store one element) and we
give $(\Delta_{e},x_{e}/p)$ to WRS when we detect a heavy edge $e$. Let the
final sample reported by WRS be $(w,\Delta)$. We can argue that triangle
$\Delta$ satisfies the guarantee by Sample-heavy-Triangle as stated in 4.8. It
is important to note that the set $H$ also plays a crucial role in Sample-
Light-Triangle (see Line 3 of Algorithm 4 and 1). That is, in Sample-Light-
Triangle, we check for each $e\in\mathcal{F}_{1}$, whether
$\mathsf{flag}(e)=1$ and $e\notin H$. But, now we are not storing $H$
explicitly. However, we run SampLightHelper and SampHeavyHelper in parallel.
An edge $e$ is possibly detected in SampHeavyHelper as a heavy edge when $e$
arrives for the second time and $\mathsf{flag}(e)$ is possibly set to $1$ in
SampLightHelper when $e$ comes for the second time. So, when $e$ is detected
to be a heavy edge, we can set $\mathsf{flag}(e)$ to $0$. Thus, the triangle
$\Delta$ reported by Sample-Light-Triangle satisfies the guarantee as stated
in 4.6.

Putting things together, we conclude that, in one pass, the space complexity
of Triangle Sampling is $\widetilde{{\mathcal{O}}}(m/\sqrt{T})$ in the Al
model, hence we are done with the proof of 4.1.

##  5 Conclusion

In this work, we have studied the problem of triangle sampling in three
popular streaming models. Our main contribution in this work is designing
triangle sampling algorithms in the Al model, where the counting algorithms
can not be generalized to get sampling algorithms, and we designed almost
optimal algorithms in these scenarios. We showed that in Ea/Va models,
triangle counting algorithms can be generalized to design triangle sampling
algorithms.

The main open question left is to study this problem in the Random Order Model
(Ra model), where the edges of the graph appear in random order. In this
model, the current best space complexity of triangle counting is
$\widetilde{\mathcal{O}}\left(m/\sqrt{T}\right)$ by McGregor and Vorotnikova
[29]. So the main open question is:

######  Question 5.1.

Can one design a triangle sampling algorithm for Ra model matching the bounds
of its counting variant?

Another open question in this context is:

######  Question 5.2.

Can one design efficient sampling algorithms for other substructures in the
streaming models?

## References

  * [1] N. Alon, R. Yuster, and U. Zwick.  Finding and Counting Given Length Cycles.  Algorithmica, 17(3):209–223, 1997.
  * [2] M. Arenas, L. A. Croquevielle, R. Jayaram, and C. Riveros.  When is approximate counting for conjunctive queries tractable?  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1015–1027, 2021.
  * [3] S. Assadi, M. Kapralov, and S. Khanna.  A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling.  arXiv preprint arXiv:1811.07780, 2018.
  * [4] Z. Bar-Yossef, R. Kumar, and D. Sivakumar.  Reductions in streaming algorithms, with an application to counting triangles in graphs.  In SODA, volume 2, pages 623–632, 2002.
  * [5] S. K. Bera and A. Chakrabarti.  Towards Tighter Space Bounds for Counting Triangles and other Substructures in Graph Streams.  In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, STACS, 2017.
  * [6] A. S. Biswas, T. Eden, and R. Rubinfeld.  Towards a decomposition-optimal algorithm for counting and sampling arbitrary motifs in sublinear time.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2021.
  * [7] E. Bloedorn, N. J. Rothleder, D. DeBarr, and L. Rosen.  Relational graph analysis with real-world constraints: An application in irs tax fraud detection.  Grobelnik et al.[63], 2005.
  * [8] V. Braverman, R. Ostrovsky, and D. Vilenchik.  How hard is counting triangles in the streaming model?  In International Colloquium on Automata, Languages, and Programming, pages 244–254. Springer, 2013.
  * [9] L. Bulteau, V. Froese, K. Kutzkov, and R. Pagh.  Triangle Counting in Dynamic Graph Streams.  Algorithmica, 76(1):259–278, 2016.
  * [10] L. S. Buriol, G. Frahling, S. Leonardi, A. Marchetti-Spaccamela, and C. Sohler.  Counting Triangles in Data Streams.  In Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pages 253–262, 2006.
  * [11] H. Chen and S. Mengel.  The logic of counting query answers.  In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12. IEEE, 2017.
  * [12] Y. Chen and K. Yi.  Random sampling and size estimation over cyclic joins.  In 23rd International Conference on Database Theory (ICDT 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [13] G. Cormode and H. Jowhari.  A second look at counting triangles in graph streams.  Theoretical Computer Science, 552:44–51, 2014.
  * [14] D. P. Dubhashi and A. Panconesi.  Concentration of Measure for the Analysis of Randomized Algorithms.  Cambridge University Press, 2009.
  * [15] A. Durand and S. Mengel.  Structural tractability of counting of solutions to conjunctive queries.  In Proceedings of the 16th International Conference on Database Theory, pages 81–92, 2013.
  * [16] T. Eden, S. Narayanan, and J. Tetek.  Sampling an edge in sublinear time exactly and optimally.  In T. Kavitha and K. Mehlhorn, editors, 2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023, pages 253–260. SIAM, 2023.
  * [17] T. Eden, D. Ron, and W. Rosenbaum.  Almost optimal bounds for sublinear-time sampling of k-cliques in bounded arboricity graphs.  In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [18] T. Eden and W. Rosenbaum.  On Sampling Edges Almost Uniformly.  In Proceedings of the 1st Symposium on Simplicity in Algorithms, SOSA, volume 61, pages 7:1–7:9, 2018.
  * [19] H. Fichtenberger, M. Gao, and P. Peng.  Sampling arbitrary subgraphs exactly uniformly in sublinear time.  In A. Czumaj, A. Dawar, and E. Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 45:1–45:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [20] R. Jayaram and J. Kallaugher.  An optimal algorithm for triangle counting in the stream.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), volume 207 of LIPIcs, pages 11:1–11:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [21] H. Jowhari and M. Ghodsi.  New Streaming Algorithms for Counting Triangles in Graphs.  In International Computing and Combinatorics Conference, pages 710–716. Springer, 2005.
  * [22] J. Kallaugher, M. Kapralov, and E. Price.  The sketching complexity of graph and hypergraph counting.  In M. Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 556–567. IEEE Computer Society, 2018.
  * [23] J. Kallaugher, A. McGregor, E. Price, and S. Vorotnikova.  The complexity of counting cycles in the adjacency list streaming model.  In D. Suciu, S. Skritek, and C. Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 119–133. ACM, 2019.
  * [24] J. Kallaugher, A. McGregor, E. Price, and S. Vorotnikova.  The Complexity of Counting Cycles in the Adjacency List Streaming Model.  In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 119–133, 2019.
  * [25] J. Kallaugher and E. Price.  A Hybrid Sampling Scheme for Triangle Counting.  In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1778 – 1797, 2017.
  * [26] D. M. Kane, K. Mehlhorn, T. Sauerwald, and H. Sun.  Counting arbitrary subgraphs in data streams.  In A. Czumaj, K. Mehlhorn, A. M. Pitts, and R. Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, volume 7392 of Lecture Notes in Computer Science, pages 598–609. Springer, 2012.
  * [27] M. N. Kolountzakis, G. L. Miller, R. Peng, and C. E. Tsourakakis.  Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning.  Internet Mathematics, 8(1-2):161–185, 2012.
  * [28] A. McGregor.  Graph Stream Algorithms: A Survey.  ACM SIGMOD Record, 43(1):9–20, 2014.
  * [29] A. McGregor and S. Vorotnikova.  Triangle and Four Cycle Counting in the Data Stream Model.  In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 445–456, 2020.
  * [30] A. McGregor, S. Vorotnikova, and H. T. Vu.  Better Algorithms for Counting Triangles in Data Streams.  In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pages 401–411, 2016.
  * [31] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon.  Network motifs: simple building blocks of complex networks.  Science, 298(5594):824–827, 2002.
  * [32] S. Muthukrishnan et al.  Data streams: Algorithms and applications.  Foundations and Trends® in Theoretical Computer Science, 1(2):117–236, 2005.
  * [33] R. Pagh and C. E. Tsourakakis.  Colorful triangle counting and a mapreduce implementation.  Information Processing Letters, 112(7):277–281, 2012.
  * [34] A. Pavan, K. Tangwongsan, S. Tirthapura, and K.-L. Wu.  Counting and sampling triangles from a graph stream.  Proceedings of the VLDB Endowment, 6(14):1870–1881, 2013.
  * [35] I. Rivin.  Counting cycles and finite dimensional lp norms.  Advances in Applied Mathematics, 29(4):647–662, 2002.
  * [36] J. Scott, T. Ideker, R. M. Karp, and R. Sharan.  Efficient algorithms for detecting signaling pathways in protein interaction networks.  Journal of Computational Biology, 13(2):133–144, 2006.
  * [37] A. A. Sherstov.  Communication lower bounds using directional derivatives.  J. ACM, 61(6):34:1–34:71, 2014.
  * [38] T. Shlomi, D. Segal, E. Ruppin, and R. Sharan.  Qpath: a method for querying pathways in a protein-protein interaction network.  BMC bioinformatics, 7:1–9, 2006.
  * [39] J. Tetek and M. Thorup.  Edge sampling and graph parameter estimation via vertex neighborhood accesses.  In S. Leonardi and A. Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1116–1129. ACM, 2022.
  * [40] J. Ugander, L. Backstrom, and J. Kleinberg.  Subgraph frequencies: Mapping the empirical and extremal geography of large graph collections.  In Proceedings of the 22nd international conference on World Wide Web, pages 1307–1318, 2013.
  * [41] J. S. Vitter.  Random sampling with a reservoir.  ACM Trans. Math. Softw., 11(1):37–57, 1985.
  * [42] Z. Zhao, R. Christensen, F. Li, X. Hu, and K. Yi.  Random sampling over joins revisited.  In Proceedings of the 2018 International Conference on Management of Data, pages 1525–1539, 2018.

##  Appendix A Remarks from Section 1

######  Remark 2.

(Sampling lower bounds from counting results). The lower bounds stated in
Theorem 1.1 follow from the lower bounds for counting version of the problems
[24, 8, 5]. All the triangle counting lower bounds are for the algorithms that
distinguish between $0$ and $T$ triangles. Let $G$ be the input graph for
counting triangles. Let us now consider a new graph $G^{\prime}=G\cup H$,
where $H$ is a clique on $\Theta(T^{1/3})$ vertices. If we run $O(1)$
instances of our sampling algorithm over $G^{\prime}$, then from the samples,
we can distinguish whether $G$ contains $T$ triangles or $0$ triangles
depending on whether we get a triangle outside $H$ as a sample or not,
respectively. The formal statements of the lower bounds are presented in
Appendix C.

######  Remark 3.

(Regarding the threshold $T$). We assume that the parameter $T$ (a promised
lower bound on $\left|t(G)\right|$) is at least polynomial in $\log n$ and
$1/\varepsilon$, that is, $T\geq\mbox{{poly}}(\log n,1/\varepsilon)$.
Otherwise, the trivial streaming algorithm that stores all the edges matches
the stated bounds in the above results. We assume that we know a lower bound
on $T$. The promise $T$ on the number of structures is a standard assumption
for estimating substructures (such as triangles) in the world of graph
streaming algorithms [22, 26, 23, 30, 5]. 151515Here we have cited a few.
However, there are huge amount of relevant literature. To make the exposition
simple, While describing our algorithm, we assume that we know the exact
values of $m$ and $\left|t(G)\right|=T$. We would like to note that the
algorithm can be modified when we do not known $m$ and know a lower bound $T$
on $\left|t(G)\right|$ such that $T$ is at least a constant factor of
$\Omega(\left|t(G)\right|)$. However, the algorithms can be suitably modified
using standard techniques from graph streaming algorithms to work for unknown
$m$ and a lower bound on $|t(G)|$. Our algorithms can adapt to the value of
$m$ as stream progresses. The assumption on $T$ can be removed by running
$\mathcal{O}(\log n)$ parallel instances of our algorithm with
$T=T_{1},\ldots,T=T_{\mathcal{O}(\log n)}$ such that $T_{1}$ is the promised
lower bound on $\left|t(G)\right|$ and $T_{\mathcal{O}(\log
n)}=\Theta(n^{3})$. If we run the triangle counting algorithm in parallel,
then at the end, we can know an approximate value $\widehat{t}$ for
$\Theta(\left|t(G)\right|)$ such that $\frac{|t(G)|}{2}\leq\widehat{t}\leq
2|t(G)|$. Then use the output of $T=T_{i}$ such that $i$ is the highest index
satisfying $T_{i}\geq\frac{1}{4}\widehat{t}$.

##  Appendix B Triangle Sampling in Ea/Va Model

We discuss our triangle sampling algorithms for Ea and Va models. We start by
first describing the $3$-pass algorithm.

###  B.1 Multi-pass Sampling in Ea/Va Model

######  Theorem B.1.

Triangle Sampling can be solved in
$\widetilde{{\mathcal{O}}}\left(m^{3/2}/T\right)$ space in Ea/Va model in
$3$-passes.

Let us first discuss our intuition of the algorithm. Let us consider an
ordering $\prec$ on the vertices of $G$ such that $u\prec v$ implies
$\deg(u)\leq\deg(v)$. For a triangle $\\{u,v,w\\}$ with $u\prec v\prec w$, we
charge the triangle to the edge $\\{u,v\\}$.

Let us discuss the following algorithm to sample a triangle uniformly at
random. First let us take an edge $\\{u,v\\}$ uniformly at random from the
graph. Without loss of generality, let us assume that $u\prec v$. If
$\deg(u)\leq\sqrt{2m}$, then we take a neighbor $w$ of $u$ uniformly at
random, then check whether $\\{u,v,w\\}$ is a triangle and $u\prec v\prec w$.
If yes, we report the triangle $\\{u,v,w\\}$ with probability
$\deg(u)/\sqrt{2m}$. If $\deg(u)>\sqrt{2m}$, then choose a vertex $w$ from the
graph such that the probability a particular vertex is chosen as $w$ is
proportional to the degree of the vertex. Then check whether $\\{u,v,w\\}$ is
a triangle and $u\prec v\prec w$. If yes, we report the triangle $\\{u,v,w\\}$
as the output.

We can argue that the above procedure reports a triangle from the graph
uniformly at random with probability $\Omega(T/m^{3/2})$. To boost the success
probability, one can repeat the above procedure
$\widetilde{{\mathcal{O}}}{(m^{3/2}/T)}$ times.

Now we will describe our streaming implementation of this above intuition in
Algorithm 7, and thereafter we analyse its correctness.

1

2Pass 1: Sample two random edges $\\{u,v\\}$ and $\\{x,y\\}$ from the stream
$\mathcal{M}$.

3Pass 2: Find the degrees of $u$ and $v$, that is, $\mathrm{deg}(u)$ and
$\deg(v)$, and the degrees of $x$ and $y$, that is, $\deg(x)$ and $\deg(y)$,
respectively.

4Find random neighbors $u^{\prime}$ of $u$ and $v^{\prime}$ of $v$,
respectively.

5Process: Without loss of generality, let us assume $u\prec v$. Perform the
following two operations parallely.

6if  _$\mathrm{deg}(u)\leq\sqrt{2m}$_ then

7

8 Set $w\leftarrow u^{\prime}$.

9 Proceed to Pass 3 with probability $\deg(u)/\sqrt{2m}$.

10

11if  _$\deg(u) >\sqrt{2m}$_ then

12

13 $w\leftarrow\mbox{Unif}\\{x,y\\}$.

14 if  _$\deg(w)\leq\sqrt{2m}$_ then

15

16 FAIL and ABORT the process.

17

18 else

19

20 Proceed to Pass 3 with probability $\sqrt{2m}/\deg(w)$.

21

22 Pass 3: if  _$u,v$ and $w$ form a triangle and $u\prec v\prec w$_ then

23

24 Output the triangle $\\{u,v,w\\}$.

25

Algorithm 7 Triangle Sampling in $3$-pass Ea/Va Model

Now let us prove Theorem B.1.

###### Proof of Theorem B.1.

We start with the space complexity.

##### Space Complexity:

As seen in Algorithm 7, all the passes require $\mathcal{O}(1)$ space. Since
we are running $\widetilde{\mathcal{O}}(m^{3/2}/T)$ instances of Algorithm 7
in parallel, the total space used is $\widetilde{\mathcal{O}}(m^{3/2}/T)$.

##### Proof of Correctness:

Let us consider an arbitrary triangle $\Delta=\\{u,v,w\\}$ such that $u\prec
v\prec w$. We argue that the probability that $\Delta$ is sampled by Algorithm
7 is $1/\sqrt{2}m^{3/2}$. Note that $\Delta$ has been sampled by Algorithm 7
only if the edge $\\{u,v\\}$ has been sampled in Pass 1, as well as $w$ has
been chosen in Pass 2. Thus the probability that $\Delta$ has been sampled by
Algorithm 7 can be written as follows:

$\displaystyle\mathbb{P}(\Delta\ \mbox{is been sampled})=\mathbb{P}(\\{u,v\\}\
\mbox{is sampled in {\bf Pass 1}})\times\ \mathbb{P}(w\ \mbox{is chosen in
{\bf Pass 2}}).$ (3)

Now let us compute the second term in Equation 3. We consider the following
two cases depending upon the degree of the vertex $u$.

##### Case 1: $\deg(u)\leq\sqrt{2m}$:

Note that the algorithm finds a random neighbor $u^{\prime}$ of $u$ in Pass 2
in Line 7. Then in the Process step, the algorithm proceeds with probability
$\deg(u)/\sqrt{2m}$, and sets $w$ as $u^{\prime}$. Since $u^{\prime}$ has been
chosen randomly among all the neighbors of $u$, the vertex $w$ is sampled with
probability $1/\deg(u)$. Hence,

$\displaystyle\mathbb{P}(\Delta\ \mbox{is been
sampled})=\frac{1}{m}\times\frac{\deg(u)}{\sqrt{2m}}\times\frac{1}{\deg(u)}=\frac{1}{\sqrt{2}m^{3/2}}.$

##### Case 2: $\deg(u)>\sqrt{2m}$:

The vertex $w$ is chosen uniformly among the vertices $\\{x,y\\}$ with equal
probability. In that case, the probability that $w$ is sampled is as follows:

$\mathbb{P}(w\in\\{x,y\\})\times\frac{1}{2}\times\frac{\sqrt{2m}}{\deg(w)}=\frac{\deg(w)}{m}\times\frac{1}{2}\times\frac{\sqrt{2m}}{\deg(w)}=\frac{1}{\sqrt{2m}}.$

Hence,

$\displaystyle\mathbb{P}(\Delta\ \mbox{is been
sampled})=\frac{1}{m}\times\frac{1}{\sqrt{2m}}=\frac{1}{\sqrt{2}m^{3/2}}.$

Note that till now we have been arguing for a fixed triangle $\Delta$. Using
the union bound over the $T$ triangles of $G$, we conclude that the
probability that any triangle has been sampled by Algorithm 7 in a single
execution is $T/\sqrt{2}m^{\frac{3}{2}}$.

Since we are running $t=\widetilde{{\mathcal{O}}}(m^{\frac{3}{2}}/T)$
instances of Algorithm 7 in parallel, the probability that no triangle has
been sampled is at most $(1-T/\sqrt{2}m^{\frac{3}{2}})^{t}\leq
1/\mathsf{poly}(n)$.

Now let us prove that Algorithm 7 has sampled a triangle uniformly among all
the triangles of the graph $G$. So, let us now work on the conditional space
that a triangle has been sampled by Algorithm 7. Under this conditional space,
the probability that the particular triangle $\Delta$ has been sampled is:

$\displaystyle\mathbb{P}\left(\frac{\Delta\ \mbox{has been sampled}}{\mbox{A
triangle has been
sampled}}\right)=\frac{\frac{1}{\sqrt{2}m^{\frac{3}{2}}}}{\frac{T}{\sqrt{2}m^{\frac{3}{2}}}}=\frac{1}{T}$

Thus the triangle $\Delta$ has been sampled uniformly by Algorithm 7. This
completes the proof of Theorem B.1. ∎

###  B.2 $1$-Pass Triangle Sampling in Ea/Va Model

######  Theorem B.2.

Triangle Sampling can be solved by using
$\widetilde{{\mathcal{O}}}\left(\min\\{m,m^{2}/T\\}\right)$ space in Ea/Va
model in $1$-pass.

Let us consider an ordering $\pi:E\rightarrow|E|$ over the edges of the graph
such that $\pi$ is a bijection. 161616In particular, $\pi$ refers to the order
in which the edges of the graph will come in the streaming. Let us discuss an
algorithm to sample a triangle uniformly. Take two edges $\\{u,v\\}$ and
$\\{u^{\prime},v^{\prime}\\}$ from the graph uniformly at random and with
replacement. If the two edges have exactly one common vertex (say
$u=u^{\prime}$), then check whether $\\{v,v^{\prime}\\}$ is an edge, i.e.,
$\\{u,v,v^{\prime}\\}$ form a triangle. If yes and
$\pi(\\{v,v^{\prime}\\})>\pi(\\{u,v\\}),\pi(\\{u,v^{\prime}\\})$, report the
triangle as the output. We can argue that the above algorithm samples a
triangle uniformly at random with probability $\Omega(T/m^{2})$. We repeat the
above procedure $\widetilde{{\mathcal{O}}}{(m^{2}/T)}$ times to boost the
success probability.

In order to implement the above intuition in the streaming, we use a reservoir
sampler. The streaming implementation is described in Algorithm 8, and
thereafter we prove its correctness.

1

2Initiate a Reservoir sampler RS to store two edges $e_{1},e_{2}$ uniformly at
random with replacement from the stream.

3for  _each edge $e$ in the streaming_ do

4 Give $e$ to as the input to the RS.

5 After the execution of RS,

6 $\\{e_{1}^{\prime},e_{2}^{\prime}\\}\leftarrow RS$.

7 if  _$e\notin\\{e_{1}^{\prime},e_{2}^{\prime}\\}$_ then

8

9 Check if $e$ forms an edge with the two edges
$e_{1}^{\prime},e_{2}^{\prime}$ sampled by RS.

10 Let the respective triangle be
$\Delta=\\{e_{1}^{\prime},e_{2}^{\prime},e\\}$.

11

12 else

13 Delete any information (possible about some triangle) stored except the two
edges (one of them is $e$ itself) sampled by RS.

14

15if  _there is any triangle $\Delta$ stored_ then

16

17 Output $\Delta$.

18

19else

20

21 Report Fail.

22

Algorithm 8 Triangle Sampling in $1$-pass Ea/Va Model

Now we proceed to prove Theorem B.2.

###### Proof of Theorem B.2.

First we argue about space complexity.

##### Space Complexity:

The space complexity of Algorithm 8 is due to the reservoir sampler RS, which
stores two edges, along with a (possible) triangle. This requires
$\mathcal{O}(1)$ space in a single iteration. Since we run
$\widetilde{{\mathcal{O}}}(m^{2}/T)$ instances of Algorithm 8 in parallel, the
total space complexity is $\widetilde{{\mathcal{O}}}(m^{2}/T)$.

##### Proof of Correctness:

To prove that Algorithm 8 samples a triangle uniformly, let us consider an
arbitrary triangle $\Delta=\\{e_{1},e_{2},e_{3}\\}$ containing edges $e_{1}$,
$e_{2}$ and $e_{3}$ such that $e_{1}$ and $e_{2}$ comes before $e_{3}$ in the
streaming.

Let us consider the case when $\\{e_{1},e_{2}\\}$ is sampled by the reservoir
sample RS. Then observe that the status if reservoir sampler is not changed on
arrival of any edge $e$ in the stream, after the arrival of $e_{1}$ and
$e_{2}$. So, by the description of the algorithm, when $e_{3}$ arrives, the
algorithm detects the triangle $\Delta=\\{e_{1},e_{2},e_{3}\\}$, Moreover,
$\Delta$ will be the output reported by the algorithm.

Hence,

$\mathbb{P}\left(\Delta~{}\mbox{is reported}\right)=\mathbb{P}(\mbox{RS
samples $e_{1}$ and $e_{2}$})=\frac{1}{m^{2}}.$

Since there are $T$ triangles in the graph $G$ and the triangles reported by
the algorithm are disjoint event, using the union bound, we can say that the
probability that Algorithm 8 outputs a sampled triangle is: $T/m^{2}$.

Since we are running $t=\widetilde{{\mathcal{O}}}(m^{2}/T)$ instances of
Algorithm 8 in parallel, the probability that no triangle will be sampled
among all the instances is bounded by $(1-T/m^{2})^{t}\leq
1/\mathsf{poly}(n)$. Thus, we conclude that with probability at least
$1-1/\mathsf{poly}(n)$, a triangle will be sampled.

Under the conditional space that a triangle has been sampled, the probability
that a particular triangle $\Delta$ is sampled is as follows:

$\displaystyle\mathbb{P}(\Delta\mbox{ is sampled})=\frac{\mathbb{P}(\Delta\
\mbox{is reported})}{\mathbb{P}(\mbox{A triangle is
reported})}=\frac{1/m^{2}}{T/m^{2}}=\frac{1}{T}.$

Thus, the triangle $\Delta$ has been sampled uniformly. ∎

##  Appendix C Lower Bound Results for Triangle Sampling

Here we discuss the lower bound results for Triangle Sampling in different
modes, as mentioned in the introduction. The lower bound results on Triangle
Sampling follow from the corresponding lower bound for triangle counting along
with the discussion in 2 of Appendix A.

###  C.1 Lower bound for Triangle Sampling in Al Model

Let us begin by stating the multi-pass triangle counting lower bound in Al
model.

######  Lemma C.1 (Lower bound of Triangle Counting in Multi-pass, Theorem 5.2
of [24]).

For any $m,T\in\mathbb{N}$ such that $T\leq m^{3/2}$, there exist
$m^{\prime}=\Theta(m)$ and $T^{\prime}=\Theta(T)$ such that any adjacency list
streaming algorithm that distinguishes between $m^{\prime}$-edge graphs with
$0$ and $T^{\prime}$ triangles with probability at least $2/3$ in a constant
number of passes requires $\Omega(m/T^{2/3})$ space.

######  Remark 4.

The lower bound stated in the above theorem is conditioned on the conjecture
for the complexity of the _Disjointness_ problem in the _number on forehead_
model. Here, there are $k$ players each holding a vector in $\\{0,1\\}^{n}$
such that each player can see all the vectors except own vector. The objective
of the players is to decide if there exists an index $i\in[n]$ such that the
$i$-th coordinate of all the vectors are $1$. The conjecture states that the
communication complexity of the problem is $\Omega(n)$ where as the best known
lower bound is $\Omega(\sqrt{n})$ [37].

In the multi-pass setting, we have the following lower bound result for
Triangle Sampling in the Al model (assuming that the conjecture states in 4 is
true).

######  Theorem C.2 (Lower bound of 1.1 (i)).

For any $m,T\in\mathbb{N}$ such that $T\leq m^{3/2}$, there exist
$m^{\prime}=\Theta(m)$ and $T^{\prime}=\Theta(T)$ such that any adjacency list
streaming algorithm that samples a triangle uniformly from any graph with
$m^{\prime}$ edges and $T^{\prime}$ triangles with probability at least $2/3$
in a constant number of passes requires $\Omega(m/T^{2/3})$ space.

Now, we state the $1$-pass lower bound of triangle counting in Al model.

######  Lemma C.3 (Lower bound for Triangle Counting in 1-pass, Theorem 5.1 of
[24]).

For any $m,T\in\mathbb{N}$ such that $T\leq m$, there exist
$m^{\prime}=\Theta(m)$ and $T^{\prime}=\Theta(T)$ such that any Al streaming
algorithm that distinguishes between $m^{\prime}$-edge graphs with $0$ and
$T^{\prime}$ triangles in one pass with probability at least $2/3$ requires
$\Omega(m/\sqrt{T})$ space.

In the one-pass setting, we have the following lower bound result for Triangle
Sampling in the Al model.

######  Theorem C.4 (Lower bound of Theorem 1.1 (ii)).

For any $m,T\in\mathbb{N}$ such that $T\leq m$, there exist
$m^{\prime}=\Theta(m)$ and $T^{\prime}=\Theta(T)$ such that any Al streaming
algorithm that samples a triangle uniformly from any graph with $m^{\prime}$
edges and $T^{\prime}$ triangles in one pass with probability at least $2/3$
requires $\Omega(m/\sqrt{T})$ space.

###  C.2 Lower bounds for Triangle Sampling in Ea/Va Model

Similar to the lower bounds for Al model, we will first state the lower bound
of triangle counting in Ea/Va model below.

######  Lemma C.5 (Lower bound for Triangle Counting in Multi-pass, Theorem
4.2 of [5]).

For any $m,T\in\mathbb{N}$ such that $T=\Omega(m)$, there exist
$m^{\prime}=\Theta(m)$ and $T^{\prime}=\Theta(T)$ such that any Ea (Va)
streaming algorithm that distinguishes between $m^{\prime}$-edge graphs with
$0$ and $T^{\prime}$ triangles in multi-pass with probability at least $2/3$
requires $\Omega(m^{3/2}/T)$ space.

In the Ea/Va model model, we have the following lower bound for triangle
sampling in multi-pass.

######  Theorem C.6 (Lower bound of B.1).

For any $m,T\in\mathbb{N}$ such that $T=\Omega(m)$, there exist
$m^{\prime}=\Theta(m)$ and $T^{\prime}=\Theta(T)$ such that any Ea (Va)
streaming algorithm samples a triangle from any graph with $m^{\prime}$ edges
and $T^{\prime}$ triangles in multi-pass with probability at least $2/3$
requires $\Omega(m^{3/2}/T)$ space.

Similarly, let us first state the lower bound of triangle counting in $1$-pass
Ea/Va model.

######  Lemma C.7 (Lower bound for Triangle Counting in 1-pass, Theorem 1 of
[8]).

For any $m,T\in\mathbb{N}$ such that $T=\Omega(m)$, there exist
$m^{\prime}=\Theta(m)$ and $T^{\prime}=\Theta(T)$ such that any Ea (Va)
streaming algorithm that distinguishes between $m^{\prime}$-edge graphs with
$0$ and $T^{\prime}$ triangles in $1$-pass with probability at least $2/3$
requires $\Omega(m^{2}/T)$ space.

So, in the Ea/Va model, we have the following lower bound of triangle sampling
in $1$-pass.

######  Theorem C.8 (Lower bound of B.2).

For any $m,T\in\mathbb{N}$ such that $T=\Omega(m)$, there exist
$m^{\prime}=\Theta(m)$ and $T^{\prime}=\Theta(T)$ such that any Ea (Va)
streaming algorithm that samples a triangle from a graph with $m^{\prime}$
edges and $T^{\prime}$ triangles in $1$-pass with probability at least $2/3$
requires $\Omega(m^{2}/T)$ space.

##  Appendix D Useful concentration bounds

In our work, we use the following three concentration inequalities, see [14].

######  Lemma D.1 (Chernoff-Hoeffding bound).

Let $X_{1},\ldots,X_{n}$ be independent random variables such that
$X_{i}\in[0,1]$. For $X=\sum\limits_{i=1}^{n}X_{i}$ and $\mu=\mathbb{E}[X]$,
the following holds for all $0\leq\delta\leq 1$

$\mathbb{P}\left(\left|X-\mu\right|\geq\delta\mu\right)\leq
2\exp{\left(\frac{-\mu\delta^{2}}{3}\right)}.$

######  Lemma D.2 (Chernoff-Hoeffding bound).

Let $X_{1},\ldots,X_{n}$ be independent random variables such that
$X_{i}\in[0,1]$. For $X=\sum\limits_{i=1}^{n}X_{i}$ and
$\mu_{l}\leq\mathbb{E}[X]\leq\mu_{h}$, the followings hold for any $\delta>0$.

  * (i)

$\mathbb{P}\left(X\geq\mu_{h}+\delta\right)\leq\exp{\left(\frac{-2\delta^{2}}{n}\right)}$.

  * (ii)

$\mathbb{P}\left(X\leq\mu_{l}-\delta\right)\leq\exp{\left(\frac{-2\delta^{2}}{n}\right)}$.

######  Lemma D.3 (Hoeffding’s Inequality).

Let $X_{1},\ldots,X_{n}$ be independent random variables such that $a_{i}\leq
X_{i}\leq b_{i}$ and $X=\sum\limits_{i=1}^{n}X_{i}$. Then, for all $\delta>0$,
we have

$\mathbb{P}\left(\left|X-\mathbb{E}[X]\right|\geq\delta\right)\leq
2\exp\left(\frac{-2\delta^{2}}{\sum\limits_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$