  Given query access to an undirected graph $G$, we consider the problem of
computing a $(1\pm\epsilon)$-approximation of the number of $k$-cliques in $G$.
The standard query model for general graphs allows for degree queries, neighbor
queries, and pair queries. Let $n$ be the number of vertices, $m$ be the number
of edges, and $n_k$ be the number of $k$-cliques. Previous work by Eden, Ron
and Seshadhri (STOC 2018) gives an $O^*(\frac{n}{n^{1/k}_k} +
\frac{m^{k/2}}{n_k})$-time algorithm for this problem (we use $O^*(\cdot)$ to
suppress $\poly(\log n, 1/\epsilon, k^k)$ dependencies). Moreover, this bound
is nearly optimal when the expression is sublinear in the size of the graph.
  Our motivation is to circumvent this lower bound, by parameterizing the
complexity in terms of \emph{graph arboricity}. The arboricity of $G$ is a
measure for the graph density "everywhere". We design an algorithm for the
class of graphs with arboricity at most $\alpha$, whose running time is
$O^*(\min\{\frac{n\alpha^{k-1}}{n_k},\, \frac{n}{n_k^{1/k}}+\frac{m
\alpha^{k-2}}{n_k} \})$. We also prove a nearly matching lower bound. For all
graphs, the arboricity is $O(\sqrt m)$, so this bound subsumes all previous
results on sublinear clique approximation.
  As a special case of interest, consider minor-closed families of graphs,
which have constant arboricity. Our result implies that for any minor-closed
family of graphs, there is a $(1\pm\epsilon)$-approximation algorithm for $n_k$
that has running time $O^*(\frac{n}{n_k})$. Such a bound was not known even for
the special (classic) case of triangle counting in planar graphs.

Data Structures and Algorithms