Approximately Counting Triangles in Sublinear Time

arXiv:1504.00954v3 [] 22 Sep 2015

Talya Eden∗

Amit Levi†

Dana Ron‡

C. Seshadhri

§

Abstract
We consider the problem of estimating the number of triangles in a graph. This problem
has been extensively studied in both theory and practice, but all existing algorithms read the
entire graph. In this work we design a sublinear-time algorithm for approximating the number
of triangles in a graph, where the algorithm is given query access to the graph. The allowed
queries are degree queries, vertex-pair queries and neighbor queries.
We show that for any given approximation parameter 0 < ǫ < 1, the algorithm provides
an estimate b
t such that with high constant probability, (1 − ǫ) · t < b
t < (1 + ǫ) · t, where t is
the
number
of
triangles
in
the
graph
G.
The
expected
query
complexity
of the algorithm is
n

o
m3/2
n
+ min m, t
· poly(log n, 1/ǫ), where n is the number of vertices in the graph and
t1/3


3/2
n
· poly(log n, 1/ǫ). We
m is the number of edges, and the expected running time is t1/3
+ mt

n
o
n
m3/2
also prove that Ω t1/3 + min m, t
queries are necessary, thus establishing that the query
complexity of this algorithm is optimal up to polylogarithmic factors in n (and the dependence
on 1/ǫ).

∗

School of Computer Science, Tel Aviv University, talyaa01@gmail.com
School of Electrical Engineering, Tel Aviv University, amitlev3@post.tau.ac.il
‡
School of Electrical Engineering, Tel Aviv University, danaron@tau.ac.il. This research was partially supported
by the Israel Science Foundation grant No. 671/13 and by a grant from the Blavatnik fund.
§
University of California, Santa Cruz, scomandu@ucsc.edu
†

1

Contents
1 Introduction
1.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Overview of the algorithm . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 A simple oracle-based procedure for a 1/3-estimate . . . . .
1.2.2 Assigning weights to triangles so as to improve the estimate
1.2.3 Deciding whether
a vertex is heavy . . . . . . . . . . . . . .
P
1.2.4 Estimating v∈S wt(v) . . . . . . . . . . . . . . . . . . . .
1.3 A high level discussion of the lower bound . . . . . . . . . . . . . .
1.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1 Approximating graph parameters in sublinear time . . . . .
1.4.2 Triangle counting . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

2 Preliminaries
3 The
3.1
3.2
3.3
3.4

6

Algorithm
Heavy and light vertices . . . . . . . . . . . . . . .
A procedure for deciding whether a vertex is heavy
Estimating the number of triangles given m and t .
The final algorithm . . . . . . . . . . . . . . . . . .

4 A Lower Bound
4.1 A lower bound for t = m . . . . . . . . . . .
4.1.1 The lower-bound construction . . . .
4.1.2 Definition of the processes P1 and P2
4.1.3 The auxiliary graph for t = m . . . .
4.1.4 Statistical distance . . . . . . . . . .
4.2 A lower bound for m < t < m3/2 . . . . . .
4.2.1 The lower-bound construction . . . .
4.2.2 The processes P1 and P2 . . . . . . .
4.2.3 The auxiliary graph . . . . . . . . .
4.2.4 Statistical distance . . . . . . . . . .
√
4.3 A lower bound for m ≤ t ≤ 14 m . . . . . .
4.3.1 The lower-bound construction . . . .
4.3.2 The processes P1 and P2 . . . . . . .
4.3.3 The auxiliary graph . . . . . . . . .
4.3.4 Statistical distance . . . . . . . . . .
√
4.4 Lower Bound for t < 14 m. . . . . . . . . .
4.4.1 The construction . . . . . . . . . . .
4.4.2 The processes P1 and P2 . . . . . . .
4.4.3 The auxiliary graph . . . . . . . . .
4.4.4 Statistical distance . . . . . . . . . .
4.5 Wrapping things up . . . . . . . . . . . . .

2
2
3
3
3
3
4
5
5
5
5

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

7
7
9
11
15

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

17
20
20
20
23
24
28
28
28
28
29
30
30
30
31
32
35
35
37
37
38
38

1

Introduction

Counting the number of triangles in a graph is a fundamental algorithmic problem. In the study
of complex networks and massive real-world graphs, triangle counting is a key operation in graph
analysis for bioinformatics, social networks, community analysis, and graph modeling [HL70, Col88,
Por00, EM02, MSOI+ 02, Bur04, BBCG08, FWVDC10, BHLP11, SKP12]. In the theoretical
computer science community, the primary tool for counting the number of triangles is fast matrix multiplication [IR78, AYZ97, BPWZ14]. On the more applied side, there is a plethora of
provable and practical algorithms that employ clever sampling methods for approximate triangle counting [CN85, SW05b, SW05a, Tso08, TKMF09, Avr10, KMPT12, CC11, SV11, TKM11,
AKM13, SPK13, TPT13]. Triangle counting has also been a popular problem in the streaming
setting [BYKS02, JG05, BFL+ 06, AGM12, KMSS12, JSP13, PTTW13, TPT13, ADNK14].
All these algorithms read the entire graph, which may be time consuming when the graph is
very large. In this work, we focus on sublinear algorithms for triangle counting. We assume the
following query access to the graph, which is standard for sublinear algorithms that approximate
graph parameters. The algorithm can make: (1) Degree queries, in which the algorithm can query
the degree dv of any vertex v. (2) Neighbor queries, in which the algorithm can query what vertex
is the ith neighbor of a vertex v, for any i ≤ dv . (3) Vertex-pair queries, in which the algorithm
can query for any pair of vertices v and u whether (u, v) is an edge.
Gonen et al. [GRS11], who studied the problem of approximating the number of stars in a
graph in sublinear time, also considered the problem of approximating the number of triangles in
sublinear time. They proved that there is no sublinear approximation algorithm for the number
of triangles when the algorithm is allowed to perform degree and neighbor queries (but not pair
queries). 1
They asked whether a sublinear algorithm exists when allowed vertex-pair queries in addition
to degree and neighbor queries. We show that this is indeed the case.

1.1

Results

Let G be a graph with n vertices, m edges, and t triangles. We describe an algorithm that, given
an approximation parameter 0 < ǫ < 1 and query access to G, outputs an estimate b
t, such that
with high constant probability (over the randomness of the algorithm), (1 − ǫ) · t ≤ b
t ≤ (1 + ǫ) · t.
The expected query complexity of the algorithm is
(
)!
n
m3/2
+ min m,
· poly(log n, 1/ǫ) ,
t
t1/3


3/2
n
+ mt
and its expected running time is t1/3
· poly(log n, 1/ǫ). We show that this result is almost
optimal by proving that the number of queries performed by any multiplicative-approximation
algorithm for the number of triangles in a graph is
(
)!
m3/2
n
Ω 1/3 + min m,
.
t
t
1

To be precise, they showed that there exist two families of graphs over m = Θ(n) edges, such that all graphs in
one family have Θ(n) triangles, all graphs in the other family have no triangles, but in order to distinguish between
a random graph in the first family and random graph in the second family, it is necessary to perform Ω(n) degree
and neighbor queries.

2

1.2

Overview of the algorithm

For the sake of clarity, we suppress any dependencies on the approximation parameter ǫ and on
log n using the notation O∗ (·).
1.2.1

A simple oracle-based procedure for a 1/3-estimate

First, let us assume access to an P
oracle that, given a vertex v, returns tv , the number of triangles that
v is incident to. Note that t = v tv /3. An unbiased estimate is obtained
by sampling, uniformly
P
at random, a (multi-)set S of s vertices, and outputting tS = 31 · ns · v∈S tv . Yet this estimate can
have extremely large variance (consider the “wheel” graph where there is one vertex with tv = Θ(n)
and all other tv ’s are constant). Inspired by work on estimating the average degree [Fei06, GR08],
we can reduce the variance by simply “cutting off” the contribution of vertices v for which tv is
above a certain threshold. Call such vertices heavy, and denote the remaining light. If the threshold
is set to Θ(t2/3 /ǫ1/3 ), then the number of heavy vertices is O((ǫt)1/3 ). This implies that the total
number of triangles in which all three endpoints are heavy is O(ǫt).
Hence, suppose we define e
tv to be tv if tv ≤ t2/3 /ǫ1/3 and 0 otherwise, and consider e
tS =
1 n P
e
e
t
.
We
can
argue
that
E[
t
]
∈
[(1/3
−
ǫ)t,
t],
since
(roughly
speaking)
every
triangle
·
·
v
S
v∈S
3 s
that contains at least one light vertex is counted at least once. Since e
tv ranges
0 and

 between
n
2/3
1/3
∗
t /ǫ , by applying the multiplicative Chernoff bound, a sample of size s = O t1/3 is sufficient



to ensure that with high constant probability e
tS is in the range 1 − 2ǫ · t, (1 + ǫ) · t .
3

1.2.2

Assigning weights to triangles so as to improve the estimate

To improve the approximation, we assign weights to triangles inversely proportional to the number
of their light endpoints (rather than assigning a uniform weight of 31 as is done when defining
P
e
tS = ns · v∈S 31 · e
tv ). If for each light vertex v we let wt(v) be the sum over the weights of all
triangles that
v participates in and for each heavy vertex v we let wt(v) = e
tv = 0, then the expected
n P
value of s · v∈S wt(v) is in [(1 − O(ǫ)) · t, (1 + O(ǫ)) · t].
To get rid of the fictitious oracle, we must resolve two issues. The first P
issue is efficiently deciding
n
whether a vertex is heavy or light, and the second is approximating s · v∈S wt(v), assuming we
have a procedure for deciding whether a vertex is heavy or light. We next discuss each of these two
issues. For convenience, we will assume that the algorithm already has constant factor estimates
for m and t. This can be removed by approximating m and performing a geometric search on t.
1.2.3

Deciding whether a vertex is heavy

Let v be a fixed vertex with degree dv . Consider an edge e incident to v, and let u be the other
endpoint of this edge. Let te denote the number of triangles that e belongs to. Consider the random
variable Y defined by selecting, uniformly at random, a neighbor w of u, and setting Y = du if (v, w)
is an edge (so that (v, u, w) is a triangle) and Y = 0 otherwise. Since the number of neighbors
of u that form a triangle with v is te , the expected value of Y is dteu · du = te . Now consider
selecting (uniformly at random) several edges incident to v, denoted e1 , . . . , er , and for each
edge
1 Pr
ej selected, defining the corresponding random variable Yj . Then the expected value of r j=1 Yj
P
is d1v · e=(v,u) te = d2v · tv . If we multiply by dv /2, then we get an unbiased estimator for tv , which
in particular can indicate whether v is heavy or light.
However, once again the difficulty is with the variance of this estimator and the implication
on the complexity of the resulting decision procedure. To address these difficulties we modify
3

the procedure described above as follows. First, if dv is above a certain
threshold, then v is also

