On Approximating the Number of k-cliques in Sublinear Time

arXiv:1707.04858v2 [cs.DS] 12 Mar 2018

Talya Eden

∗

Dana Ron

†

C. Seshadhri

‡

Abstract
We study the problem of approximating the number of k-cliques in a graph when given
query access to the graph. We consider the standard query model for general graphs via (1)
degree queries, (2) neighbor queries and (3) pair queries. Let n denote the number of vertices
in the graph, m the number of edges, and Ck the number of k-cliques. We design an algorithm
that outputs a (1 + ǫ)-approximation
 (with high probability) for Ck , whose expected query
complexity and running time are O

n

1/k
Ck

+

mk/2
Ck

poly(log n, 1/ǫ, k). Hence, the complexity of

the algorithm is sublinear in the size of the graph for Ck = ω(mk/2−1 ). Furthermore, the query
complexity of our algorithm is essentially optimal (up to the dependence on log n, 1/ǫ and k).
The previous results in this vein are by Feige (SICOMP 06) and by Goldreich and Ron (RSA
08) for edge counting (k = 2) and by Eden et al. (FOCS 2015) for triangle counting (k = 3).
Our result matches the complexities of these results.
The previous result by Eden et al. hinges on a certain amortization technique that works
for triangle counting, and does not generalize to all k. We obtain a general algorithm that
works for any k ≥ 3 by designing a procedure that samples each k-clique incident to a given
set S of vertices with approximately equal probability. The primary difficulty is in finding
cliques incident to purely high-degree vertices, since random sampling within neighbors has a
low success probability. This is achieved by an algorithm that samples uniform random high
degree vertices and a careful tradeoff between estimating cliques incident purely to high-degree
vertices and those that include a low-degree vertex.

∗

Tel Aviv University, talyaa01@gmail.com. This research was partially supported by a grant from the Blavatnik
fund. The author is grateful to the Azrieli Foundation for the award of an Azrieli Fellowship.
†
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, sesh@ucsc.edu

1

Introduction

Counting the number of k-cliques in a graph is a classic problem in theoretical computer science,
and the special case of k = 3 (triangle counting) is itself an important problem. In practice, clique
counting has received much attention due to its significance for analyzing real-world graphs [HL70,
Col88, Por00, EM02, MSOI+ 02, Bur04, BBCG08, FVC10, BHLP11, SKP12, JRBT12, ELS13,
Tso15, FFF15]. From a theoretical standpoint, the best exact algorithms use matrix multiplication [NP85, EG04]. Better bounds for sparse graphs can be obtained by combinatorial methods [CN85, Vas09].
There is a long line of algorithms for approximately counting the number of cliques (especially triangles) in various computational models, including distributed and streaming settings
[CN85, SW05b, SW05a, JG05, Tso08, TKMF09, Avr10, KMPT12, CC11, SV11, TKM11, AGM12,
KMSS12, SPK13, TPT13]. All these algorithms begin by reading their entire input graph, and
hence must run in at least linear time. Recently, Eden et al. [ELRS15] gave the first sublinear-time
algorithm for triangle counting. The query model used is the standard model for sublinear algorithms on general graphs (refer to Chapter 10 of Goldreich’s book [Gol17]). We assume that the
vertex set is V = [n]. Algorithms can make the following queries. (1) Degree queries: given v ∈ V ,
get the degree d(v). (2) Neighbor queries, given v ∈ V and i ≤ d(v) get the ith neighbor of v. (3)
Pair queries: given vertices u, v, determine if (u, v) is an edge.
We show that there is a sublinear-time algorithm for approximating the number of k-cliques in
this model, for any given k, subsuming the result of [ELRS15] for k = 3.

1.1

Results

Let G = (V, E) be a graph over n vertices and m edges, where we view edges as ordered pairs, so
that m equals the sum of the degrees of all vertices. Let Ck denote that number of cliques of size
k in G.
Our main theorem follows.
Theorem 1. There exists an algorithm that, given n, k, an approximation parameter 0 < ǫ < 1,
bk , such that with high constant probability
and query access to a graph G, outputs an estimate C
(over the randomness of the algorithm),
bk ≤ (1 + ǫ) · Ck .
(1 − ǫ) · Ck ≤ C

