  Clique and near-clique counts are important graph properties with
applications in graph generation, graph modeling, graph analytics, community
detection among others. They are the archetypal examples of dense subgraphs.
While there are several different definitions of near-cliques, most of them
share the attribute that they are cliques that are missing a small number of
edges. Clique counting is itself considered a challenging problem. Counting
near-cliques is significantly harder more so since the search space for
near-cliques is orders of magnitude larger than that of cliques.
  We give a formulation of a near-clique as a clique that is missing a constant
number of edges. We exploit the fact that a near-clique contains a smaller
clique, and use techniques for clique sampling to count near-cliques. This
method allows us to count near-cliques with 1 or 2 missing edges, in graphs
with tens of millions of edges. To the best of our knowledge, there was no
known efficient method for this problem, and we obtain a 10x - 100x speedup
over existing algorithms for counting near-cliques.
  Our main technique is a space-efficient adaptation of the Tur\'an Shadow
sampling approach, recently introduced by Jain and Seshadhri (WWW 2017). This
approach constructs a large recursion tree (called the Tur\'an Shadow) that
represents cliques in a graph. We design a novel algorithm that builds an
estimator for near-cliques, using an online, compact construction of the
Tur\'an Shadow.