1/3
considered heavy (where this threshold is of order O m/(ǫt)
, so that the total number of
triangles in which all three endpoints are heavy remains O(ǫt). Second, observe that when trying
to estimate the number of triangles that an edge ej = (v, xj ) participates in, we can either select
a random neighbor w of v and check whether (xj , w) ∈ E, or we can select a random neighbor
w of xj and check whether (v, w) ∈ E. Since it is advantageous for the sake of the complexity
to consider the endpoint that has a smaller degree, we do the following. Each time we select an
edge ej = (v, xj ) incident to v, we let uj be the endpoint of ej that has smaller degree. If duj is
√
√
relatively large (larger than m), then we select k = ⌈duj / m⌉ neighbors of uj and let Yj equal
duj times the fraction among these neighbors that close a triangle with ej . The setting of k implies
√
a bound on the variance of Yj (conditioned on the choice of ej ), which is m times its expected
value, tej . Third, in order to bound the variance due to the random choice of edges ej incident to
v, we do the following. We assign each triangle that v participates in to a unique edge incident to
v and modify the definition of te to be the number of such triangles that are assigned to e. The
√
assignment is such that te is always upper bounded by O( m). Finally, we perform a standard
median selection over O(log n) repetitions of the procedure.
Our analysis shows
 it suffices to set r (the number of random edges incident to v that are
 3/2that
m
so as to ensure the correctness of the procedure (with high probability).
selected) to be O∗ t
In the analysis of the expected query complexity and running time of the procedure we have to
√
take into account the number of iterations k = ⌈duj / m⌉ for each selected (lower degree endpoint)
uj and argue that for every vertex v, the expected number of these iterations is a constant.
1.2.4

Estimating

P

v∈S

wt(v)
n
s

4

·

P

wt(v) is indeed in
 [(1− O(ǫ)) ·
n
∗
t, (1 + O(ǫ)) · t] (which we know occurs with high probability if we select s = O t1/3
vertices
uniformly at random). Consider the set of edges incident to vertices in S, where we view edges as
directed, so that if there is an edge between v and v ′ that both belong to S, then (v, v ′ ) and (v ′ , v)
are considered
P as two different edges. We denote this set of edges by ES , and their number by dS ,
where dS = v∈S dv . Suppose that for each edge e = (v, x) we assign a weight wt(e), which is the
sum of the weights of all triangles that v participates in and are assigned to e (where the weight
of
as defined previously based on the number of light endpoints that it has). Then
P a triangle is P
wt(e)
=
v∈S wt(v).
e∈ES
The next idea is to sample edges in ES uniformly at random, and for each selected edge e = (v, u)
to estimate wt(e). An important observation is that since we can query the degrees of all vertices
in S, we can efficiently select uniform random edges in ES (as opposed to the more difficult task
of selecting random edges from the entire graph). Similarly to what was described in the decision
procedure for heavy vertices, given an edge e ∈ ES we let u be its endpoint that has smaller degree.
√
We then select ⌈ m/du ⌉ random neighbors of u and for each check whether it closes a triangle with
e. For each triangle found that is assigned to e, we check how many heavy endpoints it has (using
the aforementioned procedure for detecting heavy vertices) so as to compute the weight
of the
1 P
triangle. In this manner we can obtain random variables whose expected value is dS v∈S wt(v),
√
and whose variance is not too large (upper bounded
 3/2by
 m times this expected value). We can
now take an average over sufficiently many (O ∗ m t ) such random variables and multiply by
dS · n. By upper bounding the probability that dS is much larger than its expected value we can
prove that the output of the algorithm is as desired. The expected query complexity and running
Suppose we have a (multi-)set S of vertices such that

v∈S

time of the algorithm are shown to be O ∗



n
t1/3

+

m3/2
t

3/2


.

3/2

Finally we note that if t < m1/2 so that m t > m, then we can replace m t with m in the
upper bound on the query complexity since we can store all queried edges so that no edge needs to
be queried more than twice (once from each endpoint).

1.3

A high level discussion of the lower bound



n
queries is fairly
Proving that every multiplicative-approximation algorithm must perform Ω t1/3

n
o
3/2
straightforward, and our main focus is on proving that Ω min m, m t
queries are necessary

as well. In order to prove this claim we define, for every n, every 1 ≤ m ≤ n2 and every

1 ≤ t ≤ min{ n3 , m3/2 }, a graph G1 and a family of graphs G2 for which the following holds:
(1) The graph G1 and all the graphs in G2 have n vertices and m edges. (2) In G1 there are no
triangles, while the number of triangles
in each graph G ∈ G2 is Θ(t). We prove that for values of t

√
m3/2
queries are required in order to distinguish with high constant
such that t ≥ m, at least Ω t
probability between G1 and a random graph in G2 . We then prove that for values of t such that
√
t < m, at least Ω(m) queries are required for this task. We give three different constructions for
G1 and G2 depending on the value of t as a function of m (where two of the constructions are for
√
subcases of the case that t ≥ m). For further discussion of the lower bound, see Section 4.

1.4
1.4.1

Related Work
Approximating graph parameters in sublinear time

We build on previous work on approximating the average degree of a graph and the number of
stars [Fei06, GR08, GRS11]. Feige [Fei06] investigated the problem of estimating the average degree of a graph, denoted d, when given query access
q to thedegrees of the vertices. By performing
n/d/ǫ queries are sufficient in order to oba careful variance analysis, Feige proved that O
tain a ( 21 − ǫ)-approximation of d. He also proved that a better approximation ratio cannot be
achieved in sublinear time using only degree queries. The same problem was considered by Goldreich and
[GR08]. Goldreich and Ron proved that a (1 + ǫ)-approximation can be achieved
q Ron
√ 
n/ d · poly(log n, 1/ǫ) queries, if neighbor queries are also allowed.
with O

Building on these ideas, Gonen et al. [GRS11] considered the problem of approximating the
number of s-stars in a graph. Their algorithm only used neighbor and degree queries. A major
difference between stars and triangles is that the former are non-induced subgraphs, while the
latter are. Additional work on sublinear algorithms for estimating other graph parameters include
those for approximating the size of the minimum weight spanning tree [CRT05, CS09, CEF+ 05],
maximum matching [NO08, YYI09] and of the minimum vertex cover [PR07, NO08, MR09, YYI09,
HKNO09, ORRR12].
1.4.2

Triangle counting

Triangle counting has a rich history. A classic result of Itai and Rodeh showed that triangles
can be enumerated in O(m3/2 ) time, and a more elegant algorithm was given by Chiba and
Nishizeki [CN85]. The connections to matrix multiplication have been exploited for faster theoretical algorithms [IR78, AYZ97, BPWZ14]. In practice, there is a diverse body on work on

5

counting triangles using different techniques, for different models. There are serial algorithms based
on eigenvalue methods [Tso08, Avr10], graph sparsification [TDM+ 09, KMPT12, TKM11, PT12],
and sampling paths [SW05b, SPK13]. Triangle counters have been given for MapReduce [Coh09,
SV11, KPP+ 13]; external memory models [CC11]; distributed settings [AKM13]; semi-streaming
models [BBCG08, KMPT12]; one-pass streaming [BYKS02, JG05, BFL+ 06, AGM12, KMSS12,
JSP13, PTTW13, TPT13, ADNK14]. It is worth noting that across the board, all these algorithms
required reading the entire graph.
Most relevant to our work are various sampling algorithms, that set up a random variable whose
expectation is directly related to the triangle count [SW05b, KMPT12, JG05, BFL+ 06, SPK13,
JSP13, PTTW13, TPT13, ADNK14]. Typically, this involves sampling some set of vertices or edges
to get a set of three vertices. The algorithm checks whether the sampled set induces a triangle, and
uses the probability of success to estimate the triangle count. We follow the basic same philosophy.
But it is significantly more challenging to set up the “right” random experiment, since we cannot
read the entire graph.

2

Preliminaries

Let G = (V, E) be a simple graph with |V | = n vertices and |E| = m edges. For a vertex v ∈ V ,
we denote by dv the degree of the vertex, by Γv the set of v’s neighbors, and by Ev the set of edges
incident to v. We denote by Tv the set of triangles incident to the vertex v, and let tv = |Tv |.
Similarly, the set of triangles in the graph G is denoted by T , and the number of triangles in the
graph in denote by t. We use c, c1 , . . . to denote sufficiently large constants.
We consider algorithms that can sample uniformly in V and perform three types of queries:
1. Degree queries, in which the algorithm may query for the degree dv of any vertex v of its
choice.
2. Neighbor queries, in which the algorithm may query for the ith neighbor of any vertex v of
its choice. If i > dv , then a special symbol (e.g. †) is returned. No assumption is made on
the order of the neighbors of any vertex.
3. Pair queries, in which the algorithm may ask if there is an edge (u, v) ∈ E between any pair
of vertices u and v.
We sometimes use set notations for operations on multisets. We use the notation O∗ (·) to suppress
dependencies on the approximation parameter ǫ or on log n.
We use the following variant of the multiplicative Chernoff bound. Let χ1 , . . . , χr be r independent random variables, such that χi ∈ [0, B] for some B > 0 and E[χi ] = b for every 1 ≤ i ≤ r. For
every γ ∈ (0, 1] the following holds:
#
" r
 2

γ ·b·r
1X
χi > (1 + γ)b < exp −
,
(1)
Pr
r
3B
i=1

and

#
 2

r
γ ·b·r
1X
χi < (1 − γ)b < exp −
.
Pr
r
2B
"

(2)

i=1

We will also make an extensive use of Chebyshev’s inequality: For a random variable X and for
γ > 0,
Var[X]
.
Pr [|X − E[X]| ≥ γ] ≤
γ2
6

We fix a total order on vertices denoted by ≺ as follows: u ≺ v if du < dv or du = dv and u < v
(in terms of id number). Given u and v, two degree queries suffice to decide their ordering.
√
Claim 1. Fix any vertex v. The number of neighbors w of v such that v ≺ w is at most 2m.
Proof. P
Let S = {w|w ∈ Γv , v ≺ w}.
√ Naturally, dv ≥ |S|. By definition of ≺, ∀w ∈ S, dw ≥ dv ≥ |S|.
Thus, w∈S dw ≥ |S|2 and |S| ≤ 2m.

3

The Algorithm

We start by introducing the notions of heavy and light vertices and how they can be utilized
in the context of estimating the number of triangles. We then give a procedure for deciding
(approximately) whether a vertex is heavy or light. Using this procedure we give an algorithm for
estimating the number of triangles based on the following assumption (which is later removed).
Assumption 1. Our initial algorithm takes as input estimates t and m on the number of edges
and triangles in the graph respectively, such that
1. t/4 ≤ t ≤ t.
2. m/6 ≤ m.
Assumption 1 can be easily removed by performing a geometric search on t and using the
algorithm from [Fei06] to approximate m, as explained precisely in the proof of Theorem 13.
For every vertex v, we view the set of edges Ev as directed edges originating from v. We then
associate each triangle (v, x, w) ∈ Tv with a unique edge e ∈ Ev , as defined next.

−−−→
Definition 1. We say that a triangle (v, x, w) ∈ Tv is associated with the directed edge (v, x) if
−−−→
−−−→
→
→
x ≺ w, and to (v, w) otherwise. For a directed edge −
e = (v, x) we let T−
e denote the set of triangles
that it is associated with, that is, the set of triangles (v, x, w) such that x ≺ w.
Since it will always be clear from the context from which vertex an edge we consider originates,
for the sake of succinctness, we drop the
Pdirected notation and use the notation Te . We let te = |Te |,
te .
and for a fixed vertex v, we get tv =
e∈Ev

In all the follows we assume that ǫ < 1/2, and otherwise we run the algorithm with ǫ = 1/2.

3.1

Heavy and light vertices

Definition 2. We say that a vertex v is heavy if dv >
dv ≤

2m
(ǫt)1/3

and tv ≤

2/3

t
,
2ǫ1/3

2m
(ǫt)1/3

or if tv >

2/3

2t
ǫ1/3

. If v is such that

then we say that v is light.

We shall say that a partition (H, L) of V is appropriate (with respect to m and t) if every heavy
vertex belongs to H and every light vertex belongs to L.
Note that for an appropriate partition (H, L) both H and L may contain vertices that are
neither heavy nor light (but no light vertex belongs to H and no heavy vertex belongs to L).
For a fixed partition (H, L) we associate with each triangle ∆ a weight depending on the number
of its endpoints that belong to L.

7

Definition 3. For a triangle ∆ we define its weight wtL (∆) to be
(
0
if no endpoints of ∆ belong to L
wtL (∆) =
1/ℓ if ∆ has ℓ > 0 endpoints that belong to L .
Whenever it is clear for the context, we drop the subscript L and use the notation wt(·) instead
of wtL (·).
Claim 2. If (H, L) is appropriate and Assumption 1 holds, then the number of triangles with weight
0 is at most cH · ǫt for some constant cH .

Proof. By Assumption 1, the number of vertices v such that dv is greater than (2m/(ǫt)1/3 , is at
2/3
most 2m/(2m/(ǫt)1/3 ) ≤ 6(ǫt)1/3 , and the number of vertices v such that tv > 2t /ǫ1/3 is at most

1/3
2/3
< 2000ǫt triangles with all three
3t/(2t /ǫ1/3 ) ≤ 6(ǫt)1/3 . Therefore, there are at most 12(ǫt)
3
endpoints in H. Setting cH = 2000 completes the proof.
P
wt(∆). For a vertex v ∈ L we
Definition 4. For any set T of triangles we define wt(T ) =
∆∈T
P
wt(∆), and wt(v) = 0 for v ∈ H.
define wt(v) =
∆∈Tv

P
wt(v) ≤ t. If (H, L) is appropriate and Assumption 1
Lemma 3. For any partition (H, L),
v∈L
P
wt(v) ∈ [t(1 − cH · ǫ), t].
holds, then
v∈L

Proof. Let χ(v, ∆) be an indicator variable such that χ(v, ∆) = 1 if ∆ contains the vertex v, and
χ(v, ∆) = 0 otherwise. Consider a triangle ∆ that contains ℓ > 0 light vertices. Then
X
χ(v, ∆) = ℓ = 1/wt(∆) .
v∈L

If ℓ = wt(∆) = 0, then the above expression equals 0. By interchanging summations,
X
X
X
X X
wt(∆) =
wt(∆)
χ(v, ∆) = t − |{∆ | wt(∆) = 0}|.
wt(v) =
v∈L

∆∈T

v∈L ∆∈Tv

v∈L

Clearly for any partition (H, L) the above expression is at most t. On the other hand, If (H, L) is
appropriate and Assumption 1 holds, then by Claim 2 we have that |{∆ | wt(∆) = 0}| ≤ cH · ǫt,
and the lemma follows.
1/3

Theorem 4. Let s = (c log(n/ǫ)/ǫ3 )n/t
where c is a constant, and let S be a sample of s vertices
v1 , v2 , . . . , vs that are selected uniformly, independently at random. Then
" s
#
1X
t
E
wt(vi ) ≤ .
s
n
i=1

Furthermore, if (H, L) is appropriate and Assumption 1 holds, then
" s
#
1X
E
wt(vi ) ∈ [t(1 − cH · ǫ)/n, t/n]
s
i=1

and for a sufficiently large constant c,
#
" s
1X
wt(vi ) < t(1 − 2cH · ǫ)/n < ǫ2 /n .
Pr
s
i=1

8

s
P
Proof. Let Y denote the random variable Y = 1s
wt(vi ). By the first part of Lemma 3,
i=1
 s

P
E 1s
wt(vi ) ≤ t/n. Now assume that (H, L) is appropriate and Assumption 1 holds. The
i=1

claim regarding the expected value of Y follows from the second part of Lemma 3, so it remains to
prove the claim regarding the deviation from the expected value. Note that wt(v) ≤ tv for every

vertex v, which for v ∈ L is at most
Assumption 1,


2/3

2t
ǫ1/3

. By the multiplicative Chernoff bound and by Item 1 in

ǫ2 E[Y ]s
Pr [Y < (1 − ǫ)E[Y ]] < exp − 2/3 1/3
4t /ǫ



< exp −

ǫ2 · c log(n/ǫ)(n/ǫt
4t

2/3

1/3

/ǫ1/3

) · t/(2n)

!

<

ǫ2
,
n

where the last inequality holds for a sufficiently large constant c.

3.2

A procedure for deciding whether a vertex is heavy

In this subsection we provide a procedure for deciding (approximately) whether a given vertex v is
heavy or light. Recall that a high-level description of the procedure appears in Subsection 1.2.3 of
the introduction.
Heavy(v)
1. If dv > 2m/(ǫt)1/3 , output heavy.
2. For i = 1, 2, . . . , 10 log n:
(a) For j = 1, 2, . . . , s = 20m3/2 /ǫ2 t:
i. Select an edge e ∈ Ev uniformly, independently and at random, and let u
be the smaller endpoint according
to the order ≺.
√
ii. For k = 1, 2, . . . , r = ⌈du / m⌉:
A. Pick a neighbor w of u uniformly at random. Let x denote the endpoint
of e that is not v.
B. If e andPw form a triangle and x ≺ w, set Zk = du , else Zk = 0.
iii. Set Yj = 1r
Zk .
k
P
Yj .
(b) Set Xi = dsv
j

3. If the median of the Xi variables is greater than t
light.

2/3

/ǫ1/3 , output heavy, else output

We have three nested loops, with loop variables i, j, k respectively. We refer to these as “iteration
i”, “iteration j”, and “iteration k”.
Lemma 5. For any iteration i, Pr[|Xi − tv | > ǫ · max(tv , tdv /m)] < 1/4.
Proof. Recall that we associate each
P triangle (v, x, w) ∈ Tv with (v, x) if x ≺ w and with (v, w)
otherwise, so that we have tv = e∈Ev te . For an edge e = (v, x), te is upper bounded by the
√
number of neighbors w of x such that x ≺ w. By Claim 1, te ≤ 2m.
Fix an iteration j and let ej denote the edge chosen in the j th iteration and uj denote its smaller
degree endpoint. We use Ej to denote the event of ej being chosen. Conditioned on the event Ej ,
the probability that Zk is non-zero is is tej /duj . Hence,
E[Zk | Ej ] =

te j
· duj = tej ,
duj
9

and
Var[Zk | Ej ] ≤ E[Zk2 | Ej ] ≤ duj · E[Zk | Ej ].
By linearity of expectation,
#
r
r
1X
1X
Zk | Ej =
E [Zk | Ej ] = tej .
E[Yj | Ej ] = E
r
r
"

k=1

(3)

k=1

By the independence of the Zk variables,
" r
#
r
r
1X
1 X
1 X
Var[Yj | Ej ] = Var
Var [Zk | Ej ] ≤ 2
duj · E [Zk | Ej ]
Zk | Ej = 2
r
r
r
k=1

k=1

k=1

√
du
= 2j · r · tej ≤ m · tej .
r

(4)

The conditioning can be removed to yield
E[Yj ] =

X 1
tv
1 X
te = .
· E[Yj | Ej ] =
·
dv
dv
dv

e∈Ev

By the law of total variance, the law of total expectation, the bounds tej ≤
by Equations (3) and (4):

Let Y =

1
s

P

(5)

e∈Ev

√
2m and m ≤ 6m, and

Var[Yj ] = Eej [Var [Yj | Ej ]] + Varej [E [Yj | Ej ]]
h√
i
≤ Eej
m · E [Yj | Ej ] + Varej [tej ]
√
= m · E [Yj ] + Eej [t2ej ]
√
1 X 2
= m · E [Yj ] +
te j
·
dv
ej ∈Ev
√
√
√
≤ m · E [Yj ] + 2m · E[Yj ] < 5 mE[Yj ] .

(6)

Yj . By Equation (5), E[Y ] = tv /dv . By Equation (6),

j



√
s
s
s
X
X
X
√
5 m
1
1
1
Var[Y ] = Var 
Var[Yj ] < 2
5 m · E [Yj ] =
Yj  = 2
·E
Yj 
s
s
s
s
s
j=1
j=1
j=1
j=1
√
√
2
5 m · (tv /dv )
5 m  
ǫ tv t
=
=
E Y =
·
·
.
(7)
3/2
2
s
4 dv m
20 · m /ǫ t


s
1X



By Chebyshev’s inequality and Equation (7),



tv t
Var[Y ]
1
tv
Pr Y −
> ǫ · max
,
≤ 2
< .
2
dv
dv m
4
ǫ max(tv /dv , t/m)
Since Xi = dv · Y , we have that Pr[|Xi − tv | > ǫ · max(tv , tdv /m)] < 1/4.

Lemma 6. For every vertex v, if v is heavy, then a call to Heavy(v) returns heavy with probability
at least 1−1/n2 . If v is light, then a call to Heavy(v) returns light with probability at least 1−1/n2 .
10

Proof. First consider a heavy vertex v. Clearly, if dv > 2m/(ǫt)1/3 , then v is declared heavy.
2/3
2/3
Therefore, assume that tv > 2t /ǫ1/3 and dv ≤ 2m/(ǫt)1/3 , so that tdv /m ≤ 2t /ǫ1/3 , and hence
max(tdv /m, tv ) = tv . By Lemma 5, and since ǫ <≤ 1/2, for any iteration i, Pr [|Xi − tv | > ǫtv ] <
2/3
1/4. Therefore, Pr[Xi < t /ǫ1/3 ] < 1/4, and by Chernoff, the probability that the median of the
2/3
Xi variables (where i = 1, . . . , 10 log n) will be greater than t /ǫ1/3 is at least 1 − 1/n2 . Hence
Heavy(v) outputs heavy with probability at least 1 − 1/n2 .
2/3
Now consider a light vertex v. Since dv ≤ 2m/(ǫt)1/3 and tv ≤ t /2ǫ1/3 , it holds that tdv /m ≤
2/3
2/3
2t /ǫ1/3 , implying that max(tdv /m, tv ) = tv ≤ 2t /ǫ1/3 . Therefore, by Lemma 5, Pr[|Xi − tv | >
2/3
2/3
ǫ(2t /ǫ1/3 )] < 1/4, and the probability that the median will be less than t /ǫ1/3 is at least
1 − 1/n2 . Hence v is declared light with probability at least 1 − 1/n2 .
The following is a corollary of Lemma 6.
Corollary 7. Consider running Heavy for all the vertices in the graph. Let H denote the set of
vertices that are declared heavy and let L denote the set of vertices that are declared light. Then,
with probability at least 1 − 1/n, the partition (H, L) is appropriate (as defined in Definition 2).
We now turn to analyze the running time of Heavy. The proof will be similar to the complexity
analysis of the exact triangle counter of Chiba and Nishizeki [CN85].
Lemma 8. If Item 2 in Assumption 1 holds, then for every vertex v the expected running time of
Heavy(v) is O ∗ (m3/2 /t).
Proof. We first argue that the expected time to generate a single sample of Yj is O(1). Our query
√
model allows for selecting an edge in Ev uniformly at random by√a single query. If dv ≤ m,
then the degree of the smaller endpoint for √
any e ∈ Ev is at most m. Hence a sample is clearly
generated in O(1) time.
√ Suppose that dv > m. If an edge e = (v, u) is sampled, then the runtime
is O(1 + min(dv , du )/ m). Hence, the expected runtime to generate Yj is, up to constant factors,
at most:


X
X
1
2m
1
min {dv , du }
1 X
√
du ≤ 1 + √
du ≤ 1 + √
≤ 5,
≤1+ √
1+
dv
m
m
·
d
m
·
d
m
·
d
v
v
v
u∈Γ
u∈Γ
u∈V
v

v

where the last inequality follows from Item 2 in Assumption 1
By the above, each iteration of the ‘for’ loop in Step 2a takes O(1) time in expectation. Therefore, together, all iterations of Step 2a take O(m3/2 /(ǫt)) time in expectation, and since it is repeated
O(log n) times, the expected running time of the procedure is (m3/2 /t) · poly(log n, 1/ǫ).

3.3

Estimating the number of triangles given m and t

We are now ready to present an algorithm Estimate-with-advice that takes m, t as input (“advice”), and outputs an estimate of t. Later, we employ the the average degree approximation
algorithm of Feige [Fei06] and a geometric search to get the bonafide algorithm that estimates t
without any initial estimates m and t. Recall that a high-level description of the procedure appears
in Subsection 1.2.4 of the introduction. In what follows we rely on the following assumption.
Assumption 2. We will assume that the random coins used by Heavy are fixed in advance, and
that the partition (H, L) as defined in Corollary 7 is indeed appropriate.
By Corollary 7 this assumption only adds 1/n to the error probability in all subsequent probability bounds. Recall that we use c, c1 , . . . to denote sufficiently large constants.
Recall that cH is the constant defined in Claim 2.
11

Estimate-with-advice(m, t, ǫ)
1/3

1. Sample s1 = c1 ǫ−3 log(n/ǫ)(n/t ) vertices, uniformly, independently and at random. Denote the chosen multiset S.
2. Set up a data structure to enable sampling vertices in S proportional to their degree.
3. For i = 1, 2, . . . , s2 = c2 ǫ−4 (log2 n)(m3/2 /t):
(a) Sample v ∈ S proportional to dv and sample e ∈ Ev uniformly at random. Let
u be the smaller endpoint according to the order ≺. Let x be the endpoint of
e that is√not v.
√
(b) If du √
≤ m, set r = 1√with probability du / m and set r = 0 otherwise. If
du > m, set r = ⌈du / m⌉.
(c) Repeat for j = 1, 2, . . . , r:
i. Pick a neighbor w of u uniformly at random.
ii. If e and w do not form a triangle, set Zj = 0.
iii. If e and w form a triangle and w ≺ x, set Zj = 0.
iv. If e and w form a triangle ∆ and x ≺ w: call Heavy for all vertices in ∆,
and let (
0
if Heavy(v) returned heavy
√
.
Zj =
max(du , m) · wt(∆) otherwise
r
P
(d) Set Yi = 1r
Zj . (If r = 0, set Yi = 0.)
j=1

 s

2
P
P
n
dv ·
Yi .
4. Output X = s1 s2 ·
v∈S

i=1

Theorem 9. For X as defined in Step 4 of Estimate-with-advice, E[X] ≤ t. Moreover, if (H, L)
is appropriate and Assumption 1 holds, then E[X] ∈ [t(1 − cH · ǫ), t] and Pr[X < t(1 − 3cH · ǫ)] <
3ǫ/ log n.
There are three “levels” of randomness. First is the choice of S, second is the choice of e
(Step 3a), and finally the Zj ’s. When analyzing the randomness in any level, we condition on the
previous levels. Before proving the theorem, we present the following definition and claim.
P
wt(v)/s1 ≥ t(1 −
Definition 5. Let S be a multiset of s1 vertices. We say that S is good if
v∈S
P
dv ≤ s1 (2m/n)(log n/ǫ).
2cH · ǫ)/n. We say that S is great if, in addition to being good, dS =
v∈S

P
P
wt(v)
dv . For every i, E[Yi | S] = d−1
Claim 10. Fix the choice of the set S, and let dS =
S
v∈S
v∈S
√
and Var[Yi | S] < 5 m · E[Yi | S].

Proof. This is similar to the argument in Lemma 5. Let vi be the chosen vertex in the ith iteration of
the algorithm, and let ei be the chosen edge. We refer to this event by Ei , and condition over the set
S being chosen and the event Ei . Denote by ui the lower degree endpoint of ei . If Heavy(vi )=heavy,
then E[Y√
i | S, Ei ] = 0 and Var[Yi | S, Ei ] = 0. If Heavy(vi )=light, then there are two possibilities.
If dui ≤ m then,
du X 1 √
· m · wt(∆) = wt(Tei ) .
E[Yi | S, Ei ] = √ i
m ∆∈T dui
ei

12

Since the maximum value of Yi in this case is at most

√

m,
√
(8)
Var[Yi | S, Ei ] ≤ E[Yi2 | S, Ei ] ≤ m · E[Yi | S, Ei ] .
√
Now consider the case that dui > m. In order to bound the variance of the Yi variables we first
analyze the expectation and variance of the Zj variables. Note that Zj is non-zero when a triangle
∆ ∈ Tei is found. It holds that
E[Zj | S, Ei ] =

X

∆∈Tei

1
· dui · wt(∆) = wt(Tei ),
dui

and
Var[Zj | S, Ei ] ≤ dui · E[Zj | S, Ei ].

(9)

By linearity of expectation,
E[Yi | S, Ei ] = wt(Tei ).
By independence of the (Zj | S, Ei ) variables, linearity of expectation and Equation (9),


r
r
r
X
1 X
1 X
1


Var [Zj | S, Ei ] ≤ 2
dui · E [Zj | S, Ei ]
Zj | S, Ei = 2
Var[Yi | S, Ei ] = Var
r
r
r
j=1
j=1
j=1


r
X
√
du
1
= i · E
Zj | S, Ei  ≤ m · E[Yi | S, Ei ].
(10)
r
r
j=1

We remove the conditioning on Ei :
E[Yi | S] =

X
X X
X dv 1 X
−1
wt(v) .
wt(T
)
=
d
wt(Te ) = d−1
·
e
S
S
dS dv

v∈S∩L

v∈S

v∈S∩L e∈Ev

e∈Ev

√
Recall that by Claim 1, wt(e) ≤ 2m. Therefore, by the law of total variance, the law of total
expectation, the bound m ≤ 6m, and Equations (8) and (10),
Var[Yi | S] = Eei [Var [Yi | S, Ei ]] + Varei [E [Yi | S, Ei ]]
i
h√
m · E [Yi | S, Ei ] + Eei [wt(Tei )2 ]
≤ Eei
√
√
√
m · E[Yi | S] + 2mEei [wt(Tei )] < 5 m · E[Yi | S] .
This completes the proof of Claim 10.
Proof of Theorem 9: For a fixed set S, let XS denote the sum XS =

n
s1 s2



P

v∈S

 s

2
P
dv ·
Yi
i=1

(as defined in Step 4 of Estimate-with-advice), given that the set S in chosen in Step 1. By the
definition of XS and by Claim 10,
E[XS ] =

ndS
n X
E[Yi | S] =
wt(v).
s1
s1
v∈S

By Theorem 4, ES



1
s1

P

v∈S


wt(v) ∈ [t(1 − cH · ǫ)/n, t/n], implying that
E[XS ] ∈ [t(1 − cH · ǫ), t].
13

(11)

By Theorem 4, Definition 5 and Assumption 2, S
expected value, over S, of dS is Es [dS ] = s1 · 2m
n .

2m
PrS dS > s1 ·
n

is good with probability at least 1 − ǫ2 /n. The
By Markov’s inequality,

log n
ǫ
·
.
<
ǫ
log n

By taking a union bound, the probability that S is great is at least 1 − 2ǫ/ log n. For a fixed choice
s2
P
Yi . By the independence of the Yi variables and by Claim 10,
of S, let YS = s12
i=1

√
s2
s2
√
1 X
5 m
1 X
Var [Yi | S] < 2
5 m · E[Yi | S]=
Var [YS ] = 2
· E [YS ] .
s2
s2 i=1
s2 i=1

(12)

By Chebyshev’s inequality, the setting of s2 and Equation (12), we get that
√


5 m · E[YS ]
Var[YS ]
≤ 2
Pr |YS − E[YS ]| > ǫE[YS ] < 2
ǫ · E[YS ]2
ǫ (c2 ǫ−4 log2 n)(m3/2 /t) · E[YS ]2
ǫ2
.
=
c2 (log2 n)(m/t) · E[YS ]
P
wt(v), which for a great S is at least
By Claim 10, E[YS ] = d−1
S
v∈S

t(1 − 2cH · ǫ)/n)/s1
t
ǫ
≥
·
.
s1 (2m/n)(ǫ/ log n)
4m log n

Therefore, by Assumption 1, for a sufficiently large constant c2 ,
ǫ
.
log n

Pr [|YS − E[YS ]| > ǫE[YS ]] ≤

By the definition of XS in Step 4 of the algorithm, XS is just a scaling of YS . Therefore,
Pr [|XS − E[XS ]| > ǫE[XS ]] ≤
By Equation (11), E[XS ] =
great S,

n
s1

P

v∈S

ǫ
.
log n

wt(v), which for a great S is at least t(1 − 2cH · ǫ). Hence, for a

Pr [XS < (1 − 3cH · ǫ) · t] ≤

ǫ
.
log n

The probability of S not being great is at most 2ǫ/ log n. We apply the union bound to remove the
conditioning, so we get
3ǫ
,
Pr [X < (1 − 3cH · ǫ) · t] ≤
log n


which completes the proof.

Theorem 11. If Item 2 in Assumption 1 holds then the expected running time of Estimate-with-advice
1/3
is O∗ (n/t + m3/2 /t).

14

1/3

Proof. The sampling of S is done in O∗ (n/t ) time. Generating the Zj variables, without the
calls to Heavy, takes time O∗ (m3/2 /t) in expectation, by an argument identical to that in the proof
of Lemma 8. Therefore, it remains to bound the running time resulting from calls to Heavy.
Let us compute the expected number of triangles found during the run of the algorithm. In each
iteration
√ choosing an edge e, the expected number of triangles found is at most
√ i, conditioned on
2(du / m)(te /du ) = 2te / m. Averaging
over the edges, the expected number of triangles found in
√
a single iteration is at most 6t/(m · m), which by Item 2 in Assumption 1 is O(t/m3/2 ). There are
O(m3/2 /t) · poly(log n, 1/ǫ) iterations, leading to a total of O∗ (1) expected triangles. Thus, there
are O ∗ (1) expected calls to Heavy, each taking O ∗ (m3/2 /t) time by Lemma 8. Together with the
1/3
above, we get an expected running time of O(n/t + m3/2 /t) · poly(log n, 1/ǫ).

3.4

The final algorithm

We are now ready to present an algorithm that requires no prior knowledge regarding m and t.
Estimate(ǫ)
1. Let ǫ′ = ǫ/3cH , where cH is the constant defined in Claim 2.
2. Invoke Feige’s algorithm [Fei06] for approximating the average degree of a graph
10 log n times. Let d be the median value of all invocations.
3. Let m = nd/2.
4. Let e
t = n3 .
5. While e
t≥1
t:
(a) For t = n3 , n3 /2, n3 /4, . . . , e
i. For i = 1, . . . , cǫ−1 log log n:
A. Let Xi =Estimate-with-advice(ǫ′, m, t).
ii. Let X = mini {Xi }.
iii. If X ≥ t return X.
(b) Let e
t=e
t/2.

Before analyzing the correctness and running time of the algorithm, we present the following
simple proposition, whose proof we give for the sake of completeness.
Proposition 12. For every graph G, t ≤ 43 m3/2 .
Proof.

1X1
1
t=
tv ≤
3
2
6
v∈V

X

√
v: dv > m

tv +

X

√
v: dv ≤ m




√
√
1
2d2v  ≤ 2 m · 2m + 2 m
6

X

√
v: dv ≤ m



4
dv  ≤ m3/2 .
3

Theorem 13. Algorithm Estimate(ǫ) returns a value X, such that (1 − ǫ)t ≤ X ≤
(1 + ǫ)t, with probability
at  least 5/6. The expected query complexity of the algorithm is

O∗ n/t1/3 + max m, m3/2 /t
and the expected running time of the algorithm is O ∗ (n/t1/3 +
m3/2 /t).
Proof. We first prove that the value of X is as stated in the theorem. Let davg denote the average
degree of vertices in G. The algorithm from [Fei06] returns a value d such that, with probability
at least 2/3, d ∈ [davg /(2 + γ), davg ] for a constant γ. Since we take the median value of 10 log n
15

invocations, it follows from Chernoff’s inequality that m is as stated in Item 2 of Assumption 1
with probability at least 1 − 1/poly(n). Assume that this is indeed the case.
Before analyzing the algorithm Estimate as described above, first consider executing Step 5a
with e
t = 1. That is, rather than running both an outer loop over decreasing values of e
t and an
inner loop over decreasing values of t, we only run a single loop over decreasing value of t, starting
with t = n3 . By the first part of Theorem 9 and by Markov’s inequality, for each value of t and for
each i, Pr[Xi ≤ (1 + ǫ)t] > ǫ/2, where Xi as defined in Step 5(a)iA. Therefore, for each value of t,
the minimum estimate X (as defined in Step 5(a)iii) is at most (1 + ǫ)t, with probability at least
1 − 1/ log 3 n. It follows that for each t such that t > 2t, we have that X < t with probability at
least 1 − 1/ log 3 n, and the algorithm will continue with t = t/2. Once we reach a value of t for
which t/4 ≤ t ≤ t/2, Item 1 in Assumption 1, regarding t, holds. By the second part of Theorem 9,
Xi ∈ [(1 − ǫ)t, (1 + ǫ)t] for every i with probability at least 1 − c/ log n. Hence, we have that
t≤

1
t ≤ (1 − ǫ)t ≤ X ≤ (1 + ǫ)t,
2

with probability at least 1 − c/ log n. Therefore, we halt and return correct X.
If however we do reach a value t such that t ≤ t/4, since Assumption 1 does not hold, we cannot
lower bound X, implying that we can no longer bound the probability that X < t. Therefore we
might continue running with decreasing values of t, causing the running time to exceed the desired
bound of O∗ (n/t1/3 + m3/2 /t). In order to avoid this scenario, we run both an outer loop over e
t and
3
e
e
an inner loop over t. Specifically, starting with t = n , whenever we halve t, we run over all values
of t = n3 , n3 /2, . . ., until we reach e
t. This implies that for every value of e
t > 2t the probability of
returning an incorrect estimate, that is, outside the range of (1 − ǫ)t ≤ X ≤ (1 + ǫ)t, is at most
1 − 1/ log 2 n. On the other hand, for values of e
t such that e
t ≤ t/2 the probability of returning a
correct estimate (within (1 − ǫ)t ≤ X ≤ (1 + ǫ)t) is at least 1 − c/ log n. A union bound over all
failure probabilities gives a success probability of at least 5/6.
We now turn to analyze the query complexity and running time of the algorithm. By [Fei06],
√
the expected running time of the average degree approximation algorithm is O ∗ (n/ m). By
Theorem 11, conditioned on m satisfying Item 2 in Assumption 1, the expected running time
1/3
of Estimate-with-advice(ǫ, m, t) is O∗ (n/t
+ m3/2 /t). It follows from Proposition 12 that
√
n/ m = O(n/t1/3 ), implying that the running time is determined by the value of m and by the
smallest value of t that Estimate-with-advice(ǫ, m, t) is invoked with.
Recall that whenever we halve the value of t̃, we run with all values t = n3 , n3 /2, . . .. This,
together with the fact that when running with t/4 ≤ t ≤ t/2 we halt with probability at least
1−c/ log n, implies that the probability of reaching a value t̃ = t/2k is at most (c/ log n)k . Therefore,
the expected running time, conditioned on m satisfying Item 2 in Assumption 1, is bounded by
! log n
!
!
X
m3/2
m3/2
m3/2
n
n
n
2
∗
∗
k
k
∗
log n · O
+
+
+
+
=O
.
(c/ log n) · 2 · O
t
t
t
t1/3
t1/3
t1/3
k=1

Now consider the value of m computed in Step 3 of Estimate(ǫ). As stated previously, with
probability at least 1 − 1/poly(n) (e.g., 1 − 1/n4 ), the estimate m is within a constant factor from
m. Therefore the expected running time of the algorithm (without the conditioning on the value
of m) is bounded by
!
!


3/2
3/2
m
m
1
n
n
1
+ 4 · O(n3 ) = O ∗ 1/3 +
.
1 − 4 · O ∗ 1/3 +
n
t
n
t
t
t
16

Observe that we can always assume that the algorithm does not perform queries it can answer by
itself. That is, we can allow the algorithm to save all the information it obtained from past queries,
and assume it does not query for information it can deduce from its past queries. Further observe
that any pair query is preceded by a neighbor query. Therefore, if at any point the algorithm
performs more than 2m queries, it can abort. It follows that the expected query complexity is
O∗ (n/t1/3 + min{m, m3/2 /t}).

4

A Lower Bound

In this section we present a lower bound on the number of queries necessary for estimating the
number of triangles in a graph. Since we sometimes refer to the number of triangles in different
graphs, we use the notation t(G) for the number of triangles in a graph G. Our lower bound matches
our upper bound in terms of the dependence on n, m and t(G), up to polylogarithmic factors in
n and the dependence in 1/ǫ. In what follows, when we refer to approximation algorithms for the
number of triangles in a graph, we mean multiplicative-approximation algorithms that output with
high constant probability an estimation b
t such that t(G)/C ≤ b
t ≤ C · t(G) for some predetermined
approximation factor C.
We consider multiplicative-approximation algorithms that are allowed the following three types
of queries: Degree queries, pair queries and random new-neighbor queries. Degree queries and pair
queries are as defined in Section 2. A random new-neighbor query qi is a single vertex u and the
corresponding answer is a vertex v such that (u, v) ∈ E and the edge (u, v) is selected uniformly
at random among the edges incident to u that have not yet been observed by the algorithm. In
Corollary 34 we show that this implies a lower bound when the algorithm may perform (standard)
neighbor queries instead of random new-neighbor queries.
We first give a simple lower bound that depends on n and t(G).
Theorem 14. Any
algorithm for the number of triangles in a graph
 multiplicative-approximation

n
must perform Ω t(G)1/3 queries, where the allowed queries are degree queries, pair queries and
random new-neighbor queries.

Proof. For every n and every 1 ≤ t ≤ n3 we next define a graph G1 and a family of graphs G2 for
which the following holds. The graph G1 is the empty graph over n vertices.
In G2 , each graph

1/3
1/3
consists of a clique of size t
and an independent set of size n − t
. See Figure 1 for an
illustration. Within G2 the graphs differ only in the labeling of the vertices. By construction, G1
contains no triangles and each graph in G2 contains Θ(t) triangles. Clearly, unless the algorithm
“hits” a vertex in the clique it cannot distinguish between the two cases.
 The probability of hitting
1/3 /n. Thus, in order for this
such a vertex in a graph selected uniformly at random
from
G
is
t
2


event to occur with high constant probability, Ω

n
t1/3

queries are necessary.

We next state our main theorem.

Theorem 15. Any multiplicative-approximation
algorithm for the number of triangles in a graph

n 3/2 o
m
must perform at least Ω min t(G) , m
queries, where the allowed queries are degree queries,
pair queries and random new-neighbor queries.

 
For every n, every 1 ≤ m ≤ n2 and every 1 ≤ t ≤ min n3 , m3/2 we define a graph G1 and
a family of graphs G2 for which the following holds. The graph G1 and all the graphs in G2 have
n vertices and m edges. For the graph G1 , t(G1 ) = 0, and for every graph G ∈ G2 , t(G) = Θ(t).
17

n

∆1/3

n − ∆1/3

Figure 1: An illustration of the two families.

n 3/2 o
We prove it is necessary to perform Ω min m t , m
queries in order to distinguish with high
constant probability between G1 and a random graph in G2 . For the sake of simplicity, in everything
√
that follows we assume that m is even.
1√
We prove that for values of t such that
t
<
 3/2  4 m, at least Ω(m) queries are required, and for
√
values of t such that t ≥ m at least Ω m t
queries are required.
We delay the discussion on the former case to Subsection 4.4, and start with the case that
√
t ≥ m. Our construction of G2 depends on the value of t as a function of m where we deal
separately with the following two ranges of t:
1. t ∈ [Ω(m), O(m3/2 )].
√
2. t ∈ [Ω( m, O(m)].
We prove that for every t as above, Ω(m3/2 /t) queries are needed in order to distinguish between
the graph G1 and a random
 graph in G2 . Observe that by Proposition 12, for every graph G, it
holds that t(G) = O m3/2 . Hence, the above ranges indeed cover all the possible values of t as a
function of m.
A high level discussion of the lower bound. The constructions for the different ranges of
√
t ≥ m are all based on the same basic idea, and have the following in common. In all construction
√
for t as above, G1 consists of a complete bipartite graph (L ∪ R, E) with |L| = |R| = m and an
√
independent set of n − 2 m vertices. The basic structure of the graphs in the family G2 is the same
as that of G1 with the following modifications:
√
• For every value of t, we add t/ m edges between vertices in L (and similarly in R). Since
√
each edge contributes (roughly) m triangles, this gives the desired total number of triangles
in the graph. In the case that t = m this is done by adding a perfect matching within L and
a perfect matching within R. In the case that t > m we add several such perfect matchings,
√
√
and in the case that m ≤ t ≤ m/4 we add a (non-perfect) matching of size t/ m.
• In order to maintain the degrees of all the vertices in the bipartite component, we remove
edges between vertices in L and R.
For an illustration of the case t = m, see Figure 2. In what follows we assume that the algorithm
knows in advance which vertices are in L and which are in R, and consider only the bipartite
component of the graphs. In order to give the intuition for the m3/2 /t lower bound we consider
each type of query separately, starting with degree queries.

18

Since both in the graph G1 and in all the graphs in G2 , all the vertices in L ∪ R have the
√
same degree (of m), degree queries do not reveal any information that is useful for distinguishing
between the two.
As for pair queries, unless the algorithm queries a pair in L × L (or R × R) and receives a
positive answer, or queries a pair in L × R and receives a negative answer, the algorithm cannot
distinguish between the bipartite component of the graph G1 and those of the graphs in G2 . We
√
refer to these pairs as witness pairs. Roughly speaking, since there are Θ(t/ m) such pairs, and
m pairs in total, it takes Ω(m3/2 /t) queries in order to “catch a witness pair”.
We are left to deal with neighbor queries. Here too, distinguishing between the graph G1 and
the graphs in G2 can be done by “catching a witness”. That is, if the algorithm queries for a
neighbor of a vertex in L and the answer is another vertex in L (analogously for a vertex in R).
As before, the probability for hitting such a witness pair is small. However, there is another source
of difference resulting from neighbor queries. When the algorithm queries a vertex v ∈ L there is
a difference in the conditional distribution on answers v ∈ R when the answer is according to the
graph G1 or according to a graph in the family G2 . The reason for the difference, is that in the
√
graph G1 every vertex has exactly m neighbors in the opposite side, while for graphs in G2 , each
√
√
vertex has Θ( m − t/m) neighbors in the opposite side (for the range Ω( m) ≤ t ≤ O(m) this is
true on average). We prove that this difference in sufficiently small so as to ensure the Ω(m3/2 /t)
lower bound.
Our formal analysis is based on defining two processes that interact with an algorithm for
approximating the number of triangles, denoted ALG. The first process answer queries according
to G1 , and the second process answers queries while constructing a uniformly selected graph in
G2 . An interaction between ALG and each of these processes induces a distribution over sequences
of queries and answers. We prove that if the number of queries performed by ALG is smaller
than m3/2 /(ct) for a sufficiently large constant c, then the statistical distance between the two
distributions is a small constant.
We start by addressing the case that t = m in Subsection 4.1, and deal with the case that
√
3/2
m < t ≤ m8 in Subsection 4.2, and with the case that m ≤ t ≤ m
4 in Subsection 4.3.
Before embarking on the proof for t = m, we introduce the notion of a knowledge graph (as
defined previously in e.g., [GR02]), which will be used in all lower bound proofs. Let ALG be an
algorithm for approximating he number of triangles, which performs Q queries. Let qt denote its tth
query and let at denote the corresponding answer. Then ALG is a (possibly probabilistic) mapping
from query-answer histories π , h(q1 , a1 ), . . . , (qt , at )i to qt+1 , for every t < Q, and to N for t = Q.
We assume that the mapping determined by the algorithm is determined only on histories that
are consistent with the graph G1 or one of the graphs in G2 . Any query-answer history π of length
kn
t can be used to define a knowledge graph Gkn
π at time t. Namely, the vertex set of Gπ consists
of n vertices. For every new-neighbor query ui answered by vi for i ≤ t, the knowledge graph
contains the edge (ui , vi ), and similarly for every pair query (uj , vj ) that was answered by 1. In
addition, for every pair query (ui , vi ) that is answered by 0, the knowledge graph maintains the
information that (ui , vi ) is a non-edge. The above definition of the knowledge graph is a slight
abuse of the notation of a graph since Gkn
π is a subgraph of the graph tested by the algorithm, but
it also contains additional information regarding queried pairs that are not edges. For a vertex u,
kn
kn
we denote its set of neighbors in the knowledge graph by Γkn
π (u), and let dπ (u) = Γπ (u) . We
denote by Nπkn (u) the set of vertices v such that (u, v) is either an edge or a non-edge in Gkn
π .

19

4.1

A lower bound for t = m

4.1.1

The lower-bound construction

√
The graph G1 has two components. The first component is a complete bipartite graph with m
√
vertices on each side, i.e, K√m,√m , and the second component is an independent set of size n−2 m.
We denote by L the set of vertices ℓ1 , . . . , ℓ√m on the left-hand side of the bipartite component and
by R the set of vertices r1 , . . . , r√m on its right-hand side. The graphs in the family G2 have the
same basic structure with a few modifications. We first choose for each graph a perfect matching
M C between the two sides R and L and remove the edges in M C from the graph. We refer to the
removed matching as the “red matching” and its pairs as “crossing non-edges” or “red pairs”. Now,
we add two perfect matching from L to L and from R to R, denoted M L and M R respectively.
We refer to these matchings as the blue matchings and their edges as “non-crossing edges” or “blue
pairs”. Thus for each choice of three perfect matchings M C , M L and M R as defined above, we
have a corresponding graph in G2 .
√
Consider a graph G ∈ G2 . Clearly, every blue edge participate in m − 2 triangles. Since, every
√
√
triangle in the graph contains exactly one blue edge, there are 2 m · ( m − 2) = Θ(m) triangles
in G.

√

√
n−2 m

m

Figure 2: An illustration of the family G2 for t = m.
4.1.2

Definition of the processes P1 and P2

In what follows we describe two random processes, P1 and P2 , which interact with an arbitrary
algorithm ALG. The process P1 answers ALG’s queries consistently with G1 . The process P2
answers ALG’s queries while constructing a uniformly selected random graph from G2 . We assume
without loss of generality that ALG does not ask queries whose answers can be derived from its
knowledge graph, since such queries give it no new information. For example, ALG does not ask
a pair query about a pair of vertices that are already known to be connected by an edge due to a
neighbor query. Also, we assume ALG knows in advance which vertices belong to L and which to
to R, so that ALG need not query vertices in the independent set. Since the graphs in G2 differ
from G1 only in the edges of the subgraph induced by L ∪ R, we think of G1 and graphs in G2 as
consisting only of this subgraph. Finally, since in our constructions all the vertices in L ∪ R have
√
the same degree of m, we assume that no degree queries are performed.
For every, Q, every t ≤ Q and every query-answer history π of length t − 1 the process P1
answers the tth query of the algorithm consistently with G1 . Namely:
• For a pair query qt = (u, v) if the pair (u, v) is a crossing pair in G1 , then the process replies
1, and otherwise it replies 0.
20

• For a random new-neighbor query qt = u the process answers with a random neighbor of u that
has yet been observed by the algorithm. That is, for every vertex v such that v ∈ Γ(u)\Γkn
π (u)
√
the process replies at = v with probability 1/( m − dkn
(u)).
π
The process P2 is defined as follows:
• For a query-answer history π we denote by G2 (π) ⊂ G2 the subset of graphs in G2 that are
consistent with π.
• For every t ≤ Q and every query-answer history π of length t − 1, the process P2 selects a
graph in G2 uniformly at random and answers the tth query as follows.
1. If the tth query is a pair query qt = (u, v), then P2 answers the query qt according to the
selected graph.
2. If the tth query is a random new-neighbor query qt = ut , then P2 ’s answer is a uniform
new neighbor of ut in the selected graph.
• After all queries are answered (i.e., after Q queries), uniformly choose a random graph G
from G2 (π).
For a query-answer history π of length Q we denote by π ≤t the length t prefix of π and by π ≥t
the Q − t + 1 suffix of π.
We note that the selected graph is only used to answer the tth query and is then “discarded
back to” the remaining graphs that are consistent with that answer (and all previous answers in
π).
Claim 16. Let π be a query-answer history of length t − 1. We use ◦ to denote concatenation.
• If the tth query is a pair query, then at = 1 with probability
|G2 (π ◦ (qt , 1))|
,
|G2 (π)|
and at = 0 with probability

|G2 (π ◦ (qt , 0))|
.
|G2 (π)|

• If the tth query is a random new-neighbor query qt = ut , then for every v ∈ V \ Γkn
π (u) the
probability that the process P2 answers at = v is
1
|G2 (π ◦ (qt , v))|
·√
.
|G2 (π)|
m − dkn
π (ut )
If v ∈ Γkn
π (u) then the probability that P2 answers at = v is 0.
Proof. First consider a pair query qt = (ut , vt ). The probability that (ut , vt ) is an edge in the graph
chosen by the process P2 is the fraction of graphs in G2 (π) in which (ut , vt ) is an edge. This is
t ,1))|
. Similarly, the probability of choosing a graph in which (ut , vt ) is not an edge
exactly |G2 (π◦(q
|G2 (π)|

is

|G2 (π◦(qt ,0))|
.
|G2 (π)|

Now consider a random new-neighbor query qt = ut . We start with the case that v ∈ V \ Γkn
π .
The probability that v is chosen by P2 is the probability that a graph G in which v is a neighbor
of ut is chosen in the first step, and that v is the chosen new neighbor among all of u’s neighbors
21

in the second step. Since there are |G2 (π ◦ (u, v))| graphs in which v is a neighbor of ut , and ut has
√
m − dkn
π (ut ) neighbors, this happens with probability
|G2 (π ◦ (u, v))|
1
·√
.
|G2 |
m − dkn
π (ut )

For a vertex v such that v ∈
/ V \ Γkn
π , in every graph G ∈ G2 , v is not a neighbor of ut , implying
that the probability that the process replies at = v is 0.
Lemma 17. For every algorithm ALG, the process P2 , when interacting with ALG, answers ALG’s
queries according to a uniformly generated graph G in G2 .

Proof. Consider a specific graph G ∈ G2 . Let π be the query-answer history generated by the
interaction between ALG and P2 . Let Q be the number of queries performed during the interaction.
The probability that G is the resulting graph from that interaction is
1
Pr[G ∈ G2 (π ≤1 )] · Pr[G ∈ G2 (π ≤2 ) | G ∈ G2 (π ≤1 )] · . . . · Pr[G ∈ G2 (π ≤Q )|G ∈ G2 (π ≤Q−1 )] ·
|G(π ≤Q )|
|G2 (π ≤1 )| |G2 (π ≤2 )|
|G2 (π ≤Q )|
1
1
=
·
·
.
.
.
·
·
=
,
|G2 |
|G2 (π ≤1 )|
|G2 (π ≤Q−1 )| |G2 (π Q )|
|G2 |
and the lemma follows.

b
For a fixed algorithm ALG that performs Q queries, and for b ∈ {1, 2}, let DALG
denote the
distribution on query-answers histories of length Q induced by the interaction between ALG and
3/2
Pb . We shall show that for every algorithm ALG that performs at most
Q = m
100t queries, the

statistical distance between D1ALG and D2ALG , denoted d D1ALG , D2ALG , is at most 31 . This will
imply that the lower bound stated in Theorem 15 holds for the case that t(G) = m. In order to
obtain this bound we introduce the notion of a query-answer witness pair, defined next.

Definition 6. We say that ALG has detected a query-answer witness pair in three cases:
1. If qt is a pair query for a crossing pair (ut , vt ) ∈ L × R and at = 0.
2. If qt is a pair query for a non-crossing pair (ut , vt ) ∈ (L × L) ∪ (R × R) and at = 1.
3. If qt = ut is a random new-neighbor query and at = v for some v such that (ut , v) is a
non-crossing pair.
We note that the source of the difference between D1ALG and D2ALG is not only due to the
probability that the query-answer history contains a witness pair (which is 0 under D1ALG and
non-0 under D2ALG ). There is also a difference in the distribution over answers to random new
neighbor queries when the answers do not result in witness pairs (in particular when we condition
on the query-answer history prior to the tth query). However, the analysis of witness pairs serves
us also in bounding the contribution to the distance due to random new neighbor queries that do
not result in a witness pairs.
Let w be a “witness function”, such that for a pair query qt on a crossing pair, w(qt ) = 0, and
for a non-crossing pair, w(qt ) = 1. The probability that ALG detects a witness pair when qt is a
pair query (ut , vt ) and π is a query-answer history of length t − 1, is
PrP2 [w(qt ) | π] =

|G2 (π ◦ (qt , w(qt )))|
|G2 (π ◦ (qt , w(qt )))|
≤
.
|G2 (π)|
|G2 (π ◦ (qt , w(qt )))|

Therefore, to bound the probability that the algorithm observes a witness pair it is sufficient to
bound the ratio between the number of graphs in G2 (π ◦ (q, w(qt ))) and the number of graphs in
G2 (π ◦ (q, w(qt ) )). We do this by introducing an auxiliary graph, which is defined next.
22

4.1.3

The auxiliary graph for t = m

For every t ≤ Q, every query-answer history π of length t − 1 for which π is consistent with G1 (that
is, no witness pair has yet been detected), and every pair (u, v), we consider a bipartite auxiliary
graph Aπ,(u,v) . On one side of Aπ,(u,v) we have a node for every graph in G2 (π) for which the pair
(u, v) is a witness pair. We refer to these nodes as witness graphs. On the other side of the auxiliary
graph, we place a node for every graph in G2 (π) for which the pair is not a witness. We refer
to these nodes as non-witness graphs. We put an edge in the auxiliary graph between a witness
graph W and a non-witness graph W if the pair (u, v) is a crossing (non-crossing) pair and the two
graphs are identical except that their red (blue) matchings differ on exactly two pairs – (u, v) and
one additional pair. In other words, W can be obtained from W by performing a switch operation,
as defined next.
Definition 7. We define a switch between pairs in a matching in the following manner. Let (u, v)
and (u′ , v ′ ) be two matched pairs in a matching M . A switch between (u, v) and (u′ , v ′ ) means
removing the edges (u, v) and (u′ , v ′ ) from M and adding to it the edges (u, v ′ ) and (u′ , v).
Note that the switch process maintains the cardinality of the matching. We denote by dw (Aπ,(u,v) )
the minimal degree of any witness graph in Aπ,(u,v) , and by dnw (Aπ,(u,v) ) the maximal degree of the
non-witness graphs. See Figure 3 for an illustration.

edge in
Aπ,(u,v)

dw
witness
graphs

non-witness ′
u
graphs

v′

u′

v′

u

v

u

v

dw

A witness graph W
(a) The auxiliary graph with witness nodes on
the left and non-witness nodes on the right.

W – A neighbor of W

(b) An illustration of two neighbors in the auxiliary graph
for t = m.

Figure 3
3/2

Lemma 18. Let t = m and Q = m
100t . For every t ≤ Q, every query-answer history π of length
t − 1 such that π is consistent with G1 and every pair (u, v),
dnw (Aπ,(u,v) )
2
2t
≤ √ = 3/2 .
dw (Aπ,(u,v) )
m
m
Proof. Recall that the graphs in G2 are as defined in Subsection 4.1.1 and illustrated in Figure 2.
In the following we consider crossing pairs, as the proof for non-crossing pairs is almost identical.
Recall that a crossing pair is a pair (u, v) such that u ∈ L and v ∈ R or vise versa. A witness graph
W with respect to the pair (u, v) is a graph in which (u, v) is a red pair, i.e., (u, v) ∈ M C . There
is an edge from W to every non-witness graph W ∈ G2 (π) such that M C (W ) and M C (W ) differ
exactly on (u, v) and one additional edge.

23

Every red pair (u′ , v ′ ) ∈ M C (W ) creates a potential non-witness graph W (u′ ,v′ ) when switched
with (u, v) (as defined in Definition 7). However, not all of the these non-witness graphs are in
′
kn
G2 (π). If u′ is a neighbor of v in the knowledge graph Gkn
π , i.e., u ∈ Γπ (v), then W (u′ ,v′ ) is not
/ G2 (π). This is also the case for a
consistent with the knowledge graph, and therefore W (u′ ,v′ ) ∈
′ , v ′ ) ∈ M C such that u′ ∈
(u).
Therefore,
only
pairs
(u
/ Γkn
pair (u′ , v ′ ) such that v ′ ∈ Γkn
π (v) and
π
′
kn
v ∈
/ Γπ (u) produce a non-witness graph W (u′ ,v′ ) ∈ G2 (π) when switched with (u, v). We refer to
√

m
m
, both u and v each have at most 100
neighbors in the
these pairs as consistent pairs. Since t ≤ 100
√
knowledge graph, implying that out of the m − 1 potential pairs, the number of consistent pairs
is at least
√
√
√
m
1√
kn
kn
m − 1 − dπ (u) − dπ (v) ≥ m − 1 − 2 ·
m.
≥
100
2
√
Therefore, the degree of every witness graph W ∈ Aπ,(u,v) is at least 12 m, implying that
√
dw (Aπ,(u,v) ) ≥ 12 m.
In order to prove that dnw (Aπ,(u,v) ) = 1, consider a non-witness graph W . Since W is a nonwitness graph, the pair (u, v) is not a red pair. This implies that u is matched to some vertex
v ′ ∈ R, and v is matched to some vertex u′ ∈ L. That is, (u, v ′ ), (v, u′ ) ∈ M C . By the construction
of the edges in the auxiliary graph, every neighbor W of W can be obtained by a single switch
between two red pairs in the red matching. The only possibility to switch two pairs in M C (W )
and obtain a matching in which (u, v) is a red pair is to switch the pairs (u, v ′ ) and (v, u′ ). Hence,
every non-witness graph W has at most one neighbor.
√
We showed that dw (Aπ,(u,v) ) ≥ 21 m and that dnw (Aπ,(u,v) ) ≤ 1, implying

dnw (Aπ,(u,v) )
2
2t
≤ √ = 3/2 ,
dw (Aπ,(u,v) )
m
m
and the proof is complete.
4.1.4

Statistical distance

For a query-answer history π of length t − 1 and a query qt , let Ans(π, qt ) denote the set of possible
answers to the query qt that are consistent with π. Namely, if qt is a pair query (for a pair that
does not belong to the knowledge graph Gkn
π ), then Ans(π, qt ) = {0, 1}, and if qt is a random
new-neighbor query, then Ans(π, qt ) consists of all vertices except those in Nπkn .
3/2

Lemma 19. Let t = m and Q = m
100t . For every t ≤ Q, every query-answer history π of length
t − 1 such that π is consistent with G1 and for every query qt :
X
12t
12
PrP1 [a | π, qt ] − PrP2 [a | π, qt ] ≤ √ = 3/2 .
m
m
a∈Ans(π,qt )

Proof. We prove the lemma separately for each type of query.
• We start with a crossing pair query (ut , vt ). In this case the witnesses are red pairs. Namely,
our witness graphs for this case are all the graphs in G2 (π ◦(qt , 0)), and the non-witness graphs
are all the graphs in G2 (π ◦ (qt , 1)). By the construction of the auxiliary graph
|G2 (π ◦ (qt , 0))| · dw (Aπ,(u,v) ) ≤ |G2 (π ◦ (qt , 1))| · dnw (Aπ,(u,v) ).
This, together with Lemma 18, implies
dnw (Aπ,(u,v) )
|G2 (π ◦ (qt , 0))|
|G2 (π ◦ (qt , 0))|
2
2t
≤
≤
= √ = 3/2 .
|G2 (π)|
|G2 (π ◦ (qt , 1))|
dw (Aπ,(u,v) )
m
m
24

For a pair query qt , the set of possible answers Ans(π, qt ) is {0, 1}. Therefore,
X
PrP1 [a | π, qt ] − PrP2 [a | π, qt ]
a∈{0,1}

= PrP1 [0 | π, qt ] − PrP2 [0 | π, qt ] + PrP1 [1 | π, qt ] − PrP2 [1 | π, qt ]


2t
4t
4
2t
= 3/2 + 1 − 1 − 3/2 = 3/2 = √ .
m
m
m
m

(13)

• For a non-crossing pair query qt = (u, v) our witness graphs are graphs that contain qt as a
blue pair, i.e., graphs from G2 (π, (qt , 1)), and our non-witness graphs are graphs in which no
blue pair had been queried, i.e., graphs from G2 (π, (qt , 0)). From Lemma 18 we get that for
a non-crossing pair query qt :
dnw (Aπ,(u,v) )
2
|G2 (π ◦ (qt , 1))|
2t
|G2 (π ◦ (qt , 1))|
≤
≤
= 3/2 = √ .
|G2 (π)|
|G2 (π ◦ (qt , 0))|
dw (Aπ,(u,v) )
m
m
Therefore,
X

a∈{0,1}

PrP1 [a | π, qt ] − PrP2 [a | π, qt ]
=

PrP1 [0 | π, qt ] − PrP2 [0 | π, qt ] + PrP1 [1 | π, qt ] − PrP2 [1 | π, qt ]


2t
2t
4t
4
= 1 − 1 − 3/2 + 3/2 = 3/2 = √ .
m
m
m
m

(14)

• For a new-neighbor query qt = ut , the set of possible answers Ans(π, qt ) is the set of all the
vertices in the graph. Therefore,
X
PrP1 [a | π, qt ] − PrP2 [a | π, qt ]
a∈Ans(π,qt )

=

X

v∈R

PrP1 [v | π, qt ] − PrP2 [v | π, qt ] +

X
v∈L

PrP1 [v | π, qt ] − PrP2 [v | π, qt ] .

Recall that for a vertex v ∈ Γkn
π (u), PrP1 [v | π, qt ] = PrP2 [v | π, qt ] = 0. Therefore, it suffices to
consider only vertices v such that v ∈
/ Γkn
π (u). Assume without loss of generality that u ∈ L,
kn
and consider a vertex v ∈ R, v ∈
/ Γπ (u). Since for every v ∈ R we have that (ut , v) ∈ E(G1 ),
by the definition of P1 ,
PrP1 [v | π, qt ] = √

1
.
m − dkn
π (ut )

Now consider the process P2 . By its definition,
G2 (π ◦ (qt , v))
1
·√
G2 (π)
m − dkn
π (u)
1
G2 (π ◦ ((u, v), 1))
·√
=
G2 (π)
m − dkn
(u)
 π

1
G2 (π ◦ ((u, v), 0))
.
·√
= 1−
G2 (π)
m − dkn
π (u)

PrP2 [v | π, qt ] =

25

(15)

By the first item in the proof, for any crossing pair qt = (u, v),
4t
G2 (π ◦ (qt , 0))
4
= 3/2 = √ ,
G2 (π)
m
m

and it follows that

PrP2 [v | π, qt ] =



4t
1 − 3/2
m



·√

1
.
m − dkn
π (u)

(16)

/ Γkn
By Equations (15) and (16), we get that for every v ∈ R such that v ∈
π (u),
PrP1 [v | π, qt ] − PrP2 [v | π, qt ] = √
Therefore,
X

v∈R

PrP1 [v | π, qt ] − PrP2 [v | π, qt ] =
=

√

X

v∈R,v∈Γ
/ kn
π (u)

4t/m3/2
.
m − dkn
π (u)

(17)

PrP1 [v | π, qt ] − PrP2 [v | π, qt ]


4t/m3/2
4
4t
√
m − dkn
(u)
·
= 3/2 = √ .
π
kn
m − dπ (u)
m
m

(18)

Now consider a vertex v ∈ L. Observe that for every v ∈ L, it holds that v ∈
/ Γkn
π (u) since
otherwise π is not consistent with G1 . For the same reason,
PrP1 [v | π, qt ] = 0 .

(19)

As for P2 , as before,
PrP2 [v | π, qt ] =

1
G2 (π, (ut , v))
·√
.
G2 (π)
m − dkn
π (ut )

By the second item of the claim, since for every v ∈ L, (ut , v) is a non-crossing pair, we have
that
4
4t
|G2 (π, (ut , v))|
= 3/2 = √ .
(20)
|G2 (π)|
m
m
Combining Equations (19) and (20) we get that for every v ∈ L
PrP1 [v | π, qt ] − PrP2 [v | π, qt ] = √
√

3/2

m
kn
Since Q = m
100t = 100 , for every t ≤ Q, dπ (u) <
bounded by 2. Hence,

X

v∈L

4t/m3/2
.
m − dkn
π (u)

1√
2 m,

and it follows that

√

√

m−1
m−dkn (u)

is

√
4t/m3/2
PrP1 [v | π, qt ] − PrP2 [v | π, qt ] = ( m − 1) · √
m − dkn
π (u)
=

8
8t
=√ .
3/2
m
m

(21)

By Equations (18) and (21) we get
X
X
PrP1 [v | π, qt ] − PrP2 [v | π, qt ]
PrP1 [v | π, qt ] − PrP2 [v | π, qt ] +
v∈L

v∈R

12t
12
= 3/2 = √ .
m
m

(22)

26

This completes the proof.
Recall that DbALG , b ∈ {1, 2}, denotes the distribution on query-answer histories of length Q,
induced by the interaction of ALG and Pb . We show that the two distributions are indistinguishable
for Q that is sufficiently small.
Lemma 20. Let t = m. For every algorithm ALG that asks at most Q =
statistical distance between D1ALG and D2ALG is at most 31 .

m3/2
100t

queries, the

ALG be the distribution over query-answer
Proof. Consider the following hybrid distribution. Let D1,t
histories of length Q, where in the length t prefix ALG is answered by the process P1 and in the
ALG = D ALG and that
length Q − t suffix ALG is answered by the process P2 . Observe that D1,Q
1
ALG = D ALG . Let π = (π , π , . . . , π ) denote a query-answer history of length ℓ. By the triangle
D1,0
1
2
ℓ
2
Q−1
P
ALG , D ALG ) .
inequality d(D1ALG , D2ALG ) ≤
d(D1,t+1
1,t
t=0

d(D1ALG , D2ALG ) ≤

Q−1
X
t=0
1
2

ALG , D ALG ) =
It thus remains to bound d(D1,t+1
1,t

ALG
ALG
d(D1,t+1
, D1,t
).

P
π

PrDALG [π] − PrDALG [π] for every t such that
1,t+1

1,t

0 ≤ t ≤ Q − 1. Let Q denote the set of all possible queries.
X
π

PrDALG [π] − PrDALG [π] =
1,t+1

1,t

·
·

X

π1 ,...,πt−1

PrP1 ,ALG [π1 , . . . , πt−1 ] ·

X

a∈Ans((π1 ,...,πt−1 ),q)

X

πt+1 ,...,πQ

X

q∈Q

PrALG [q | π1 , . . . , πt−1 ]

PrP1 [a | π1 , . . . , πt−1 , q] − PrP2 [a | π1 , . . . , πt−1 , q]

PrP2 ,ALG [πt+1 , . . . , πQ | π1 , . . . , πt−1 , (q, a)] .

By Lemma 19, for every 1 ≤ t ≤ Q − 1, and every π1 , . . . , πt−1 and q,
X
12t
PrP1 [a | π1 , . . . , πt−1 , q] − PrP2 [a | π1 , . . . , πt−1 , q] ≤ 3/2 .
m
a∈Ans((π1 ,...,πt−1 ),q)

We also have that for every pair (q, a),
X
PrP2 ,ALG [πt+1 , . . . , πQ | π1 , . . . , πt−1 , (q, a)] = 1 .
πt+1 ,...,πQ

Therefore,
X
PrDALG [π] − PrDALG [π] ≤
π

1,t+1

1,t

Hence, for Q =

√
m
100 ,

X

PrP1 ,ALG [π1 , . . . , πt−1 ]

π1 ,...,πt−1

q∈Q

Q−1

d(D1ALG , D2ALG ) =
and the proof is complete.

X

PrALG [q | π1 , . . . , πt−1 ] ·

1
12t
1XX
1
PrDALG [π] − PrDALG [π] ≤ · Q · 3/2 ≤ ,
1,t+1
1,t
2 π
2
3
m
t=1

27

12t
12t
= 3/2 .
3/2
m
m

3/2

In the next subsection we turn to prove the theorem for the cases where m < t ≤ m8 , and for
√
the case where m ≤ t ≤ m
4 . We start with the former case. The proof will follow the building
blocks of the proof for t = m, where the only difference is in the description of the auxiliary graph
dnw (A
)
√2r .
Aπ,(u,v) and in the proof that dw (A π,(u,v)) ≤ m2t
3/2 =
m
π,(u,v)

4.2

A lower bound for m < t < m3/2

√
Let t = r · m for an integer r such that 1 < r ≤ 18 m. It is sufficient for our needs to consider only
values of t for which r is an integer. The proof of the lower bound for this case is a fairly simple
extension of the proof for the case of t = m, that is, r = 1. We next describe the modifications we
make in the construction of G2 .
4.2.1

The lower-bound construction

Let G1 be as defined in Subsection 4.1.1. The construction of G2 for t = r · m can be thought
of as repeating the construction of G2 for t = m (as described in Subsection 4.1.1) r times. We
√
again start with a complete bipartite graph K√m,√m and an independent set of size n − 2 m. For
each graph G ∈ G2 we select r perfect matchings between the two sides R and L and remove these
edges from the graph. We denote the r perfect matchings by M1C , . . . , MrC and refer to them as the
red matchings. We require that each two perfect matchings MiC and MjC do not have any shared
edges. That is, for every i and for every j, for every (u, v) ∈ MiC it holds that (u, v) ∈
/ MjC . In
order to maintain the degrees of the vertices, we next select r perfect matchings for each side of the
bipartite graph (L to L and R to R). We denote these matchings by M1R , ..., MrR and M1L , ..., MrL
respectively. Again we require that no two matchings share an edge. We refer to these matchings
as the blue matchings and their edges as blue pairs. Each such choice of 3r matchings defines a
graph in G2 .
Let G be a graph in G2 . We say that a triangle is blue if all its edges are blue. Otherwise
√
we say the triangle is mixed. Observe that every blue edge in G participates in at least m − 2r
mixed triangles, and at most r blue triangles. Also note that every two mixed triangles are disjoint.
√
√
√
√
√
Therefore, there are at least 12 r m · (2 m − 2r) = Ω(r · m) and at most 21 r m · (2 m − 2r) + r 2 m
√
triangles in G. Since r < 18 m, we get that every graph in G has Θ(r · m) triangles.
4.2.2

The processes P1 and P2

The definition of the processes P1 and P2 is the same as in Subsection 4.1.2 (using the modified
definition of G2 ), and Lemma 17 holds here as well.
4.2.3

The auxiliary graph

As before, for every t ≤ Q, every query-answer history π of length t−1 such that π is consistent with
G1 and every pair (u, v), we define a bipartite auxiliary graph Aπ,(u,v) , such that on one side there
is a node for every witness graph W ∈ G2 (π), and on the other side a node for every non-witness
graph W ∈ G2 (π). The witness graphs for this case are graphs in which (u, v) is a red (blue) edge
in one of the red (blue) matchings. If (u, v) is a crossing pair, then for every witness graph W ,
(u, v) ∈ MiC (W ) for some 1 ≤ i ≤ r. If (u, v) is a non-crossing pair, then for every witness graph
W , (u, v) ∈ MiL (W ) or (u, v) ∈ MiL (W ). There is an edge from W to every graph W such that
the matching that contains (u, v) in W and the corresponding matching in W differ on exactly two
pairs – (u, v) and one additional pair. For example, if (u, v) ∈ MiC (W ), there is an edge from W
to every graph W such that MiC (W ) and MiC (W ) differ on exactly (u, v) and one additional pair.
28

√

3/2

Lemma 21. Let t = r · m for an integer r such that 1 < r ≤ 8m and let Q = m
100t . For every
t ≤ Q, every query-answer history π of length t − 1 such that π is consistent with G1 and every
pair (u, v),
dnw (Aπ,(u,v) )
2r
2t
≤ 3/2 = √ .
dw (Aπ,(u,v) )
m
m
Proof. We again analyze the case in which the pair is a crossing pair (u, v), as the proof for a
non-crossing pair is almost identical. We first consider the minimal degree of the witness graphs in
Aπ,(u,v) . Let MiC be the matching to which (u, v) belongs. As before, only pairs (u′ , v ′ ) ∈ MiC such
′ / Γkn (v) result in a non-witness graph W ∈ G (π) when switched with (u, v).
that u′ ∈
/ Γkn
2
π
π (u), v ∈
However, we have an additional constraint. Since by our construction no two red matchings share
an edge, it must be that u′ is not matched to v in any of the other r red matching, and similarly
√
m3/2
)
that u is not matched to v ′ in any of the other matchings. It follows that of the ( m−1−2· 100·r·m
√

potential pairs (as in the proof of Lemma 18), we discard 2r additional pairs. Since 1 ≤ r ≤ 8m
√
√
√
√
√
we remain with ( m − 1 − 50m − 14 m) ≥ 12 m potential pairs. Thus, dw (Aπ,(u,v) ) ≥ 12 m.
We now turn to consider the degree of the non-witness graphs and prove that dnw (Aπ,(u,v) ) ≤ r.
Consider a non-witness graph W . To prove that W has at most r neighbors it is easier to consider
all the possible options to “turn” W from a non-witness graph into a witness graph. It holds that
for every j ∈ [r], (u, v) ∈
/ MjC (W ). Therefore for every matching MjC , u is matched to some vertex,
′
denoted vj and v is matched to some vertex, denoted u′j . If we switch between the pairs (u, vj′ )
and (v, u′j ), this results in a matching in which (u, v) is a witness pair. We again refer the reader
to Figure 3b, where the illustrated matching can be thought of as the j th matching. Denote the
resulting graph by W(u′j ,vj′ ) . If the pair (u′j , vj′ ) has not been observed yet by the algorithm then

W(u′j ,vj′ ) is a witness graph in Aπ,(u,v) . Therefore there are at most r options to turn W into a
√
witness graph, and dnw (Aπ,(u,v) ) ≤ r. We showed that dw (Aπ,(u,v) ) ≥ 21 m and dnw (Aπ,(u,v) ) ≤ r,
implying
dnw (Aπ,(u,v) )
2r
2t
≤ √ = 3/2 ,
dw (Aπ,(u,v) )
m
m
as required.
4.2.4

Statistical distance

The proof of the next lemma is exactly the same as the proof of Lemma 19, except that occurrences
√
√
of the term (t/m3/2 ) are replaced by (r/ m) instead of (1/ m), and we apply Lemma 21 instead
of Lemma 18.
√

3/2

Lemma 22. Let t = r · m for an integer r such that 1 < r ≤ 8m and let Q = m
100t . For every
t ≤ Q, every query-answer history π of length t − 1 such that π is consistent with G1 and for every
query qt ,
X
12t
12r
PrP1 [a | π, qt ] − PrP2 [a | π, qt ] = 3/2 = √ .
m
m
a∈Ans(π,qt )

The proof of the next lemma is same as the proof of Lemma 20 except that we replace the
application of Lemma 19, by an application of Lemma 22.
Lemma 23. Let t = r · m for an integer r such that 1 < r ≤
performs at most Q =

m3/2
100t

√

m
8 .

For every algorithm ALG that

queries, the statistical distance between D1ALG and D2ALG is at most 13 .
29

4.3

A lower bound for

√

m ≤ t ≤ 14 m

√
Similarly√to the previous section, we let t = k m and assume that k is an integer such that
1 ≤ k ≤ 4m .
4.3.1

The lower-bound construction

The construction of the graph G1 is as defined in Subsection 4.1.1, and we modify the construction of
the graphs in G2 . As before, the basic structure of every graph is a complete bipartite graph K√m,√m
√
and an independent set of size n−2 m vertices. In this case, for each graph in G2 , we do not remove
a perfect matching from the bipartite graph, but rather a matching M C of size k. In order to keep
√
the degrees of all vertices to be m, we modify the way we construct the blue matchings. Let M C =
{(ℓi1 , ri1 ), (ℓi2 , ri2 ), . . . , (ℓik , rik )} be the crossing matching. The blue matchings will be M L =
{(ℓi1 , ℓi2 ), (ℓi3 , ℓi4 ), . . . , (ℓik −1 , ℓik )} and M R = {(ri1 , ri2 ), (ri3 , ri4 ), . . . , (rik −1 , rik )}. Note that every
matched pair belongs to a four-tuple hℓij , ℓij+1 , rij+1 , rij i such that (ℓij , rij ) and (ℓij+1 , rij+1 ) are red
pairs and (ℓij , ℓij+1 ) and (rij , rij+1 ) are blue pairs. We refer to these structures as matched squares
and to four-tuples (ℓx , ℓy , rz , rw ) such that no pair in the tuple is matched as unmatched squares.
See Figure 4 for an illustration. Every graph in G2 is defined by its set of k four-tuples.
Similarly to previous constructions, in every graph G ∈ G2 , every blue edge participates in
√
m − 2 triangles. Since every triangle in the G contains exactly one blue edge, we have that G has
√
√
k · ( m − 2) = Θ(k m) triangles.

√

The ith
matched square

m

Figure 4: An illustration of the bipartite component in the family G2 for
4.3.2

√
m ≤ t ≤ 14 m.

The processes P1 and P2

We introduce a small modification to the definition of the processes P1 and P2 . Namely, we leave
the answering process for pair queries as described in Subsection 4.1.2 and modify the answering
process for random new-neighbor queries as follows. Let t ≤ Q, and π be a query-answer history of
length t − 1 such that π is consistent with G1 . If the tth query is a new-neighbor query qt = u and
1√
in Subsection 4.1.2. However, if
dkn
π (u) < 2 m, then the processes P1 and P2 answer as described √
1
the tth query is a new-neighbor query qt = u such that dkn
(u)
≥
π
2 m, then the processes answers
as follows.
• The process P1 answers with the set of all neighbors of u in G1 . That is, if u is in L, then the
process replies with a = R = {r1 , . . . , r√m }, and if u is in R, then the process replies with
a = L = {ℓ1 , . . . , ℓ√m }.

30

The process P2 answers with a = {v1 , . . . , v√m }, where {v1 , . . . , v√m } is the set of neighbors
of u in a subset of the graphs in G2 . By the definition of G2 , if u is in L, then this set is either
R, or it is R \ {ri } ∪ {ℓj } for some ri ∈ R and ℓj ∈ L, and if u is in R, then this set is either
L, or it is L \ {ℓi } ∪ {rj } for some ℓi ∈ L and rj ∈ R. For every such set a ∈ Ans(π, qt ), the
process returns a as an answer with probability
|G2 (π ◦ (qt , a))|
.
|G2 (π)|
We call this query an all-neighbors query.
First note that the above modification makes the algorithm “more powerful”. That is, every
algorithm that is not allowed all-neighbors query can be emulated by an algorithm that is allowed
this type of query. Therefore this only strengthen our lower bound results.
Also note that this modification does not affect the correctness of Lemma 17. We can redefine
the function αt (π) to be


if qt (π) is a pair query
1 √

kn
αt (π) = 1/ m − dπ≤t−1 (u) if qt (π) = u is a random new-neighbor query ,


1
if qt (π) is an all-neighbors query
and the rest of the proof follows as before.
4.3.3

The auxiliary graph

For every t ≤ Q, every query-answer history π of length t − 1 such that π is consistent with G1
and every pair (u, v), the witness graphs in Aπ,(u,v) are graphs in which (u, v) is either a red pair
or a blue pair. There is an edge between a witness graph W and a non-witness graph W if the two
graphs have the same set of four-tuples except for two matched squares – one that contains the
pair (u, v), hu, v, u′ , v ′ i and another one.
Definition 8. We define a switch between a matched square and an unmatched square in the following manner. Let hu, v, u′ , v ′ i be a matched square and hx, y, x′ , y ′ i be an un matched squares.
Informally, a switch between the squares is “unmatching” the matched square and instead “matching” the unmatched square.
Formally, a switch consists of two steps. The first step is removing the edges (u, v) and (u′ , v ′ )
from the red matching M C and the edges (u, u′ ) and (v, v ′ ) from the blue matchings M L and M R
respectively. The second step is adding the edges (x, y) and (x′ , y ′ ) from the red matching M C and
the edges (x, x′ ) and (y, y ′ ) from the blue matchings M L and M R respectively. See Figure 5 for an
illustration.
√
√
3/2
Lemma 24. Let t = k · m for an integer k such that 1 < k ≤ 4m and let Q = m
600t . For every
t ≤ Q, every query-answer history π of length t − 1 such that π is consistent with G1 and every
pair (u, v),
dnw (Aπ,(u,v) )
16k
16t
=
= 3/2 .
dw (Aπ,(u,v) )
m
m

Proof. We start with proving that dw (Aπ,(u,v) ) ≥ 12 m. A witness graph in Aπ,(u,v) with respect
to a pair (u, v) is a graph in which (u, v) is part of a matched square hu, v, u′ , v ′ i. Potentially,
31

x′

y′

x′

y′

x

y

x

y

A switch

u′

v′

u′

v′

u

v

u

v

Figure 5: An illustration of a switch between the squares hu, v, u′ , v ′ i and hx, y, x′ , y ′ i.
hu, v, u′ , v ′ i could be switched with every unmatched square to √
get a non-witness
pair. There are
√
√
m−k 
m−k 
m − k unmatched vertices on each side, so that there are
·
≥ 18 m2 potential
2
2
′
′
squares. To get a graph that is in G2 (π), the unmatched square hx, y, x , y i must be such that
none of the induced pairs between the vertices x, x′ , y, y ′ have been observed yet by the algorithm.
When all-neighbor queries are allowed, if at most Q queries has been performed, then at most 4Q
m
≤ 14 m of the potential
pairs have been observed by the algorithm. Therefore, for at most 4 100k
squares, an induced pair was queried. Hence, every witness square can be switched with at least
1 2
1
1
1
2
2
8 m − 4 m ≥ 16 m consistent unmatched squares, implying that dw (Aπ,(u,v) ) ≥ 16 m .
To complete the proof it remains to show that dnw (Aπ,(u,v) ) ≤ mk. To this end we would like
to analyze the number of witness graphs that every non-witness W can be “turned” into. In every
non-witness graph W the pair (u, v) is unmatched, and in order to turn W into a witness graph,
one of the k matched squares should be removed and the pair (u, v) with an additional pair (u′ , v ′ )
should be “matched”. There are k options to remove an existing square, and at most m options to
choose a pair u′ , v ′ to match (u, v) with. Therefore, the number of potential neighbors of W is at
most mk. It follows that
dnw (Aπ,(u,v) )
16mk
16t
16k
=
= 3/2 ,
=
dw (Aπ,(u,v) )
m2
m
m
and the proof is complete.
4.3.4

Statistical distance

For an all-neighbors query q = u we say that the corresponding answer is a witness answer if u ∈ L
and a 6= R, or symmetrically if u ∈ R and a 6= L. Let E Q be the set of all query-answer histories π
of length Q such that there exists a query-answer pair (q, a) in π in which q is an all-neighbors pair
Q
Q
and a is a witness answer with respect to that query, and let E = ΠQ \ E Q . That is, E is the set
of all query-answer histories of length Q such that no all-neighbors query is answered with a witness
answer. Let Pe1 and Pe2 by the induced distributions of the processes P1 and P2 conditioned on the
event that the process do not reply with a witness answer. Observe that for every query-answer
history π of length t − 1, for every query qt that is either a pair query or a random new-neighbor
query and for every a ∈ Ans(π, qt ),
PrPeb [a | π, qt ] = PrPb [a | π, qt ].
for b ∈ {1, 2}. Therefore, the proof of the next lemma is exactly the same as the proof of Lemma 19,
√
except that occurrences of the term (t/m3/2 ) are replaced by (k/m) instead of (1/ m) and we apply
Lemma 24 instead of Lemma 18.
32

√
√
3/2
Lemma 25. Let t = k · m for an integer k such that 1 < k ≤ 4m and let Q = m
600t . For every
t ≤ Q, every query-answer history π of length t − 1 such that π is consistent with G1 and for every
pair or random new-neighbors query qt ,

X

a∈Ans(π,qt )

PrPe1 [a | π, qt ] − PrPe2 [a | π, qt ] =

96k
96t
= 3/2 .
m
m

Note that Lemma 25 does not cover all-neighbors queries, and hence we establish the next
lemma.
√
√
3/2
Lemma 26. Let t = k · m for an integer k such that 1 < k ≤ 4m and let Q = m
600t . For every
t ≤ Q, every query-answer history π of length t − 1 such that π is consistent with G1 and for every
all-neighbors query qt ,
16k
PrP2 [at is a witness answer | π, qt ] ≤ √ .
m
Proof. Assume without loss of generality that u ∈ L. By the definition of the process P2 , it
answers the query consistently with a uniformly selected random graph G2 ∈ G2 (π) by returning
the complete set of u’s neighbors in G2 . In G2 , there are two types of graphs. First, there are graphs
in which u is not matched, that is (u, u′ ) ∈
/ M L for every vertex u′ ∈ L. In these graphs the set
√
of u’s neighbors is R ={r1 , . . . , r m }. We refer to these graphs as non-witness graphs. The second
type of graphs are those in which (u, u′ ) ∈ M L for some u′ ∈ L and (u, v) ∈ M C for some v ∈ R.
In these graphs the set of u’s neighbors is (R \ {v}) ∪ {u′ }. We refer to these graphs as witness
graphs. As before, let Ans(π, qt ) be the set of all possible answers for an all-neighbors query qt . It
holds that
X
PrP2 [at is a witness answer | π, qt ] =
PrP2 [a | π, qt ]
a∈Ans(π,qt )
a6=R

=

X

u′ ∈L,v∈R

=

|G2 (π ◦ ((u, u′ ), 1) ◦ ((u, v), 0))|
|G2 (π)|

X |G2 (π ◦ ((u, u′ ), 1))| X |G2 (π ◦ ((u, u′ ), 1) ◦ ((u, v), 0))|
·
|G2 (π)|
|G2 (π)|
′
v∈R

u ∈L

X |G2 (π ◦ ((u, u′ ), 1))|
.
=
|G2 (π)|
′
u ∈L

Similarly to the proof of Lemma 19, for every u and u′ in L,
PrP2 [at is a witness answer | π, qt ] =

|G2 (π◦((u,u′ ),1))|
|G2 (π)|

≤

16k
m .

Therefore,

X |G2 (π ◦ ((u, u′ ), 1))| √
16k
16k
≤ m·
=√ ,
|G2 (π)|
m
m
′

u ∈L

and the lemma follows.
√
It remains to prove that a similar lemma to Lemma 20 holds for m ≤ t ≤ 14 m (and the
distributions D1ALG and D2ALG as defined in this subsection).
√
√
Lemma 27. Let t = k · m for an integer k such that 1 < k ≤ 4m . For every algorithm ALG that
performs at most Q =

m3/2
600t

queries, the statistical distance between D1ALG and D2ALG is at most 13 .
33

Q

Proof. Let the sets E Q and E be as defined in the beginning of this subsection. By the definition
of the statistical distance, and since PrP1 ,ALG [E Q ] = 0,


X
X
1
PrP1 ,ALG [π] − PrP2 ,ALG [π] +
PrP1 ,ALG [π] − PrP2 ,ALG [π] 
d(D1ALG , D2ALG ) = 
2
Q
Q
π∈E
π∈E


X
1
= PrP2 ,ALG [E Q ] +
(23)
PrP1 ,ALG [π] − PrP2 ,ALG [π]  .
2
Q
π∈E

By Lemma 26, the probability of detecting a witness as a result of an all-neighbors query is at most
√
16k
√
. Since in Q queries, there can be at most 4Q/ m all-neighbors queries, we have that
m
PrDALG [E Q ] ≤
2

1
.
6

(24)

We now turn to upper bound the second term. Let α = PrP2 ,ALG [E Q ].
X

π∈E

Q

PrP1 ,ALG [π] − PrP2 ,ALG [π]

=

X

π∈E

=

π∈E

≤

Q

X

π∈E

≤

Q

X

Q

X

π∈E

Q

Q

Q

PrPe1 ,ALG [π] · PrP1 ,ALG [E ] − PrPe2 ,ALG [π] · PrP2 ,ALG [E ]
(25)

PrPe1 ,ALG [π] − (1 − α) · PrPe2 ,ALG [π]
Q

PrPe1 ,ALG [π] − PrPe2 ,ALG [π] + α · PrPe2 ,ALG [E ]
PrPe1 ,ALG [π] − PrPe2 ,ALG [π] +

1
,
6

(26)

Q

where in Equation (25) we used the fact that PrP1 ,ALG [E ] = 1, and in Equation (26) we used the
Q
fact that PrPe2 ,ALG [E ] = 1 and that α ≤ 1/6.
Therefore, it remains to bound
X
PrPe1 ,ALG [π] − PrPe2 ,ALG [π] .
π∈E

Q

ALG for t ∈ [Q − 1] be as defined in Lemma 20 (based on the
Let the hybrid distributions D1,t
ALG
ALG
that are induced by the processes P1 and P2 that were defined in
and D2
distributions D1
ALG
ALG conditioned on the event that no
e
this subsection). Also, let D1,t be the hybrid distribution D1,t
e ALG is the distribution over query-answer
all-neighbors query is answered with a witness. That is, D
1,t
histories π of length Q, where in the length t prefix ALG is answered by the process P1 , in the
length Q − t suffix ALG is answered by the process P2 , and each all-neighbors query is answered
consistently with G1 (so that no witness is observed). By the above definitions and the triangle
inequality,

X

π∈E

Q

PrPe1 ,ALG [π] − PrPe2 ,ALG [π] ≤

Q−1
X

34

t

X

π∈E

Q

PrDe ALG [π] − PrDe ALG [π] .
1,t+1

1,t

(27)

As in the proof of Lemma 20 we have that for every t ∈ [Q − 1],
X
PrDe ALG [π] − PrDe ALG [π]
π∈E

1,t+1

Q

1,t

X

=

π ′ =π1 ,...,πt−1 ,qt :
t−1
π ′ ∈E

PrPe1 ,ALG [π ′ , qt ] ·

X

PrPe1 [a | π ′ , qt ] − PrPe2 [a | π ′ , qt ] .

a∈Ans(π ′ ,qt ):
t
π ′ ◦(qt ,a)∈E

(28)

By Lemma 25 (and since for an all-neighbor query qt we have that the (unique) answer according
to Pe2 is the same as according to Pe1 ),
X

PrPe1 [a | π ′ , qt ] − PrPe2 [a | π ′ , qt ] ≤

a∈Ans(π ′ ,qt ):
t
π ′ ◦(qt ,a)∈E

and it follows that

X

π∈E

Hence, for Q =

PrDe ALG [π] − PrDe ALG [π] ≤
1,t+1

Q

1,t

96k
96t
= 3/2 ,
m
m

96t
96k
= 3/2 .
m
m

m3/2
600t ,
Q−1
X
t

X

π∈E

Q

PrDe ALG [π] − PrDe ALG [π] ≤ Q ·
1,t

1,t+1

1
48t
≤ .
3/2
6
m

Combining Equations (23), (24), (26), (27) and (29), we get


1 1 1 1
1
ALG
ALG
+ +
d(D1 , D2 ) ≤
≤ ,
2 6 6 6
3

(29)

(30)

and the proof is complete.

4.4
4.4.1

Lower Bound for t <

1√
m.
4

The construction

In this case the basic structure of G1 and G2 is a bit different. Also, for the sake of simplicity, we
present graphs with 2m edges, and either 0 or 4t triangles. The graph G1 has three components –
√
√
two complete bipartite graphs, each over 2 m vertices, and an independent set of size n − 4 m.
Let A and B be the left-hand side and the right-hand side sets, respectively, of the first bipartite
component, and C and D of the second one. We refer to the edges between
A and B and the edges
√
m
between C and D as black edges. We divide each of these
sets into t subsets of size t, denoted
√
{Λ1 , . . . , Λ √m } for Λ ∈ {A, B, C, D}. For every 1 ≤ i ≤
t

m
t ,

we first remove a complete bipartite

graph between Ai and Bi and between Ci and Di , and refer to the removed edges as red edges.
We then add a complete bipartite graph between Bi and Ci and between Di and Ai , and refer to
√
added edges as blue edges. Note that this maintains the degrees of all the vertices to be m.
In G2 the basic structure of all the graphs is the same as of G1 with the following modifications.
Each graph is defined by the choice of four “special” vertices a∗ , b∗ , c∗ , d∗ such that a∗ ∈ Aia∗ , b∗ ∈
Bib∗ , c∗ ∈ Cic∗ and d∗ ∈ Did∗ for some indices ia∗ , ib∗ , ic∗ and id∗ such that no two indices are equal.
We then add edges (a∗ , c∗ ) and (b∗ , d∗ ), referred to as green edges, and remove edges (a∗ , b∗ ) and
35

A

B

C

D

c∗

a∗

d∗

b∗

Figure 6: An illustration of a graph in G2 . The broken thin (red) edges describe edges that were
removed and the thin (blue) edges describe edges that were added. The broken thick (purple) edges
describe the special non-edges (a∗ , b∗ ) and (c∗ , d∗ ). The curly (green) edges describe the special
edges (a∗ , c∗ ) and (b∗ , d∗ ).
(c∗ , d∗ ), referred to as purple edges. We also refer to the green and purple edges as special edges.
Note that we add one edge and remove one edge from each special vertex, thus maintaining their
initial degrees. See Figure 6.
We first prove that t(G1 ) = 0 and then that for every graph G in G2 , t(G) = 4t.
Claim 28. The graph G1 has no triangles.
Proof. Consider an edge (u, v) in G1 . First assume u and v are connected by a black edge, that
is, they are on different sides of the same bipartite component. Hence we can assume without loss
of generality that u ∈ A and that v ∈ B. Since u is in A it is only connected to vertices in B or
vertices in D. Since v is in B it is only connected to vertices in A or vertices in C. Thus u and v
cannot have a common neighbor. A similar analysis can be done for a pair (u, v) that is connected
by a blue edge. Therefore t(G) is indeed zero as claimed.
Claim 29. For every graph G ∈ G2 , t(G) = 4t.
Proof. Since the only differences between G1 and graphs in G2 are the two added green edges and
the two removed red edges, any triangle in G2 must include a green edge. Therefore we can count
all the triangles that the green edges form. Consider the green edge (a∗ , c∗ ) and recall that a∗ is
in Aia∗ and c∗ is in Cic∗ . The only common neighbors of (a∗ , c∗ ) are all the vertices in Bic∗ and all
the vertices in Dia∗ . A vertex v such that v ∈
/ Bic∗ and v ∈
/ Dia∗ is either (1) in A or in D \ Dia∗ , in
which case it is not a neighbor of a∗ , or it is (2) in C or in B \Bic∗ , in which case it is not a neighbor
36

of c∗ . Since both Bic∗ and Dia∗ are of size t, the edge (a∗ , c∗ ) participates in 2t triangles. Similarly
the edge (b∗ , d∗ ) participate in 2t triangles, and together we get that t(G) = 4t, as claimed.
4.4.2

The processes P1 and P2

The definition of the processes P1 and P2 is the same as in Subsection 4.3.2 (using the modified
definitions of G1 and G2 ).
4.4.3

The auxiliary graph

We define a switch for this case as well. Informally, a switch between a matched pair (u∗ , v ∗ ) and
an unmatched pair (u, v) is “unmatching” (u∗ , v ∗ ) and “matching” (u, v) instead. Formally stating
we define a switch as follows.
Definition 9. A switch between a green pair (a∗ , c∗ ) and a pair (a, c) such that a ∈ Ai , c ∈ Cj
and none of the indices i, j, ib∗ , id∗ are equal, is the following two steps process. In the first step we
“unmatch” (a∗ , c∗ ) by removing the green edge (a∗ , c∗ ) and adding the edges (a∗ , b∗ ) and (c∗ , d∗ ).
In the second step we “match” (a, c) by adding the green edge (a, c) and removing the edges (a, b∗ )
and (c, d∗ ). A switch with the pair (b∗ , d∗ ) can be defined in a similar manner.
a

a

c
c∗

c
c∗

A switch

a∗

a∗
d∗

d∗

b∗

b∗

Figure 7: An illustration of a switch between the pairs (a∗ , c∗ ) and (a, c).
√
m
. For every t ≤ Q, every query-answer history π of length t − 1 and
Let t < m and let Q = 600
every pair (u, v) we define the following auxiliary graph. The witness nodes are graphs in which
(u, v) is one of the four special pairs. If the pair is a green matched pair then there is an edge in
the auxiliary graph between a witness graph W and a non-witness graph W , if W can be obtained
from W by a single switch between (u, v) and another unmatched pair.
√
m
Lemma 30. For t < 14 m let Q = 600
. For every t ≤ Q, every query-answer history π of length
t − 1 such that π is consistent with G1 and every pair (u, v),
dnw (Aπ,(u,v) )
8
= .
dw (Aπ,(u,v) )
m
Proof. We analyze the case where the pair (u, v) is such that u ∈ A and v ∈ C, as the proof for
the other cases is almost identical. We first prove that dw (Aπ,(u,v) ) ≥ 81 m. A witness graph W
is a graph in which (a, c) is a special pair. That is (u, v) = (a∗ , c∗ ). Potentially, for every pair
(a′ , c′ ) such that a′ ∈ Ai , c′ ∈ Cj and none of the indices i, j, ib∗ , id∗ are equal, the graph resulting
√
from a switch between (a∗ , c∗ ) and (a′ , c′ ) is a non-witness graph. There are m − 2t vertices a′ in
√
A \ (Aib∗ ∪ Aid∗ ) and for each such a′ there are m − 3t vertices c′ in C \ (Cib∗ ∪ Cid∗ ∪ Cia′ )). Since
37

√
√
√
t < 14 m, there are at least ( m − 2t) · ( m − 3t) = m − 6t2 ≥ 41 m potential pairs (a′ , c′ ) that
(a∗ , c∗ ) could be switched with. For the resulting graph to be consistent, that is, to be in G2 (π),
the pair (a′ , c′ ) must be such that the pairs (a′ , c′ ), (a∗ , b∗ ) and (c∗ , d∗ ) have not been observed yet
1
1
by the algorithm. Since the number of queries is at most 600
m, at least 14 m − 125
m ≥ 18 m of the
potential pairs (a′ , c′ ) can be switched with (a∗ , c∗ ) such that the resulting graph is consistent with
G2 (π). Therefore, dw (Aπ,(u,v) ) ≥ 81 m.
Now consider a non-witness graph W . There is only one possibility to turn W into a witness
graph, which is to switch the pair (u, v) with the green pair (a∗ , c∗ ). Therefore, the maximal degree
of every non-witness graph, dnw (Aπ,(u,v) ), is 1.
Together we get that
dnw (Aπ,(u,v) )
8
≤ ,
dw (Aπ,(u,v) )
m
and the proof is complete.
4.4.4

Statistical distance

A similar proof to the ones of Lemma 25 and Lemma 26 using Lemma 30 gives the following
√
lemmas for the case that 1 ≤ t < 14 m.
√
m
. For every t ≤ Q, every query-answer history π of
Lemma 31. Let 1 ≤ t < 41 m and Q = 600
length t − 1 such that π is consistent with G1 and for every all-neighbors query qt ,
PrP2 [at is a witness answer | π, qt ] ≤

16
.
m

√
m
Lemma 32. Let 1 ≤ t < 41 m and Q = 600
. For every t ≤ Q, every query-answer history π of
length t − 1 such that π is consistent with G1 and for every pair or random new-neighbors query qt ,
X

a∈Ans(π,qt )

PrPe1 [a | π, qt ] − PrPe2 [a | π, qt ] =

96
.
m

The next lemma is proven in a similar way to 1.3.4 based on the above two lemma.
√
m
, the statistical
Lemma 33. Let 1 ≤ t < 41 m. For every algorithm ALG that asks at most Q = 600
1
ALG
ALG
is at most 3 .
and D2
distance between D1

4.5

Wrapping things up

Theorem 15 follows from Lemmas 20, 23, 27 and 33, and the next corollary is proved using Theorems
15 and 14.
Corollary 34. Any
algorithm for the number of triangles in a graph
n
 multiplicative-approximation
o
m3/2
n
must perform Ω t(G)1/3 + min m, t(G)
queries, where the allowed queries are degree queries,
pair queries and neighbor queries.
Proof. Assume towards a contradiction that there exists an algorithm ALG’ for which the following
holds:
1. ALG’ is allowed to ask neighbor queries as well as degree queries and pair queries.
2. ALG’ asks Q′ queries.
38

3. ALG’ outputs a (1 ± ǫ)-approximation to the number of triangles of any graph G with probability greater than 2/3.
Using ALG’ we can define an algorithm ALG that is allowed random new-neighbor queries, performs
at most Q = 3Q′ queries and answers correctly with the same probability as ALG’ does. ALG runs
ALG’ and whenever ALG’ performs a query qt′ , ALG does as follows:
• If qt′ is a degree query, ALG performs the same query and sets a′t = at .
• If qt′ is a pair query (u, v), then ALG performs the same query q = q ′ . Let at be the
corresponding answer.
– If at = 0, then ALG sets a′t = at .
– If at = 1, then ALG sets a′t = (at , i, j), such that i and j are randomly chosen labels
that have not been previously used for neighbors of u and v, and are within the ranges
[1..d(u)] and [1..dv ] respectively.
• If qt′ is a neighbor query (u, i), ALG performs a random new-neighbor query qt = u, and
returns the same answer a′t = at .
We note that the above requires the algorithm ALG to store for every vertex v, all the labels used for
its neighbors in the previous steps. Once ALG’ outputs an answer, ALG outputs the same answer.
It follows that ALG performs at most 3Q queries to the graph G. By the third assumption above,
ALG outputs a (1 ± ǫ)-approximation
to the n
number of
otriangles of anygraph G withnprobability
o

3/2
n
m3/2
′
then Q ∈
/ Ω t(G)n1/3 + min m, m
greater than 2/3. If Q ∈
/ Ω t(G)1/3 + min m, t(G)
t(G)
which is a contradiction to Theorem 14 and Theorem 15.

References
[ADNK14]

N. K. Ahmed, N. Duffield, J. Neville, and R. Kompella. Graph sample and hold: A
framework for big graph analytics. In Conference on Knowledge Discovery and Data
Mining (KDD), 2014. 2, 6

[AGM12]

K. J. Ahn, S. Guha, and A. McGregor. Graph sketches: sparsification, spanners, and
subgraphs. In Principles of Database Systems, pages 5–14, 2012. 2, 6

[AKM13]

Shaikh Arifuzzaman, Maleq Khan, and Madhav Marathe. Patric: A parallel algorithm for counting triangles in massive networks. In Proceedings of the 22nd ACM
international conference on Conference on information & knowledge management,
pages 529–538. ACM, 2013. 2, 6

[Avr10]

Haim Avron. Counting triangles in large graphs using randomized matrix trace estimation. In Workshop on Large-scale Data Mining: Theory and Applications, volume 1, 2010. 2, 6

[AYZ97]

Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles.
Algorithmica, 17(3):209–223, 1997. 2, 5

[BBCG08]

Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. Efficient semistreaming algorithms for local triangle counting in massive graphs. In Proceedings of
the 14th ACM SIGKDD international conference on Knowledge discovery and data
mining, pages 16–24. ACM, 2008. 2, 6
39

[BFL+ 06]

Luciana S Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela,
and Christian Sohler. Counting triangles in data streams. In Proceedings of the
twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database
systems, pages 253–262. ACM, 2006. 2, 6

[BHLP11]

J. W. Berry, B. Hendrickson, R. A. LaViolette, and C. A. Phillips. Tolerating the
Community Detection Resolution Limit with Edge Weighting. Physical Review E,
83(5), May 2011. 2

[BPWZ14]

A. Björklund, R. Pagh, V. Vassilevska Williams, and U. Zwick. Listing triangles. In
Proceedings of International Colloquium on Automata, Languages, and Programming
(ICALP), pages 223–234, 2014. 2, 5

[Bur04]

R. S. Burt. Structural holes and good ideas.
110(2):349–399, 2004. 2

[BYKS02]

Ziv Bar-Yossef, Ravi Kumar, and D Sivakumar. Reductions in streaming algorithms,
with an application to counting triangles in graphs. In Proceedings of the Thirteenth
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 623–632. Society for Industrial and Applied Mathematics, 2002. 2, 6

[CC11]

Shumo Chu and James Cheng. Triangle listing in massive networks and its applications. In Proceedings of the 17th ACM SIGKDD international conference on
Knowledge discovery and data mining, pages 672–680. ACM, 2011. 2, 6

[CEF+ 05]

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt
Rubinfeld, and Christian Sohler. Approximating the weight of the euclidean minimum
spanning tree in sublinear time. SIAM Journal on Computing, 35(1):91–109, 2005. 5

[CN85]

Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms.
SIAM Journal on Computing, 14(1):210–223, 1985. 2, 5, 11

[Coh09]

J. Cohen. Graph twiddling in a MapReduce world. Computing in Science & Engineering, 11:29–41, 2009. 6

[Col88]

J. S. Coleman. Social capital in the creation of human capital. American Journal of
Sociology, 94:S95–S120, 1988. 2

[CRT05]

Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum
spanning tree weight in sublinear time. SIAM Journal on Computing, 34(6):1370–
1379, 2005. 5

[CS09]

Artur Czumaj and Christian Sohler. Estimating the weight of metric minimum spanning trees in sublinear time. SIAM Journal on Computing, 39(3):904–922, 2009. 5

[EM02]

J.-P. Eckmann and E. Moses. Curvature of co-links uncovers hidden thematic layers
in the World Wide Web. Proceedings of the National Academy of Sciences (PNAS),
99(9):5825–5829, 2002. 2

[Fei06]

Uriel Feige. On sums of independent random variables with unbounded variance and
estimating the average degree in a graph. SIAM Journal on Computing, 35(4):964–
984, 2006. 3, 5, 7, 11, 15, 16
40

American Journal of Sociology,

[FWVDC10] Brooke Foucault Welles, Anne Van Devender, and Noshir Contractor. Is a friend
a friend?: Investigating the structure of friendship networks in virtual worlds. In
CHI’10 Extended Abstracts on Human Factors in Computing Systems, pages 4027–
4032. ACM, 2010. 2
[GR02]

Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, pages 302–343, 2002. 19

[GR08]

Oded Goldreich and Dana Ron. Approximating average parameters of graphs. Random Structures and Algorithms, 32(4):473–493, 2008. 3, 5

[GRS11]

Mira Gonen, Dana Ron, and Yuval Shavitt. Counting stars and other small subgraphs
in sublinear-time. SIAM Journal on Discrete Math, 25(3):1365–1411, 2011. 2, 5

[HKNO09]

Avinatan Hassidim, Jonathan A Kelner, Huy N Nguyen, and Krzysztof Onak. Local
graph partitions for approximation and testing. In Proceedings of the Fiftieth Annual
Symposium on Foundations of Computer Science (FOCS), pages 22–31. IEEE, 2009.
5

[HL70]

P. W. Holland and S. Leinhardt. A method for detecting structure in sociometric
data. American Journal of Sociology, 76:492–513, 1970. 2

[IR78]

Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM Journal
on Computing, 7(4):413–423, 1978. 2, 5

[JG05]

Hossein Jowhari and Mohammad Ghodsi. New streaming algorithms for counting
triangles in graphs. In Computing and Combinatorics, pages 710–716. Springer, 2005.
2, 6

[JSP13]

M. Jha, C. Seshadhri, and A. Pinar. A space efficient streaming algorithm for triangle
counting using the birthday paradox. In Proceedings of the 19th ACM SIGKDD
international conference on Knowledge discovery and data mining, KDD ’13, pages
589–597, New York, NY, USA, 2013. ACM. 2, 6

[KMPT12]

Mihail N Kolountzakis, Gary L Miller, Richard Peng, and Charalampos E
Tsourakakis. Efficient triangle counting in large graphs via degree-based vertex partitioning. Internet Mathematics, 8(1-2):161–185, 2012. 2, 6

[KMSS12]

D. M. Kane, K. Mehlhorn, T. Sauerwald, and H. Sun. Counting arbitrary subgraphs
in data streams. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 598–609, 2012. 2, 6

[KPP+ 13]

Tamara G. Kolda, Ali Pinar, Todd Plantenga, C. Seshadhri, and Christine Task.
Counting triangles in massive graphs with MapReduce. arXiv:1301.5887, January
2013. 6

[MR09]

Sharon Marko and Dana Ron. Approximating the distance to properties in boundeddegree and general sparse graphs. ACM Transactions on Algorithms, 5(2), 2009.
5

[MSOI+ 02]

Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and
Uri Alon. Network motifs: simple building blocks of complex networks. Science,
298(5594):824–827, 2002. 2
41

[NO08]

Huy N Nguyen and Krzysztof Onak. Constant-time approximation algorithms via
local improvements. In Proceedings of the Forty-Ninth Annual Symposium on Foundations of Computer Science (FOCS), pages 327–336. IEEE, 2008. 5

[ORRR12]

Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. A near-optimal
sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1123–1131. SIAM, 2012. 5

[Por00]

Alejandro Portes. Social capital: Its origins and applications in modern sociology.
LESSER, Eric L. Knowledge and Social Capital. Boston: Butterworth-Heinemann,
pages 43–67, 2000. 2

[PR07]

Michal Parnas and Dana Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science,
381(1-3):183–196, 2007. 5

[PT12]

R. Pagh and C. Tsourakakis. Colorful triangle counting and a mapreduce implementation. Information Processing Letters, 112:277–281, 2012. 6

[PTTW13]

A. Pavan, K. Tangwongsan, S. Tirthapura, and K.-L. Wu. Counting and sampling
triangles from a graph stream. In International Conference on Very Large Databases
(VLDB), 2013. 2, 6

[SKP12]

C. Seshadhri, T. G. Kolda, and A. Pinar. Community structure and scale-free collections of Erdös-Rényi graphs. Physical Review E, 85(5):056109, May 2012. 2

[SPK13]

C. Seshadhri, A. Pinar, and T. G. Kolda. Fast triangle counting through wedge
sampling. In Proceedings of the SIAM Conference on Data Mining, 2013. 2, 6

[SV11]

S. Suri and S. Vassilvitskii. Counting triangles and the curse of the last reducer. In
World Wide Web (WWW), pages 607–614, 2011. 2, 6

[SW05a]

T. Schank and D. Wagner. Approximating clustering coefficient and transitivity.
Journal of Graph Algorithms and Applications, 9:265–275, 2005. 2

[SW05b]

T. Schank and D. Wagner. Finding, counting and listing all triangles in large graphs,
an experimental study. In Experimental and Efficient Algorithms, pages 606–609.
Springer Berlin / Heidelberg, 2005. 2, 6

[TDM+ 09]

Charalampos E Tsourakakis, Petros Drineas, Eirinaios Michelakis, Ioannis Koutis,
and Christos Faloutsos. Spectral counting of triangles in power-law networks
via element-wise sparsification. In Social Network Analysis and Mining, 2009.
ASONAM’09. International Conference on Advances in, pages 66–71. IEEE, 2009.
6

[TKM11]

Charalampos E Tsourakakis, Mihail N Kolountzakis, and Gary L Miller. Triangle
sparsifiers. J. Graph Algorithms Appl., 15(6):703–726, 2011. 2, 6

[TKMF09]

Charalampos E Tsourakakis, U Kang, Gary L Miller, and Christos Faloutsos. Doulion:
counting triangles in massive graphs with a coin. In Proceedings of the 15th ACM
SIGKDD international conference on Knowledge discovery and data mining, pages
837–846. ACM, 2009. 2
42

[TPT13]

K. Tangwongsan, A. Pavan, and S. Tirthapura. Parallel triangle counting in massive
streaming graphs. In ACM Conference on Information & Knowledge Management
(CIKM), 2013. 2, 6

[Tso08]

Charalampos E Tsourakakis. Fast counting of triangles in large real networks without counting: Algorithms and laws. In Data Mining, 2008. ICDM’08. Eighth IEEE
International Conference on, pages 608–617. IEEE, 2008. 2, 6

[YYI09]

Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. An improved constant-time approximation algorithm for maximum. In Proceedings of the Fourty-First Annual ACM
Symposium on the Theory of Computing, pages 225–234. ACM, 2009. 5

43