The expected query complexity of the algorithm is
)!
(
mk/2
n
,m
· poly(log n, 1/ǫ, k) ,
+ min
O
1/k
Ck
Ck


k/2
n
+ mCk · poly(log n, 1/ǫ, k).
and the expected running time is O 1/k
Ck

Below we state a nearly matching lower bound. The lower bound was first given in an earlier
version of this paper [ERS17a], and a simplified proof is given in [ER17].
Theorem 2 ([ERS17a, ER17]). The query complexity of any multiplicative-approximation algorithm for Ck is
(
)!
mk/2
n
+ min
,m
,
Ω
1/k
Ck · (c · k)k
Ck

for a (small) constant c.
1

1.2

Main ideas and techniques

In all that follows, a random vertex refers to a vertex selected uniformly at random. Our starting point for approximating the number of k-cliques is similar to that of Eden et al. [ELRS15]
(henceforth ELRS) for approximating the number of triangles (i.e., k = 3). However, we diverge
rather quickly, as the heart of our algorithm, a process for sampling k-cliques, is conceptually and
technically different. For the sake of simplicity, assume ǫ is a constant. Also, it is convenient to
assume that constant factor estimates of Ck and m are known.1
The starting point that is shared with ELRS: vertex sampling and clique assignment.
Our algorithm starts by uniformly and independently selecting a (multi-)set S of vertices of size
1/k
roughly n/Ck . Denoting
the number of k-cliques incident to a vertex u by ck (u), a natural
n P
estimate for Ck is k|S|
u∈S ck (u). Unfortunately, for a random u, ck (u) can have extremely large
variance. ELRS reduce the variance by considering triangles only from endpoints u where c3 (u) is
not too large. In our setting, we formalize this by defining “sociable” vertices. A vertex is sociable
if it participates in a number of k-cliques that is above a certain threshold τ or if its degree is
above another threshold τ ′ . A k-clique with vertices {u1 , . . . , uk } is assigned to the smallest degree
vertex uj that is not sociable. We set the parameters τ, τ ′ to ensure that the number of k-cliques
that are not assigned to any vertex is at most ǫ · Ck . Let α(u) be the number of k-cliques assigned
1/k
n P
to u. We can prove that if |S| is roughly n/Ck , then |S|
u∈S α(u) is a (1 + ǫ)-approximation
of Ck with
high
probability.
The
problem
of
approximating
C
k is now reduced to approximating
P
α(S) = u∈S α(u). From this point on the ELRS approach does not generalize (as we explain
towards the end of this section). We continue by describing our approach.
Approximating α(S) : Sampling k -cliques incident to S almost uniformly.
Let
A(S) denote the (multi-)set of k-cliques assigned to vertices in S. We estimate α(S) = |A(S)| by
sampling k-cliques incident to S, and checking whether they belong to A(S). The key is to sample
each k-clique incident to S (and in particular in A(S)) with (approximately) the same probability.
1
Specifically, as explained next, we will do so with probability proportional to m(S)·m
k/2−1 , where
m(S) = |E(S)| and E(S) denotes the (multi-)set of (ordered) edges incident to S.
Each k-clique containing a vertex u ∈ S is associated with one of the edges incident to u in the
clique. For reasons that will become clear shortly, the other endpoint of this edge is selected to be
the lowest degree vertex among the vertices in the clique (excluding u, and breaking ties arbitrarily
but consistently). The procedure for sampling k-cliques starts by sampling an edge (u, v) uniformly
in E(S). It then attempts to extend this edge to a k-clique, where the other k − 2 vertices have
degree higher than v. This is done in one of two different ways, depending on the degree of v, where
in either way, the algorithm may fail to output any k-clique. For the sake of simplicity, in what
√
follows we refer to a vertex as a low-degree vertex if its degree is at most m, and as a high-degree
vertex otherwise. (The technical part of the paper uses a slightly different definition.)
The (easy) “low case”: If v is a low-degree vertex, then we sample k − 2 random neighbors
of v and check whether we obtained a k-clique in which v is the lowest degree vertex other than
u. In order to ensure that all k-cliques incident to S are output with the same probability, we
√
apply rejection sampling and keep each sampled neighbor w of v with probability d(v)/ m (and
conditioned on d(v) ≤ d(w)). Hence, each such clique (i.e., in which the lowest degree vertex other
1
The assumption on m can be removed by applying [Fei06], and the assumption on Ck can be removed by a
geometric search (for details see Subsection 3.7).

2

than u ∈ S is a low-degree vertex) is output with equal probability

(k−2)!
.
√
m(S)· mk−2

(The (k − 2)! factor

is due to the fact that we may obtain the k − 2 vertices in the clique other than u and v in any
order.)

The (hard) “high case”: The challenging case is when v is a high-degree vertex. Rejection
sampling, as in the low case, is too expensive now. However, observe that we are interested only
in sampling neighbors of v with degree higher than v, and that the number of vertices with high
√
degree is at most m. Therefore, if we had a way to efficiently sample each high-degree vertex with
√
probability (approximately) 1/ m, we would obtain the same probability over cliques incident to
S as in the low case. We next explain how this can be done.
n√
vertices. The setting of t is
Consider selecting a random multi-set T of roughly t = log n/
m
such that with high probability, for every high-degree vertex w, the number of neighbors that w
has in T is close to its expected value, that is, d(w) · nt . This implies that if we select an edge (x, y)
uniformly at random in E(T ) (the (ordered) edges incident to T , whose number is m(T )), then the
probability that y = w for a fixed high-degree vertex w, is approximately d(w)·(t/n)
m(T ) .
t
Assume that m(T ) is not much larger than its expected value, m · n (which can be ensured with
m(T )
√ , so that under this assumption on m(T ), and the fact
high probability). Let p(w) = d(w)·(t/n)·
m
that w is a high-degree vertex, p ∈ (0, 1]. If we now keep w with probability p(w), then we have a
√
subroutine that samples each high-degree vertex with approximately equal probability 1/ m. This
in turn implies that we can select any fixed subset of k − 2 high-degree vertices with probability
very close to √(k−2)!
k−2 . We then check whether whether the chosen vertices form a clique together
m

with u and v (and that the clique is associated with (u, v)).
We now have a procedure that outputs each clique incident to S with (roughly) the same
(k−2)!
probability,
√ k−2 . In the next paragraph, we discuss a procedure for deciding whether a
m(S)· m

k-clique
belongs to A(S).
 Given this decision procedure, we can estimate |A(S)| by performing
√
m(S)·(2 m)k−2
mk/2
calls to the k-clique sampling procedure. (We assume that |A(S)| is close
Ck
(k−2)!·|A(S)| = O
to its expected value, Ck · ns and that m(S) is not much larger than its expected value, m · ns ).
Deciding whether a k -clique is in A(S) . Deciding whether a k-clique incident to a vertex
u ∈ S should be assigned to u, requires to determine which of the clique vertices are sociable. Recall
that a vertex is considered sociable if the number of k-cliques it participates in is more than τ or
if its degree is above τ ′ (for appropriate settings of τ and τ ′ ). The second condition can be easily
verified by a single degree query. As for the first condition, given a vertex u, we verify whether
the number of k-cliques that it participates in is more than τ by running
the k-clique
sampling
√
√
τ ′ ·(2 m)k−2
d(u)·(2 m)k−2
≤ (k−2)!·τ where
procedure with S = {u} for a sufficient number of times (roughly
(k−2)!·τ
 
′
τ
m
τ = O Ck ). The procedure may err on “almost sociable” vertices, but the analysis can be
modified to deal with this. While the procedure might have high query complexity, it is only
invoked when the clique-sampling procedure returns a clique. The frequency of the latter can be
bounded appropriately to get the final query complexity.
Why the ELRS
algorithm does not generalize. The success of ELRS hinges on the followP
3/2 ), discovered in [CN85] in the context of triangle
ing bound:
(u,v)∈E min(d(u), d(v)) = O(m
enumeration. The short answer to why the ELRS algorithm does not generalize is that the above
bound does not have analogues for k > 3. Indeed, this is why the simple algorithm of [CN85] for

3

triangle enumeration does not work for cliques of larger size.2
Let us revisit the triangle estimator of ELRS. Recall that in this context, α(u) denotes the
number of triangles assigned to a vertex u, and that the aim is to estimate the average value
of α(u) for u ∈ S. ELRS first “transfer” the assignment of triangles from vertices to edges.
Letting
α(u, v) denote the number of triangles assigned to the edge (u, v) we have that α(S) =
P
(u,v)∈E(S) α(u, v). For a random edge (u, v), a triangle can be detected by sampling a random
neighbor of the lower degree vertex among u and v and performing a pair query with the other
endpoint.
l Since them probability of finding a triangle decreases as min(d(u), d(v)) increases, ELRS
√
random neighbors. Hence, the expected number of queries performed per edge
select min(d(u),d(v))
m
m
l
P
min(d(u),d(v))
1
√
, which by the aforementioned bound from [CN85], is O(1). ELRS
is m
(u,v)∈E
m

prove that in order to estimate α(S), it suffices to sample O(m3/2 /C3 ) random edges from E(S),
and therefore they get the desired bound.
of ELRS to k-cliques would require the following bound:
P A generalization k−2
= O(mk/2 ). This bound is false for k > 4. To exemplify this,
(u,v)∈E min(d(u), d(v))
consider a graph over the vertex set {1, . . . , n}, with the following edges. There is an edge (1, 2),
and both vertices 1 and 2 have an edge to all other vertices. The left-hand-side of the bound is
Θ(nk−2 ), while the right-hand-side is O(nk/2 ). Thus, the ELRS analysis depends on a seeming
singularity for k = 3, 4, and does not generalize to all k.

1.3

Related work

A significant portion of the work on clique counting focuses on triangle counting. Because our
focus is on general k, we avoid a detailed discussion of results for triangle counting. We point the
interested reader to [ELRS15].
Nešetřil and Poljak give the first non-trivial algorithm for k-clique counting by reducing to
matrix multiplication [NP85]. Specifically, their algorithm runs in time O(nω⌊k/3⌋+k(mod3) ), where
ω is the matrix multiplication exponent. Eisenbrand and Grandoni refine this bound for certain
values of k by careful reductions to rectangular matrix multiplication [EG04]. They also give better
dependencies on m for sparse graphs. The general dependence of the form nωk/3 is believed to be
optimal. Recent work by Abboud et al. builds on this conjecture to prove hardness for various
parsing algorithms [ABW15]. More relevant to our work, Chiba and Nishizeki give an algorithm
for k-clique enumeration, based on the arboricity of the graph, from which the O(n + mk/2 ) bound
for general graphs follows immediately. The use of degree/degeneracy orientations have appeared
in recent practical works on clique counting [FFF15, JS17]. In the current work we design various
primitives to sample random k-cliques, by either extending smaller cliques or by sampling high
degree vertices. The idea of extending smaller cliques to large ones using degree orientations is an
important feature of previous practical approaches [FFF15, JS17]. It would be of interest to see if
the new techniques given by our result could be used for practical algorithms.
In the context of sublinear algorithms, our work follows a line of results on sublinear estimation
of subgraph counts. Our analysis builds on several techniques developed in these results. The starting point is the average degree estimation results of Feige [Fei06] and Goldreich and Ron [GR08].
Gonen et al. generalize these techniques to estimate the count of k-stars in sublinear time [GRS11].
Eden et al. [ERS17b] further extended and simplified all these results, and show connections between this problem and the graph degeneracy. They also build on the basic ELRS framework.
Eden and Rosenbaum [ER18] provide an algorithm for sampling edges almost uniformly, and our
2

We note that [CN85] also present a general algorithm for listing k-cliques for any k, but this algorithm and its
analysis are more involved.

4

clique sampler uses some of their ideas to sample high-degree vertices. Dasgupta et al. [DKS14]
and Chierichetti et al. [CDK+ 16] consider sublinear algorithms (for average degree and related
problems) in a weaker model where uniform random vertices are not allowed. In practical settings,
we can only “crawl” a graph, which translates to performing random walks. Their results typically
require some assumption about the mixing time of the input graph G. Again, we believe this is an
interesting direction for future work, to consider weaker query models but stronger assumptions on
graph structure.
Other work on sublinear algorithms for estimating graph parameters (in the standard query
model) include results on the minimum weight spanning tree [CRT05, CS09, CEF+ 05], maximum matching [NO08, YYI09] and minimum vertex cover [PR07, NO08, MR09, YYI09, HKNO09,
ORRR12].

2

Preliminaries

We consider simple undirected graphs over a set V of n vertices. It is convenient to think of the
graph edges as ordered pairs, so that every edge is considered from both endpoints. We say that
the ordered edge (u, v) originates from the vertex u. We denote the set of all ordered edges by E
and let m , |E|. We use the following notations.
P
• d(u): the degree of a vertex u (the number of edges originating from u). Note that u∈V d(u) =
m.
P
• E(S), m(S): E(S) , {(u, v) | u ∈ S} and m(S) , |E(S)| = u∈S d(u).
• dS (u): for any vertex u and set of vertices S, dS (u) is the number of neighbors of u in S.
• Ck , ck (u): Ck is the number of k-cliques in the given
graph. For u ∈ V , ck (u) is the number
1 P
of k-cliques that u participates in. Note that Ck = k · u∈V ck (u).
We use ≺ to denote a total order over the graph vertices such that for every two vertices u and
v, if d(u) < d(v), then u ≺ v, and if d(u) = d(v), then the order between u and v is determined in
an arbitrary but fixed manner (e.g., by vertex id).


Let [r] , {1, . . . , r} and let (1 ± α)t · x denote the interval (1 − α)t · x, (1 + α)t · x .
We make use of the following version of Chernoff’s inequality [Che52]. Let χi for i = 1, . . . , m
be random variables taking values in [0, B], such that for every i, Exp[χi ] = p. Then
"
#
 2

m
1 X
γ µm
Pr
χi > (1 + γ)µ < exp −
,
m
3B
i=1

and

#
 2

m
γ µm
1 X
χi < (1 − γ)µ < exp −
.
Pr
m
2B
"

i=1

The proof of the following claim is similar to the proof of [CN85] for their exact clique enumeration algorithm (and we include it here for the sake of completeness).
Claim 3. For every graph G with m (ordered) edges and Ck k-cliques,
√ 
m
.
Ck ≤ m ·
k−2

Proof. Let D be the DAG obtained by orienting edges in G according to ≺. Let d+ (v) be the
√
out-degree of vertex v in D. Observe that maxv {d+ (v)} ≤ m. (All d+ (v) out-neighbors of v have
√
degree at least d(v) ≥ d+ (v). Thus, d+ (v) ≤ m.) The number of k-cliques
where v is the
lowest
√ 
√ P

P d+ (v)
d+ (v)
m
m
+
vertex according to ≺ is at most k−1 . Thus, Ck ≤ v k−1 ≤ k−2
v d (v) = m k−2 .
5

3

The algorithm

The main algorithm for approximating the number of k-cliques is presented in Subsection 3.2 and
named Approximate-cliques. It takes the following parameters.
• m: This is assumed to be a fairly precise estimate

of the number of (ordered) edges m, and
n
√
can be obtained using [GR08] (in expected time O
· poly(log n, 1/ǫ)).
m

• C k : This is assumed to be a constant-factor estimate of Ck , which is obtained by geometric
search (as shown in Subsection 3.7).
• ǫ: The main approximation parameter. We set ǫ = ǫ/5.
• δ: The failure parameter. We set δ = δ/4.

3.1

Sociable vertices and the assignment of cliques to vertices

The notion of sociable vertices, defined next, is critical in reducing the variance of the output of
our algorithm.
Definition 4 (Sociable and shy vertices). We say that a vertex u is sociable if ck (u) >
k · (50C k )1−1/k /ǫ1/k or if d(u) > 4m/(ǫC k )1/k . If ck (u) ≤ 41 k · (50C k )1−1/k /ǫ1/k and d(u) ≤
4m/(ǫC k )1/k , then we say that u is shy.
Note that a vertex u may be neither sociable nor shy. This is the case if d(u) ≤ 4m/(ǫC k )1/k
and 41 k · (50C k )1−1/k /ǫ1/k < ck (u) ≤ k · (50C k )1−1/k /ǫ1/k .

The following claim, whose proof follows directly from Definition 4, shows that we can ignore
cliques that do not contain shy vertices.
Claim 5. If m ∈ [(1 − ǫ)m, m] and C k > Ck /4, then at most ǫCk k-cliques consist solely of vertices
that are not shy.
Proof. For every vertex u that is not shy, either
1
ck (u) > k · (50C k )1−1/k /ǫ1/k
4
Recall that

P

u∈V

or d(u) > 4m/(ǫC k )1/k .

ck (u) = k · Ck . Therefore, if C k ≥ Ck /4, then there are at most
1
4k

k · Ck
≤ (ǫCk )1/k /2
· (50C k )1−1/k /ǫ1/k

vertices of the former type, and if m ≥ (1 − ǫ)m, then there are at most
m
≤ (ǫCk )1/k /2
4m/(ǫC k )1/k
of the latter type. This implies that there are at most (ǫCk )1/k vertices that are not shy, and it
follows that the number of k-cliques for which all of their vertices are not shy is at most ǫCk .
Definition 6 (An appropriate partition). We say that a partition P = (V0 , V1 ) of V is appropriate
if every shy vertex (as defined in Definition 4) is in V0 and every sociable vertex is in V1 (and any
other vertex can be either in V0 or V1 ).
We next specify the assignment of cliques to vertices.
6

Definition 7 (Assigning cliques). Fix a partition P = (V0 , V1 ).
• Assignment of cliques: We assign each k-clique K = {u1 , . . . , uk } to the vertex ui that is the
first (according to ≺) vertex of K in V0 . If all of K’s vertices are in V1 , then K is not assigned to
any vertex.
• αP (u), αP (S): We denote
P the number of k-cliques assigned to u (for this P ) by αP (u). For
a set S of vertices, αP (S) = u∈S αP (u).
The following is a corollary of Claim 5, Definition 6 and Definition 7.

Corollary 8. For every partition P = (V0 , V1 ) of V it holds that αP (V ) ≤ Ck . Furthermore, if
P = (V0 , V1 ) is appropriate, m ≥ (1 − ǫ)m and C k ≥ Ck /4, then
αP (V ) ∈ [(1 − ǫ)Ck , Ck ] .
Another distinction between types of vertices that will play a central role in our analysis is the
following.
Definition√9 (High-degree and low-degree vertices). We say that a vertex u is a high-degree vertex
if d(u) > 2 m and otherwise we say it is a low-degree vertex.

3.2

The main algorithm and the procedures it uses

In this subsection we present our main algorithm and the corresponding main theorem. Our
algorithm invokes several procedures, which are provided in the following subsections. Here we
shortly describe all procedures and state the main claim regarding each of them. Building on these
claims we give a proof sketch of the main theorem (the complete proof appears in Subsection 3.6).
Approximate-cliques. This is the main algorithm, and it is provided in Figure 1. The algorithm
begins by constructing two random multisets, S and T . The multiset S is obtained by simply
selecting vertices uniformly (independently) at random. The multiset T is constructed by a procedure Sample-degrees-typical. We show that with high probability, S and T have certain desired
properties (where the correctness of subsequent steps of the algorithm relies on these properties).
In Step 5, the algorithm calls two procedures: Sample-a-clique and Is-sociable. The heart of the
algorithm is the procedure Sample-a-clique that either returns a k-clique {u, v, w1 , . . . , wk−2 } where
u ∈ S or returns fail. The procedure Is-sociable distinguishes between sociable and shy vertices
(as defined in Definition 4). It is used in order to decide for each k-clique that is output in the
previous step, whether it is assigned to u (as defined in Definition 7).
Note that if the sample size s (defined in Step 2) is larger than n, then the algorithm can simply
set S = V . Similarly, if q (the number of iterations in Step 5) is larger than m, then the algorithm
can query upfront all edges incident to S and their neighbors so that it never performs more than
min{m, m} queries. (If it views more than m edges, then it can abort.) Finally, we may assume
that ǫ > 1/mk/2 , since otherwise we are required to output the exact number of k-cliques in the
graph (recall that by Claim 3, Ck < mk/2 ), and thus can simply invoke the exact enumeration
algorithm of [CN85].
The main theorem of our paper is the following (where the second item in the theorem is used
by the geometric search algorithm for Ck ).
Theorem 10. Consider an invocation of Algorithm Approximate-cliques(n, k, m, C k , ǫ, δ).

7

Approximate-cliques (n, k, m, C k , ǫ, δ)
1. Let ǫ = ǫ/5 and δ = δ/4.
2. Let S be a multiset of s =

700·k·n·ln(1/δ)
1/k

ǫ 2+1/k ·C k

vertices chosen uniformly at random.

3. Query the degree of each vertex in S and set up a data structure D(S) that
supports sampling a uniform edge in E(S) in constant time.
4. Invoke Sample-degrees-typical(n, k, m, C k , ǫ, δ). If the procedure returned fail,
then return fail. Otherwise,
let (T, m(T ), D(T )) be its output.
√
k−2

10 ln(1/δ)
m(S)·(2 m)
do:
5. For i = 1 to q = (1−ǫ)
3 ·(k−2)!·C ·(s/n) ·
ǫ2
k
(a) Invoke Sample-a-clique(S, T, m(S), m(T ), D(S), D(T ), k, m).
(b) If the procedure returned fail then set χi = 0. Otherwise, let
Ki = (ui , vi , wi,1 , . . . , wi,k−2 ) be the k-tuple returned and do the following.
i. Query the degree and invoke Is-sociable(x, T, m(T ), D(T ), m, C k , n, k, ǫ, δ)
on each vertex x ∈ Ki .
ii. If ui is the first vertex (according to ≺) in Ki for which Is-sociable
returned shy,
then set χi = 1. Otherwise, set χi = 0.
√ k−2
m(S)(2
m)
1 Pq
bk =
6. Return C
i=1 χi .
(k−2)!·(s/n) · q

Figure 1: The main algorithm for computing a (1 ± ǫ)-estimate of the number of k-cliques in a
graph (given a constant factor estimate of this number).
1. If m ∈ [(1 − ǫ)m, m] and C k ∈ [Ck /4, Ck ], then with probability at least 1 − δ,
bk such that
Approximate-cliques returns a value C
bk ∈ (1 ± ǫ) · Ck .
C

2. If m ∈ [(1 − ǫ)m, m] and C k > Ck , then with probability at least ǫ/4, Approximate-cliques
bk such
returns a value C
bk ≤ (1 + ǫ) · Ck .
C

≤ mk/2 , then the expected query
3. If C k 
 complexity and running time of Approximate-cliques
(k−2)/2
max{m,m}·m
Ck
n
are O
·C
· poly(log n, 1/ǫ, log(1/δ), k).3 The number of queries
1/k +
Ck
k
Ck


n
· poly(log n, 1/ǫ, log(1/δ), k) + min{m, m}.
is always upper bounded by O
1/k
Ck

Sample-degrees-typical. This procedure is described in Figure 4. Its goal is to output a degreestypical multiset, which is defined below. The procedure itself is quite simple; it repeats the process
of sampling a uniform random multiset for a sufficient number of times in order to achieve this
condition with high probability.
Definition 11. We say that a multiset T of size t is degrees-typical if m(T ) ≤
high-degree vertex w ∈ V ,


t
ǫ
· · d(w) .
dT (w) ∈ 1 ±
k
n
3

t
n

· 4m and for every

In the second additive term there is actually a dependence on 2k /(k − 2)!, which we ignored for the sake of
simplicity.

8

In Subsection 3.5 we prove the following lemma regarding the correctness and running time of
the procedure Sample-degrees-typical.
Lemma 12. Consider an invocation of Sample-degrees-typical(n, k, m, C k , ǫ, δ). The procedure either returns fail, or returns a multiset T together with m(T ) and a data structure D(T ) that
supports selecting a uniform edge in E(T ) in time O(1).
Let γ = min{1/(4mk/2 ), δ}. If m ∈ [(1 − ǫ)m, m], then with probability at least 1 − γ, the
procedure returns a triple (T, m(T ), D(T )) such thatthe multiset T is degrees-typical.

2
The running time of Sample-degrees-typical is O √nm · k ·log(n/γ)·log(1/γ)
.
ǫ2
Sample-a-clique. As mentioned earlier, this is the most important and novel aspect of our algorithm. Given any multiset of vertices S, the procedure Sample-a-clique produces cliques incident to
S with roughly uniform probability. The procedure is given in Figure 2.
Definition 13. Let C(S) denote the set of k-tuples (u, v, w1 , . . . , wk−2 ) that have the following
properties: (1) the subgraph induced by {u, v, w1 , . . . , wk−2 } is a k-clique; (2) u ∈ S; (3) v ≺ wj for
every j ∈ [k − 2].
By the above definition, each clique containing a vertex u ∈ S is associated with the edge (u, v)
in the clique such that v ≺ w for every other vertex w 6= u in the clique, and the clique has exactly
(k − 2)! corresponding tuples in C(S). In Subsection 3.3 we prove the following lemma regarding
the correctness and running time of the procedure Sample-a-clique.
Lemma 14. Let T be a degrees-typical multiset and let S be any multiset. For any fixed k-tuple
K ∈ C(S), the probability that an invocation of Sample-a-clique(S, T, m(S), m(T ), D(S), D(T ), k, m)
returns K is in (1 ± ǫ) · m(S)·(21√m)k−2 . The running time of Sample-a-clique is O(k2 ).
Is-sociable. This procedure decides if a vertex u is sociable or not. This is done by multiple
independent invocations of Sample-a-clique for the set S = {u}. The procedure is provided in
Figure 3 in Subsection 3.4, where we also prove the following lemma regarding the correctness and
running time of the procedure Is-sociable.
Lemma 15. Let T be a degrees-typical multiset. If Is-sociable(u, T, m(T ), D(T ), m, C k , n, k, ǫ, δ)
is invoked with a sociable vertex u, then with probability at least 1 − δ/n, the procedure returns
sociable, and if u is shy, then with probability at least 1 − δ/n, the procedure returns shy. The
running time of Is-sociable is O

mk/2
Ck

·

k·2k ·log(n/δ)
(k−2)!·ǫ2−1/k

.

Proof sketch of the first item in Theorem 10. The full proof of Theorem 10 appears in
Subsection 3.6. Here we provide a proof sketch for the case that C k ∈ [Ck /4, Ck ], relying on
Lemmas 12–15.
By the first premise of this item, m ∈ [(1 − ǫ)m, m]. Hence, by Lemma 12, with high probability
the multiset T is degrees-typical. From this point on we condition on this event.
Consider (as a thought experiment) invoking Is-sociable on all vertices with the degrees-typical
multiset T . Based on these invocations, we can define a partition Pis = (V0 , V1 ), where V0 contains
all vertices for which Is-sociable returns shy and V1 contains all vertices for which Is-sociable returns
sociable. By Lemma 15 and a union bound over all vertices, we get that with probability at
least 1 − δ, Pis is an appropriate partition (as defined in Definition 6). Conditioned on Pis being
appropriate (and using our assumptions on m and C k ), by Corollary 8 we have that αPis (V ) ∈
[(1 − ǫ)Ck , Ck ].
9

Now consider the selection of the multiset S. We show that the size s of this sample ensures
that with high probability αPis (S) is close to its expected value, ns · αPis (V ), so that αPis (S) ∈
(1±ǫ)2 · ns ·Ck . We condition on this event as well. Since T is degree-typical, by Lemma 14, whenever
we invoke Sample-a-clique (in Step 5a) it returns each k-tuple in C(S) with probability approximately
1√
. Observe that if Sample-a-clique returns a k-tuple Ki = (ui , vi , wi,1 , . . . , wi,k−2 ), then
m(S)·(2 m)k−2
in Steps 5(b)i and 5(b)ii the algorithm determines whether the corresponding k-clique is assigned
(k−2)!·α is (S)
to ui according to Pis and sets χi to 1. Therefore, Pr[χi = 1] is approximately m(S)·(2√Pm)
(recall
k−2
that for each k-clique that a vertex u ∈ S participates in, there are (k − 2)! corresponding k-tuples
in C(S)). By the setting of the number of invocations, q, of Sample-a-clique, with high probability,
the sum of the χi ’s is close to its expected value, and the output of the algorithm is as claimed.

3.3

Sampling a clique

In this subsection we provide the procedure Sample-a-clique and prove Lemma 14. The procedure
first samples a uniform edge (u, v) in E(S). It then tries to construct a k-clique that this edge
participates in by selecting k − 2 additional vertices. More precisely, it tries to construct a k-tuple
(u, v, w1 , . . . , wk−2 ) in C(S). Recall that such a k-tuple satisfies: u ∈ S, {u, v, w1 , . . . , wk−2 } induces
a k-clique, and v ≺ wj for each j ∈ [k − 2]. To this end the procedure repeats the following k − 2
times. If v is a low-degree
√ vertex, then it selects a uniform neighbor w of v, and maintains it
with probability d(v)/2 m. If v is a high-degree vertex, then the procedure tries to sample a
random high-degree vertex. It does so by first sampling a uniform edge (x, y) ∈ E(T ) and if y is
a high-degree neighbor of v, performing rejection sampling according to the degree of y. We prove
that conditioned on T being degrees-typical, we obtain each k-tuple in C(S) with almost equal
probability.
Sample-a-clique (S, T, m(S), m(T ), D(S), D(T ), k, m)
1. Sample a uniform edge e = (u, v) in E(S) (using the data structure D(S)).
2. For j = 1 to k −√2 do:
(a) If d(v) ≤ 2 m (v is a low-degree vertex), then:
i. Uniformly select a neighbor wj of v.
√
√
ii. Keep wj with probability 2d(v)
and with probability 1 − 2d(v)
return
m
m
fail.
(b) Else (v is a high-degree vertex):
i. Sample a random
edge (x, y) in E(T ) (using the data structure D(T )).
√
ii. If d(y) ≤ 2 m, return fail.
)√
iii. With probability d(y)·m(T
set wj = y, otherwise, return fail.
t
·2 m
n

3. For every pair of vertices in {u, v, w1 , . . . , wk−2 } query if there is an edge between
the two vertices.
4. If the subgraph induced by {u, v, w1 , . . . , wk−2 } is a k-clique and v ≺ wj for every
j ∈ [k − 2] then return K = (u, v, w1 , . . . , wk−2 ). Otherwise return fail.
Figure 2: A procedure for sampling a k-clique incident to S with almost uniform probability.
Proof of Lemma 14: Let (a, b, z1 , . . . , zk−2 ) be a k-tuple in C(S). Recall that by the definition
of C(S) we have that a ∈ S, the subgraph induced by {a, b, z1 , . . . , zk−2 } is a k-clique and b ≺
zj for every j ∈ [k − 2]. If Sample-a-clique does not return fail, then its output is a tuple
10

(u, v, w1 , . . . , wk−2 ) in C(S). The probability that the procedure returns the tuple (a, b, z1 , . . . , zk )
is
i
h
Pr (u, v) = (a, b) and ∀j ∈ [k − 2] , wj = zj
h
i
= Pr[(u, v) = (a, b)] · Pr ∀j ∈ [k − 2] , wj = zj | (u, v) = (a, b) .

1
, so it remains to compute the probability that wj = zj for each
Clearly, Pr[(u, v) = (a, b)] = m(S)
j ∈ [k − 2], conditioned on (u, v) = (a, b).
If b = v is a low-degree vertex, then the vertices w1 , . . . , wk−2 are uniformly selected random
neighbors of v. For each j ∈ [k − 2], the probability that wj = zj and thath the procedure did
1
√
· 2d(v)
not return fail due to rejection sampling is d(v)
= 2√1m . Therefore, Pr ∀j ∈ [k − 2] , wj =
m
i
√
zj | (u, v) = (a, b) = 1/(2 m)k−2 .
Otherwise (b is a high-degree vertex), since b ≺ zj for each j ∈ [k − 2], the vertices z1 , . . . , zk−2
are also high-degree vertices. In this case (conditioned on (u, v) = (a, b)), the procedure tries
to sample k − 2 high-degree vertices by sampling edges originating from the vertices of T . We
next prove
that, in Step 2(b)iii, any specific high-degree vertex is sampled with probability in

1 ± kǫ 2√1m .

Since T is degrees-typical (as defined in Definition 11), m(T ) ≤
every high-degree vertex z,

t
n

· 4m. This implies that for

t
m(T )
n · 4m √
√
√
≤
= 1.
d(z) · nt · 2 m
2 m · nt · 2 m

Thus, Step 4 is valid. Since T is degrees-typical, for every high-degree vertex z,


t
ǫ
dT (z) ∈ 1 ±
· · d(z) .
k
n
For any vertex y, the probability of obtaining an edge in Step 2(b)i with y as an endpoint is
dT (y)/m(T ). Therefore, for each j ∈ [k − 2], the probability that wj = zj in Step 4 is


dT (zj )
m(T )
1
ǫ
√ ∈ 1±
·
· √ .
t
m(T ) d(zj ) · n · 2 m
k
2 m
It follows that the probability that the procedure returns any specific k-tuple in C(S) is (1 ± ǫ) ·
1
√
.
m(S)(2 m)k−2
It remains to bound the running time of the procedure. Given the data structure D(S), it takes
time O(1) to sample an edge in E(S), and similarly it takes time O(1) to sample an edge in D(T ).
The procedure samples a single edge in E(S) and possibly k − 2 edges in E(T ). Adding the time
to perform queries on all pairs of vertices in {u, v, w1 , . . . , wk−2 } (in addition to a degree query on
each of these vertices), the total running time is O(k2 ).


3.4

Is-sociable

The procedure Is-sociable determines (with high success probability) whether a given vertex u is
sociable or shy. For vertices that are neither sociable nor shy, it can answer arbitrarily. Recall that
by Definition 4, the distinction between a sociable u and a shy u involves bounds on both d(u) and
11

Is-sociable (u, T, m(T ), D(T ), m, C k , n, k, ǫ, δ)
1. Query the degree of u and if√ d(u) > 4m/(ǫC k )1/k then return sociable.
k−2

15 ln(n/δ)
d(u)·(2 m)
do:
2. For i = 1 to r = (k−2)!·(k·(50C
1−1/k /ǫ1/k ) ·
ǫ2
k)
(a) Invoke Sample-a-clique({u}, T, d(u), m(T ), D({u}), D(T ), k, m).
(b) If a k-tuple (corresponding to a k-clique) was returned, then set χi = 1.
Otherwise (the
procedure returned fail), set χi = 0.
√
d(u)·2 m Pr
· i=1 χi .
3. Let b
ck (u) =
r
1
4. If b
ck (u) ≥ 2 (k · (50C k )1−1/k /ǫ1/k ), then return sociable, otherwise, return shy.

Figure 3: A procedure for determining with high probability whether a given vertex is sociable or
not.
ck (u). These will be critical in bounding the running time of Is-sociable. The procedure basically
invokes Sample-a-clique repeatedly to check if ck (u) is larger than the specified threshold.
P
Proof of Lemma 15: Consider any fixed vertex u. Let χ = 1r ri=1 χi , where χ1 , . . . , χr are
as defined in Step 2b of Is-sociable. Note that S = {u}, m(S) = m({u}) = d(u) and |C(S)| =
C({u}) = (k − 2)! · ck (u). By Lemma 14 and the assumption that T is degrees-typical, Exp[χ] ∈
(k−2)!·c
√ k (u) .
(1 ± ǫ) · d(u)·(2
m)k−2

First consider the case that u is sociable. By Definition 4, either d(u) > 4m/(ǫC k )1/k or
ck (u) ≥ k · (50C k )1−1/k /ǫ1/k (or both). Clearly, if d(u) > 4m/(ǫC k )1/k , then the procedure returns
sociable. Hence, assume that ck (u) ≥ k · (50C k )1−1/k /ǫ1/k . By Chernoff’s inequality and the
setting of
√
15 ln(n/δ)
d(u) · (2 m)k−2
·
r=
1/k
1−1/k
ǫ2
(k − 2)! · (k · (50C k )
/ǫ )
in Step 2 of the procedure,
" r
#

 2
ǫ · Exp[χ] · r
1X
χi < (1 − ǫ) · Exp[χ] < exp −
Pr
r
3
i=1
√


d(u)·(2 m)k−2
k (u)
√
ǫ 2 · (1−ǫ)·(k−2)!·c
· 15 ln(n/δ)
·
k−2
ǫ2
(k−2)!·(k·(50C k )1−1/k /ǫ1/k )
d(u)·(2
m)

< exp −
3
≤

δ
.
n

It follows that if T is typical and u is sociable, then with probability at least 1 − δ/n,
1
· k · (50C k )1−1/k /ǫ1/k ,
2

b
ck (u) ≥ (1 − ǫ)2 · ck (u) ≥

causing the procedure to return sociable.
Now consider the case that u is shy. By Definition 4,
ck (u) ≤

1
· k · (50C k )1−1/k /ǫ1/k ,
4

implying that
Exp[χ] < (1 + ǫ) ·

(k−2)!
4

· (k · (50C k )1−1/k /ǫ1/k )
√
.
d(u) · (2 m)k−2

12

Hence, by Chernoff’s inequality, and by the setting of r,

Pr

"

r

1X
3
χi > ·
r
2
i=1



(1 + ǫ)
· k · (50C k )1−1/k /ǫ1/k
4

#

  (1+ǫ)(k−2)!


< exp 
−

4

·(k·(50C k )1−1/k /ǫ1/k )
√
d(u)·(2 m)k−2

12




· r
 < δ.
 n

Therefore, if T is degrees-typical and u is shy, then with probability at least 1 − δ/n, the algorithm
returns shy.
It remains to bound the running time of the procedure. By Lemma 14, the procedure Sample-a-clique runs in time O(k2 ). Crucially, Sample-a-clique is invoked only if d(u) ≤
4m/(ǫC k )1/k . Since
√
15 ln(n/δ)
d(u) · (2 m)k−2
,
·
r=
1/k
1−1/k
ǫ2
(k − 2)! · (k · (50C k )
/ǫ )
the running time of the procedure is
!
k/2 k · 2k · log(n/δ)

m
O r · k2 = O
·
,
C k (k − 2)! · ǫ2−1/k


as claimed.

3.5

Sampling a degrees-typical set

In this subsection we provide the (simple) procedure Sample-degrees-typical and prove Lemma 12
regarding its correctness and running time. As in the case of the choice of the sample S by
Approximate-cliques, here too if the sample size t is larger than n, then the algorithm can simply
set T = V .
Sample-degrees-typical (n, k, m, C k , ǫ, δ)
1. γ = min{1/(4mk/2 ), δ}.
2. For i = 1 to log(2/γ) do:
(a) Let Ti be a multiset of t =

10n·ln(2n/γ 2 )
√
(ǫ/k)2 ·2 m

vertices chosen uniformly, at random.

(b) Query the degrees of all the vertices in Ti and compute m(Ti ).
3. Let T be the first set Ti such that m(Ti ) ≤ nt · 4m. If no such set exists, then
return fail. Else, set up a data structure D(T ) that supports sampling a
uniform edge in E(T ) in constant time.
4. Return (T, m(T ), D(T )).
Figure 4: The procedure for sampling the multiset T .
Proof of Lemma 12: For each iteration i, consider the selection of the multiset Ti . For any fixed
high-degree vertex u ∈ V and for j = 1, . . . , t, let χj (u) = 1 if the j th vertex in Ti is a neighbor
of u and let χj (u) = 0 otherwise.
By ithe definition of χ1 (u), . . . , χt (u) and the premise of the
h P
√
m
t
1
≥
lemma regarding m, Exp t j=1 χj (u) = d(u)
n
n . By Chernoff’s inequality and the setting

of t =

10n·ln(2n/γ 2 )
√
(ǫ/k)2 ·2 m



in Step 3,


t
X
(ǫ/k)2 · t ·
d(u)
d(u)
ǫ
1
 < 2 exp −
> ·
χj (u) −
Pr 
t
n
k
n
3
j=1

13

d(u)
n

!

<

γ2
.
2n

By taking a union bound over all high-degree vertices, it holds that with probability at least
t
P
1 − γ 2 /2, for every high-degree vertex u ∈ V , dTi (u) =
χj (u) ∈ (1 ± (ǫ/k)) · nt · d(u). By
j=1

taking a union bound over the log(2/γ) sampled multisets Ti , it holds that with probability at least
1 − 12 γ 2 log(2/γ)
 > 1 − γ/2, for each of the multisets Ti and for every high-degree vertex u ∈ V ,
dTi (u) ∈ 1 ± kǫ · nt · d(u) .
We now turn to bounding the probability that none of the multiset Ti satisfies m(Ti ) ≤ nt · 4m.
By the definition of m(·), for every Ti we have that Exp[m(Ti )] = nt · m. By the assumption that
m ∈ [(1 − ǫ)m, m] and by Markov’s inequality, Pr[m(Ti ) > nt · 4m] ≤ Pr[m(Ti ) > nt · 2m] < 12 .
Hence, the probability that m(Ti ) > nt · 4m for every i = 1, . . . , log(2/γ) is at most γ/2.
By combining the two failure probabilities, we get that with probability at least 1 − γ, the
algorithm returns a multiset T that is degrees-typical (as defined in Definition 11).
Finally, by a performing a preprocessing step that takes Θ(t) time it is possible to build a
data structure D(T ) that allow for sampling each vertex u ∈ S with probability proportional to
d(u)/m(T ) (see e.g., [Wal74, Wal77, MTW+ 04]). This in turn implies that, using D(T ), it is
possible to sample a uniform edge in E(T ) in constant time.
The running time of Sample-degrees-typical is


n k2 · log(n/γ) · log(1/γ)
,
O (t · log(1/γ)) = O √ ·
ǫ2
m


and the proof is complete.

3.6

Proof of Theorem 10

In this subsection we prove Theorem 10. We first define the notion of a cliques-typical multiset.
Definition 16. We say that a multiset S of size s is cliques-typical with respect to a partition P if
αP (S) ∈ (1 ± ǫ)2 ·

s
· Ck .
n

We establish a simple claim regarding the multiset S selected by our algorithm (appropriate
partitions are as defined in Definition 6).
Claim 17. Consider the multiset S sampled in Step 2 of Algorithm Approximate-cliques. For any
fixed partition P of V , Exp[αP (S)] ≤ ns · Ck . Furthermore, if P is appropriate, m ≥ (1 − ǫ)m
and C k ∈ [Ck /4, Ck ], then with probability at least 1 − δ (over the choice of S), the multiset S is
cliques-typical.
Proof. Recall that by Definition 7, αP (S) is the number of k-cliques assigned to the vertices of S, and
that by Corollary 8, for every partition P , αP (V ) ≤ Ck . Hence, Exp[αP (S)] = ns · αP (V ) ≤ ns · Ck .
We turn to consider the case that the partition P is appropriate, m ≥ (1 − ǫ)m and C k ∈
[Ck /4, Ck ]. By Corollary 8, αP (V ) ∈ [(1 − ǫ)Ck , Ck ]. By Definition 7, k-cliques are only assigned
to vertices that are not sociable, implying that for every vertex u ∈ V , αP (u) ≤ ck (u) ≤ k ·

(50C k )1−1/k /ǫ1/k . Hence, by the multiplicative Chernoff bound and the setting of s =

Pr

"

700·k·n·ln(1/δ)

#
!
ǫ 2 · αPn(V ) · s
αP (V )
αP (V )
1X
αP (u) −
< 2 exp −
>ǫ·
<δ.
s
n
n
3 · k · (50C k )1−1/k /ǫ1/k
u∈S
14

1/k

ǫ 2+1/k ·C k

,

Therefore, if P is appropriate, m ≥ (1 − ǫ)m and C k ∈ [Ck /4, Ck ], with probability at least 1 − δ,
s
s
αP (S) ∈ (1 ± ǫ) · · αP (V ) ∈ (1 ± ǫ)2 · · Ck ,
n
n
which implies that S is cliques-typical by Definition 16.
3.6.1

The case C k ∈ [Ck /4, Ck ]

We start with the first item in the theorem. Recall that by the first premise of this item, m ∈
[(1 − ǫ)m, m]. By Lemma 12, with probability at least 1 − min{1/(4mk/2 ), δ} ≥ 1 − δ the procedure
Sample-degrees-typical returns a multiset T that is degrees-typical. We henceforth condition on this
event.
Since T is degrees-typical, by Lemma 15, an invocation of the procedure Is-sociable with a shy
vertex u returns shy with probability at least 1 − δ/n, and similarly an invocation with a sociable
vertex u returns sociable with probability at least 1 − δ/n. Consider (as a thought experiment)
running the procedure Is-sociable on all the vertices in the graph, and letting V0 be the set of
vertices for which the procedure returned shy, V1 = V \ V0 and Pis = (V0 , V1 ). Conditioned on the
event that T is degrees-typical, by Lemma 15 and by taking a union bound over all the vertices
in V , with probability at least 1 − δ the partition Pis is appropriate (as defined in Definition 6).
Suppose we fix the random coins used by Is-sociable on all vertices to a setting that indeed induces
an appropriate partition Pis , and assume that all calls made by the algorithm to Is-sociable are
answered consistently with Pis . (The probability that Pis is not appropriate is taken into account
in the total failure probability of the algorithm.) Conditioned on Pis being appropriate (and using
our assumptions on m and C k ), by Corollary 8 we have that αPis (V ) ∈ [(1 − ǫ)Ck , Ck ].
Now consider the multiset S sampled in Step 2 of the algorithm. By Claim 17, with probability
at least 1−δ, S is cliques-typical with respect to Pis . That is, αPis (S) ∈ (1±ǫ)2 · ns ·Ck . We condition
on this event as well. Since T is degree-typical, by Lemma 14, whenever we invoke Sample-a-clique
(in Step 5a) it returns each k-tuple in C(S) with probability in (1 ± ǫ) · m(S)·(21√m)k−2 .
By the description of Steps 5(b)i and 5(b)ii, χi is set to 1 only if the procedure Sample-a-clique
returns a k-tuple K = (u, v, w1 , . . . , wk−2 ) in C(S) that is assigned to u according to Pis . For each
k-clique assigned to a vertex u ∈ S, the number of corresponding k-tuples in C(S) is (k − 2)!.
Therefore, for a cliques-typical multiset S,
Exp[χi ] ∈ (1 ± ǫ) ·

s
· Ck · (k − 2)!
αPis (S) · (k − 2)!
√
√
∈ (1 ± ǫ)3 · n
.
m(S) · (2 m)k−2
m(S) · (2 m)k−2
√

(1)

k−2

10 ln(1/δ)
m(S)·(2 m)
in
By the multiplicative Chernoff bound and by the setting of q = (1−ǫ)
3 ·(k−2)!·C ·(s/n) ·
ǫ2
k
Step 5 of the algorithm,

 2
ǫ · Exp[χ] · q
Pr [|χ − Exp[χ]| > ǫ · Exp[χ]] < 2 exp −
3
√ k−2


3 ·(k−2)!·C · s
(1−ǫ)
10 ln(1/δ)
m(S)·(2
m)
k
·
ǫ2 ·
√ k−2n ·
2
ǫ
(1−ǫ)3 ·(k−2)!·C k ·(s/n)
m(S)·(2 m)


< 2 exp −
 <δ.
3

Therefore, if m ∈ [(1 − ǫ)m, m], C k ∈ [Ck /4, Ck ], T is degrees-typical, Pis is appropriate and S is
cliques-typical, then with probability at least 1 − δ,
χ ∈ (1 ± ǫ)4 ·

s
n

· Ck · (k − 2)!
bk ∈ (1 ± ǫ)4 · Ck ∈ (1 ± ǫ)Ck ,
√
=⇒ C
m(S) · (2 m)k−2
15

where we have used the fact that ǫ = ǫ/5. By taking a union bound over all bad events, Ck ∈
(1 ± ǫ)Ck with probability at least 1 − 4δ > 1 − δ (since δ = δ/4).
3.6.2

The case C k > Ck

We now prove the second item of the theorem. As in the first item, since m ∈ [(1 − ǫ)m, m],
by Lemma 12 with probability at least 1 − min{1/(4mk/2 ), δ} the multiset T is degrees-typical.
Conditioned on T being degrees-typical, an invocation of the procedure Sample-a-clique returns
each k-tuple in C(S) with probability in (1 ± ǫ) m(S)·(21√m)k−2 .
In this case, since C k > Ck , the setting of r in the procedure Is-sociable is not sufficiently
large to ensure that the procedure is accurate, and that the partition Pis is appropriate (with high
probability). Similarly, αPis (S) might not be close to its expected value. Therefore, we only use an
upper bound on the expected value of αPis (S), as explained next.
Consider the following random variables. For a multiset S and for each i ∈ [q] let χi (S) denote
the random variable√ χi conditioned on S (where q and χi are as defined in Step 5 of the algorithm).
k−2
bk (S) denote the value of the random variable C
bk (which
Let Yi (S) = m(S)·(2 m)
· χi (S), and let C
(k−2)!(s/n)

is the output of the algorithm), conditioned on S. We use the notation S-c to denote the random
bk in Step 6,
coins of the procedure Sample-a-clique. By the above discussion and by the setting of C
if T is degrees-typical, then
h
ii
h
h i
bk (S)
bk = ExpS ExpS-c C
Exp C
##
"
"
√
q
m(S) · (2 m)k−2 1 X
= ExpS ExpS-c
χi (S)
·
(k − 2)! · ns
q
i=1
" q
"
##
X
1
= ExpS ExpS-c
Yi (S)
q
i=1

= ExpS [ExpS-c [Y1 (S)]] .

(2)

The last equality holds simply because all the Yi (S) variables are equally distributed (for each
fixed S). We note that q also depends on S (since it is a function of m(S)), but this does not
effect our analysis, and hence this dependence is not explicit. As in the analysis of the case that
C k ∈ [Ck /4, Ck ], since for each k-clique assigned to a vertex u ∈ S, the number of corresponding
k-tuples in C(S) is (k − 2)!, we have that if T is degrees-typical, then
Pr[χi (S) = 1] ≤ (1 + ǫ) ·

αPis (S) · (k − 2)!
√
.
m(S) · (2 m)k−2

By the definition of the Yi (S) variables and Equation (2), it follows that


h i
bk ≤ ExpS (1 + ǫ) · αPis (S) = (1 + ǫ) · n · ExpS [αP (S)] .
Exp C
is
s/n
s

17, for any partition P , Exp[αP (S)] ≤ ns · Ck . Therefore, if T is degrees-typical, then
By
h Claim
i
bk ≤ (1 + ǫ)Ck . Finally, by Markov’s inequality (and recalling that ǫ = ǫ/5),
Exp C
h
i
bk > (1 + ǫ/2)(1 + ǫ)Ck < 1 − ǫ/2 .
Pr C
16

As noted in Subsection 3.2, we can assume that ǫ ≥ 1/mk/2 . Since T is not degrees-typical with
probability at most min{1/mk/2 , δ}, by taking a union bound and by the setting of ǫ = ǫ/5, it
holds that with probability at least ǫ/2 − min{1/(4mk/2 ), δ} > ǫ/4, the algorithm returns a value
bk such that C
bk ≤ (1 + ǫ/2)(1 + ǫ)Ck ≤ (1 + ǫ)Ck .
C
3.6.3

The expected query complexity and running time

By Lemma 12 and the assumption
that C k ≤ mk/2 , the invocation of the procedure


2
k ·log(n/γ)·log(1/γ)
n
k/2 , 1/δ} . The
time,
for
γ
=
Θ
min{1/m
Sample-degrees-typical takes O
2
1/k ·
ǫ
Ck


ln(1/δ)
k·n
. By
sampling of S and the computation of m(S) and D(S) take time O (s) = O
1/k · ǫ 2+1/k
Ck

Lemma 14, each invocation of Sample-a-clique in Step 5a takes time O(k2 ), and Step 5(b)ii takes
constant time. Therefore, excludingthe invocations of the Is-sociable procedure, the running time
s
of the for loop in Step 5 is O k2 · q . Since Exp[m(S)]
 = n · m and by the
 setting of q, it follows
2

(k−2)/2

·ln(1/δ)
that the expected running time of the for loop is O m·mC
· k(k−2)!·ǫ
. It remains to bound
2
k
the running time resulting from the invocations of the procedure Is-sociable.
We first bound the expected number of invocations of Is-sociable when the multiset T is degreestypical. Let I denote the number of invocations of Is-sociable. Similarly to the analysis of the case
C k > Ck , let zi (S) be a 0/1 random variable that is defined as follows: zi (S) = 1 if (and only
if) the procedure Sample-a-clique returned a clique in the ith step of the for loop in Step 5a of the
algorithm, conditioned on the set S. As before, let S-c denote the random coins of Sample-a-clique.
Here it is actually relevant that q depends on S, and therefore we use the notation q(S). By the
definition of I,



q(S)
X
zi (S) = ExpS [q(S) · ExpS-c [z1 (S)]] = ExpS [ExpS-c [q(S) · z1 (S)]] .
Exp[I] = ExpS ExpS-c 
i=1

Recall that if T is degrees-typical, then by Lemma 14, an invocation of Sample-a-clique returns each
k-tuple in C(S) with probability in (1 ± ǫ) · m(S)·(21√m)k−2 . Hence,
Pr S-c [zi (S) = 1] ≤ (1 + ǫ)

|C(S)|
√
.
m(S) · (2 m)k−2

By the setting of q(S),
ExpS-c [q(S) · z1 (S)] ≤

(1 + ǫ)|C(S)|
(1 − ǫ)3 · (k − 2)! · C k ·

s
n

·

10 ln(1/δ)
.
ǫ2

Ck 50k ln(1/δ)
Since Exp[|C(S)|] = ns ·(k−2)!·k·Ck , it follows that Exp[I] ≤ C
·
. Therefore, by Lemma 15,
ǫ2
k
if T is degrees-typical, then
the
expected
running
time
resulting
from
all
of the invocations of the
 k/2

Ck k 2 ·2k ·log(n/δ) log(1/δ)
m
Is-sociable procedure is O C · C ·
.
(k−2)!·ǫ2−1/k
k
k
If T is not degrees-typical then we can no longer upper bound the success probability of
Sample-a-clique, implying that the number of invocations of Is-sociable can be Θ(q). However,
1
, this does not affect the expected
since T is not degrees typical with probability at most mk/2
running time resulting from the invocations of Is-sociable. The remaining steps take constant time,

17

and therefore the total running time of the algorithm is
O

n
1/k

Ck

k2 · log(n/γ) · log(1/γ) min{m, m} · m(k−2)/2 Ck k2 · 2k · log(n/δ) log(1/δ)
·
·
·
+
ǫ2+1/k
Ck
Ck
(k − 2)! · ǫ 2−1/k

!

which is

!
max{m, m} · m(k−2)/2 Ck
+
O
·
· poly(log n, 1/ǫ, log(1/δ), k),
1/k
Ck
Ck
Ck

since γ = Θ min{1/mk , δ} .
Finally, as discussed in the beginning of Subsection 3.2, if q is greater than m then the algorithm
may query beforehand for all the edges incident to S and their neighbors, and if it views

 more
n

than m edges then it can abort. Hence, the number of queries is always bounded by O

n
1/k
Ck

·

poly(log n, 1/ǫ, k) + min{m, m} .

3.7

The search algorithm

In this subsection we describe an algorithm that returns an estimate of the number of k-cliques in
a graph G without prior knowledge on the number of edges or k-cliques in the graph. We prove
this by establishing a more general claim:

−
→
Theorem 18. Let A v, ǫ, δ, V be an algorithm that is given parameters v, ǫ, δ and possibly an
→
−
additional set of parameters denoted V , for which the following holds.
1. If v ∈ [v/4, v], then with probability at least 1 − δ, A returns a value vb such that vb ∈ (1 ± ǫ)v.

2. If v > v, then A returns a value vb, such that with probability at least ǫ/4, vb ≤ (1 + ǫ)v.
 
−
→
, is monotonically non3. The expected running time of A, denoted Ert A v, ǫ, δ, V
 
 
−
→
−
→
increasing with v and furthermore, if v < v, then Ert A v, ǫ, δ, V
·
≤ Ert A v, ǫ, δ, V
(v/v)ℓ for some constant ℓ > 0.

4. The maximal running time of A is D.
Then there exists an algorithm A′ that, when given an upper bound B on v, a parameter ǫ and a
→
−
set of parameters V , returns a value X such that the following holds.
−
→
1. A′ (B, ǫ, V ) returns a value X such that X ∈ (1 ± ǫ)v with probability at least 4/5.
 

−
→
−
→
· poly(log B, 1/ǫ, ℓ) for δ =
2. The expected running time of A′ B, ǫ, V is Ert A v, ǫ, δ, V


Θ 2ℓ (ℓ+logǫ log(B)) .
3. The maximal running time of A′ is D · poly(log B, 1/ǫ, ℓ).

The algorithm A′ referred to by the theorem is provided in Figure 5. We note that the algorithm
and the proof of Theorem 18 are a direct generalization of the search algorithm Estimate and the
proof of Theorem 12 in [ELRS15]. However, this generalization may be useful as a “black box” in
future work. We assume that ǫ ≤ 1/4, since otherwise we can simply set ǫ to 1/4.
The following definition will be useful in the proof of the theorem.
18

→
−
A′ (A, B, ǫ, V )
1. Let ve = B.
2. Let δ′ = 1/(5 · 2ℓ ).
3. While ve ≥ 1 do:
(a) For v = B, B/2, . . . , ve do:
i. Let r = (4/ǫ) · ln(2 log 2 (B)/δ′ ) and let δ = δ′ /(2r).
minimum value returned over r invocations of
ii. Let Xv be the
−
→
A v, ǫ, δ, V .
iii. If Xv ≥ (1 + ǫ)v then return v.
(b) Let ve = ve/2.
4. Return fail.
Figure 5: The search algorithm.

Definition 19. We say that a value X is a good estimate of v if X ∈ (1 ± ǫ)v.
Proof of Theorem 18: Our search algorithm has two nested loops running with decreasing values
of “guesses” for the value of v. The outer loop runs with ve, which is our current guess for the value
of v, and the purpose of the inner for loop is to enhance the success probability of the algorithm
when ve ”passes” the good guess of v and runs with values smaller than v/4. We provide the full
details subsequently, and start by considering only the outer while loop. Namely, imagine for now
that instead of the for loop in Step 3a, we have the command “Let v = ve” and the rest of the
algorithm is as described in Figure 5.
2 in the properties of
First consider iterations of the while loop for which ve > v. By Item 
−
→
Algorithm A, for values ve such that ve > v, the probability that A v, ǫ, δ, V returns a value such
that vb > (1 + ǫ)v is at most 1 − ǫ/4. Hence, the probability that the minimum value returned over r
2
′
invocations, that is, Xve, satisfies Xve > (1 + ǫ)v, is at most (1 − ǫ/4)r = (1 − ǫ/4)(4/ǫ)·ln(2 log (B)/δ ) <
′
δ′
. It follows that for each value ve > v, with probability at least 1 − 2 logδ2 (B) ,
2 log2 (B)
Xve < (1 + ǫ)v < (1 + ǫ)e
v.

′

This implies that for each value ve > v, with probability at least 1 − 2 logδ2 (B) , the algorithm A′ will
continue to run with ve = ve/2.
Now consider values of ve such that ve ∈ [v/4, v]. By Item
1 in 
the properties of Algorithm A,

−
→
′
if ve ∈ [v/4, v], then with probability at least 1 − δ , A v, ǫ, δ, V returns a value vb, such that
vb ∈ (1 ± ǫ)v. By the setting δ = δ′ /(2r), and by taking a union bound, with probability at least
1 − δ′ /2, all the r invocations return a good estimate of v, implying that Xve ∈ (1 ± ǫ)v (i.e., Xve is
a good estimate of v. Note that in such a case,
Xve ≥ (1 − ǫ)v ≥ (1 − ǫ) · 2e
v ≥ (1 + ǫ)e
v.
(Here we have used the assumption that ǫ ≤ 1/4.) Hence, once A′ reaches a value ve ∈ [v/4, v/2],
with probability at least 1 − δ′ /2, it returns a value Xve that is a good estimate of v.
Finally, if A′ reaches values v < v/4, we no longer have a guarantee on the probability that A
returns a value vb or on the quality of the estimate b
v . Hence, we also have an inner for loop so that
whenever we halve the guess ve we first run with all the values B, . . . , ve. This ensures that even if
19

the algorithm did not return a value when running with a good guess ve ∈ [v/4, v/2], we can still
bound the probability that it will continue to run with decreasing values of ve.
We now consider the original algorithm with both the outer while loop and the inner for loop
as described in Figure 5. There are at most log(B) invocations of the while loop with values ve > v,
implying that there are at most log2 (B) invocations of the for loop in Step 3(a)i with a value v > v.
Therefore, by the above analysis, the probability that A′ returns a value that is not a good estimate
of v in these invocations is at most δ′ /2. Hence, with probability at least 1 − δ′ /2 we will reach an
invocation in which ve ∈ [v/4, v/2] and v ∈ [v/4, v/2], for which with probability at least 1 − δ′ /2
the algorithm A returns a value Xv that is a good estimate of v. By taking a union bound and by
the setting of δ′ , the algorithm A′ returns a value that is a good estimate of v with probability at
least 1 − δ′ > 4/5.
We turn to analyze the running
time of A′ . 
By Item 3, for
values of v such that v ≥ v,

−
→
−
→
the expected running time of A v, ǫ, δ, V is Ert A v, ǫ, δ, V
. By the above analysis, once

A′ reaches a value ve < v/4, since we run with all values v = B, . . . , ve, the probability that the
algorithm will halve the guess to ve = ve/2 is at most δ′ . Hence, the probability of invoking A with
a value v = v/2z is at most (δ′ )z . By Item 3 in
the properties
A, when running
  of Algorithm
−
→
−
→
with values v < v, it holds that Ert A v, ǫ, δ, V
· (v/v)ℓ . Therefore, the
≤ Ert A v, ǫ, δ, V
expected running time of A′ is upper bounded by

log B
 
 
−
→
−
→ X ′ z ℓ·z
(δ ) · 2 · Ert A v, ǫ, δ, V
+
log2 (B) · r · Ert A v, ǫ, δ, V
z=1

 
−
→
· poly(log B, 1/ǫ, ℓ) ,
= Ert A v, ǫ, δ, V

where the first term is due to the invocations in which v ≥ v and the second is due to invocations in
which v < v, and the equality is due to the setting of δ′ < 1/2ℓ . Therefore, Item 2 of the theorem

holds. The proof of Item 3 is immediate.
The following is a corollary of Theorem 10 and Theorem 18 and is a restatement of Theorem 1.
Corollary 20. There exists an algorithm that, given n, k ≥ 3, and query access to a graph G,
returns a value X suchthat X ∈ (1 ± ǫ)C
 k with probability at least 2/3. The expected running time
k/2

m
n
of the algorithm is O
· poly(log n, 1/ǫ, k), and its expected query complexity is
1/k + C ·(k−2)!
k
Ck


n
o
n
mk/2
O
,
m
· poly(log n, 1/ǫ, k) .
1/k + min
Ck ·(k−2)!
Ck

Proof. We start by obtaining an estimate m of m such that with probability at least 1 −
min{1/n, 1/mk/2 } it holds that m ∈ [(1 − ǫ/4)m, m]. This can be done by invoking the algorithm
of Goldreich and Ron [GR08] for estimating the number of edges Θ(log(n2k )) times and taking
−
→
the median value returned. Next we invoke A′ (Approximate-cliques, B = min{nk , mk/2 }, ǫ, V ) with
→
−
V = (n, k, m) and return the value X returned by A′ .
By Theorem 10, if m ∈ [(1−ǫ/5)m, m], then Approximate-cliques satisfies the conditions required
from Algorithm A in Theorem 18, with ℓ = 2 and D = n + mk/2 (since this is the maximal running
time when C k = 1). Hence, by Theorem 18 and by the union bound, A′ returns a value X such
that with probability at least 4/5 − 1/mk > 2/3, it holds that X ∈ (1 ± ǫ)Ck .
By [GR08], the first step of approximating

the number of edges m with success probability
n
k
at least 1 − min{1/n, 1/m } takes time O √m · poly(log n, 1/ǫ, k) which by Claim 3 is at most
20

O



n
1/k

Ck



· poly(log n, 1/ǫ, k). When m ∈ [1 − (ǫ/5)m, m], by Item 3 in Theorem 10, and by Item 2

in the properties of Algorithm A′ , the expected running time f the algorithm is
!
mk/2
n
· poly (log n, 1/ǫ, k) .
+
O
1/k
Ck
C
k

Since m ∈
/ [(1 − ǫ/5)m, m] with probability at most min{1/n, 1/mk/2 } and the maximal running
time of Approximate-cliques is at most n + mk/2 up to poly(log n, 1/ǫ, k) factors, this event does not
effect the expected query complexity.


By Item 3 in Theorem 10, Algorithm Approximate-cliques never performs more than O

n
1/k
Ck

·

poly(log n, 1/ǫ, log(1/δ), k) + min{m, m} queries. It follows that the expected query complexity is
)!
(
n
mk/2
O
,m
· poly (log n, 1/ǫ, k) ,
+ min
1/k
Ck
C
k

as claimed.

References
[ABW15]

A. Abboud, A. Backurs, and V. V. Williams. If the current clique algorithms are
optimal, so is valiant’s parser. In Proceedings of the Symposium on Foundations of
Computer Science (FOCS), pages 98–117, 2015.

[AGM12]

K. J. Ahn, S. Guha, and A. McGregor. Graph sketches: sparsification, spanners,
and subgraphs. In Proceedings of the Symposium on Principles of Database Systems
(PODS), pages 5–14, 2012.

[Avr10]

H. Avron. Counting triangles in large graphs using randomized matrix trace estimation. In Workshop on Large-scale Data Mining: Theory and Applications (LDMTA),
volume 10, pages 10–9, 2010.

[BBCG08] L. Becchetti, P. Boldi, C. Castillo, and A. Gionis. Efficient semi-streaming algorithms
for local triangle counting in massive graphs. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (SIGKDD), pages 16–24, 2008.
[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):056119, May 2011.

[Bur04]

R. S. Burt. Structural holes and good ideas. American Journal of Sociology, 110(2):349–
399, 2004. URL: http://www.jstor.org/stable/10.1086/421787.

[CC11]

S. Chu and J. Cheng. Triangle listing in massive networks and its applications. In
Proceedings of the International Conference on Knowledge Discovery and Data Mining
(SIGKDD), pages 672–680, 2011.

[CDK+ 16] F. Chierichetti, A. Dasgupta, R. Kumar, S. Lattanzi, and T. Sarlos. On sampling
nodes in a network. In Conference on the World Wide Web (WWW), pages 471–481,
2016.
21

[CEF+ 05]

A. Czumaj, F. Ergün, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, and C. Sohler.
Approximating the weight of the Euclidean minimum spanning tree in sublinear time.
SIAM Journal on Computing, 35(1):91–109, 2005.

[Che52]

H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the
sum of observations. The Annals of Mathematical Statistics, pages 493–507, 1952.

[CN85]

N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal
on Computing, 14(1):210–223, 1985.

[Col88]

J. S. Coleman. Social capital in the creation of human capital. American Journal of
Sociology, 94:S95–S120, 1988. URL: http://www.jstor.org/stable/2780243.

[CRT05]

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

[CS09]

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

[DKS14]

A. Dasgupta, R. Kumar, and T. Sarlos. On estimating the average degree. In Conference on the World Wide Web (WWW), pages 795–806. ACM, 2014.

[EG04]

F. Eisenbrand and F. Grandoni. On the complexity of fixed parameter clique and
dominating set. Theoretical Computer Science, 326(1-3):57–67, 2004.

[ELRS15]

T. Eden, A. Levi, D. Ron, and C Seshadhri. Approximately counting triangles in
sublinear time. In Proceedings of the Symposium on Foundations of Computer Science
(FOCS), pages 614–633, 2015.

[ELS13]

D. Eppstein, M. Löffler, and D. Strash. Listing all maximal cliques in large sparse
real-world graphs. ACM Journal of Experimental Algorithmics, 18:3–1, 2013. URL:
http://doi.acm.org/10.1145/2543629, doi:10.1145/2543629.

[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, 99(9):5825–
5829, 2002. doi:10.1073/pnas.032093399.

[ER17]

T. Eden and W. Rosenbaum.
Lower bounds for approximating graph parameters via communication complexity. CoRR, abs/1709.04262, 2017. URL:
http://arxiv.org/abs/1709.04262, arXiv:1709.04262.

[ER18]

T. Eden and W. Rosenbaum. On sampling edges almost uniformly. In 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA,
USA, pages 7:1–7:9, 2018. URL: https://doi.org/10.4230/OASIcs.SOSA.2018.7,
doi:10.4230/OASIcs.SOSA.2018.7.

[ERS17a]

T. Eden, D. Ron, and C. Seshadhri.
On approximating the number
of k-cliques in sublinear time.
CoRR, abs/1707.04858v1, 2017.
URL:
http://arxiv.org/abs/1707.04858v1, arXiv:1707.04858v1.

[ERS17b]

Talya Eden, Dana Ron, and C. Seshadhri.
Sublinear time estimation of degree distribution moments:
The degeneracy connection.
In

22

44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 7:1–
7:13,
2017.
URL:
https://doi.org/10.4230/LIPIcs.ICALP.2017.7,
doi:10.4230/LIPIcs.ICALP.2017.7.
[Fei06]

U. 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.

[FFF15]

I. Finocchi, M. Finocchi, and E. G. Fusco. Clique counting in mapreduce: Algorithms
and experiments. ACM Journal of Experimental Algorithmics, 20:1–7, 2015. URL:
http://doi.acm.org/10.1145/2794080, doi:10.1145/2794080.

[FVC10]

B. Foucault Welles, A. Van Devender, and N. Contractor. Is a friend a friend?: Investigating the structure of friendship networks in virtual worlds. In CHI Extended
Abstracts on Human Factors in Computing Systems, pages 4027–4032, 2010.

[Gol17]

Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017.

[GR08]

O. Goldreich and D. Ron. Approximating average parameters of graphs. Random
Structures and Algorithms, 32(4):473–493, 2008.

[GRS11]

M. Gonen, D. Ron, and Y. Shavitt. Counting stars and other small subgraphs in
sublinear-time. SIAM Journal on Discrete Mathematics, 25(3):1365–1411, 2011.

[HKNO09] A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak. Local graph partitions for approximation and testing. In Proceedings of the Symposium on Foundations of Computer
Science (FOCS), pages 22–31, 2009.
[HL70]

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

[JG05]

H. Jowhari and M. Ghodsi. New streaming algorithms for counting triangles in graphs.
In Proceedings of the International Conference Computing and Combinatorics (COCOON), pages 710–716. Springer, 2005.

[JRBT12]

M. O. Jackson, T. Rodriguez-Barraquer, and X. Tan. Social capital and social quilts:
Network patterns of favor exchange. American Economic Review, 102(5):1857?1897,
2012.

[JS17]

S. Jain and C. Seshadhri. A fast and provable method for estimating clique counts
using turán’s theorem. In Conference on the World Wide Web (WWW), pages 441–
449, 2017.

[KMPT12] M. N. Kolountzakis, G. L. Miller, R. Peng, and C. E. Tsourakakis. Efficient triangle
counting in large graphs via degree-based vertex partitioning. Internet Mathematics,
8(1-2):161–185, 2012.
[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.

23

[MR09]

S. Marko and D. Ron. Approximating the distance to properties in bounded-degree
and general sparse graphs. ACM Transactions on Algorithms, 5(2):22, 2009.

[MSOI+ 02] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network
motifs: simple building blocks of complex networks. Science, 298(5594):824–827, 2002.
[MTW+ 04] G. Marsaglia, W. W. Tsang, J. Wang, et al. Fast generation of discrete random
variables. Journal of Statistical Software, 11(3):1–11, 2004.
[NO08]

H. N. Nguyen and K. Onak. Constant-time approximation algorithms via local improvements. In Proceedings of the Symposium on Foundations of Computer Science
(FOCS), pages 327–336, 2008.

[NP85]

J. Neštřil and S. Poljak. On the complexity of the subgraph problem. Commentationes
Mathematicae Universitatis Carolinae, 26(2):415–419, 1985.

[ORRR12] K. Onak, D. Ron, M. Rosen, and R. Rubinfeld. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the Symposium on Discrete Algorithms (SODA), pages 1123–1131, 2012.
[Por00]

Alejandro Portes.
Social capital:
Its origins and applications in modern sociology.
In Eric L. Lesser, editor, Knowledge and Social Capital, pages 43 – 67. Butterworth-Heinemann, Boston, 2000.
URL:
http://www.sciencedirect.com/science/article/pii/B9780750672221500064,
doi:https://doi.org/10.1016/B978-0-7506-7222-1.50006-4.

[PR07]

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

[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.
doi:10.1103/PhysRevE.85.056109.

[SPK13]

C. Seshadhri, A. Pinar, and T. G. Kolda. Fast triangle counting through wedge sampling. In Proceedings of the International Conference on Data Mining (ICDM), volume 4, page 5, 2013. URL: http://arxiv.org/abs/1202.5230.

[SV11]

S. Suri and S. Vassilvitskii. Counting triangles and the curse of the last reducer. In Proceedings of the International Conference on World Wide Web (WWW),
pages 607–614, 2011.
URL: http://doi.acm.org/10.1145/1963405.1963491,
doi:10.1145/1963405.1963491.

[SW05a]

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

[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. 2005.

[TKM11]

C. E. Tsourakakis, M. N. Kolountzakis, and G. L. Miller. Triangle sparsifiers. Journal
of Graph Algorithms and Applications, 15(6):703–726, 2011.

24

[TKMF09] C. E. Tsourakakis, U. Kang, G.L. Miller, and C. Faloutsos. Doulion: counting triangles
in massive graphs with a coin. In Proceedings of the International Conference on
Knowledge Discovery and Data Mining (SIGKDD), pages 837–846, 2009.
[TPT13]

K. Tangwongsan, A. Pavan, and S. Tirthapura. Parallel triangle counting in massive
streaming graphs. In Proceedings of the International Conference on Information and
Knowledge Management (CIKM), pages 781–786. ACM, 2013.

[Tso08]

C. E. Tsourakakis. Fast counting of triangles in large real networks without counting:
Algorithms and laws. In International Conference on Data Mining (ICDM), pages
608–617, 2008.

[Tso15]

C. E. Tsourakakis. The k-clique densest subgraph problem. In Proceedings of the
International Conference on World Wide Web (WWW), pages 1122–1132, 2015. URL:
http://doi.acm.org/10.1145/2736277.2741098, doi:10.1145/2736277.2741098.

[Vas09]

V. Vassilevska. Efficient algorithms for clique problems. Information Processing Letters,
109(4):254–257, 2009.

[Wal74]

A. J. Walker. New fast method for generating discrete random numbers with arbitrary
frequency distributions. Electronics Letters, 10(8):127–128, 1974.

[Wal77]

A. J. Walker. An efficient method for generating discrete random variables with general
distributions. ACM Transactions on Mathematical Software, 3(3):253–256, 1977.

[YYI09]

Y. Yoshida, M. Yamamoto, and H. Ito. An improved constant-time approximation
algorithm for maximum. In Proceedings of the Symposium on Theory of Computing
(STOC), pages 225–234, 2009.

25

