  Clique counts reveal important properties about the structure of massive
graphs, especially social networks. The simple setting of just 3-cliques
(triangles) has received much attention from the research community. For larger
cliques (even, say 6-cliques) the problem quickly becomes intractable because
of combinatorial explosion. Most methods used for triangle counting do not
scale for large cliques, and existing algorithms require massive parallelism to
be feasible.
  We present a new randomized algorithm that provably approximates the number
of k-cliques, for any constant k. The key insight is the use of (strengthenings
of) the classic Tur\'an's theorem: this claims that if the edge density of a
graph is sufficiently high, the k-clique density must be non-trivial. We define
a combinatorial structure called a Tur\'an shadow, the construction of which
leads to fast algorithms for clique counting.
  We design a practical heuristic, called TUR\'AN-SHADOW, based on this
theoretical algorithm, and test it on a large class of test graphs. In all
cases,TUR\'AN-SHADOW has less than 2% error, in a fraction of the time used by
well-tuned exact algorithms. We do detailed comparisons with a range of other
sampling algorithms, and find that TUR\'AN-SHADOW is generally much faster and
more accurate. For example, TUR\'AN-SHADOW estimates all cliques numbers up to
size 10 in social network with over a hundred million edges. This is done in
less than three hours on a single commodity machine.
