  Graphlets are induced subgraph patterns and have been frequently applied to
characterize the local topology structures of graphs across various domains,
e.g., online social networks (OSNs) and biological networks. Discovering and
computing graphlet statistics are highly challenging. First, the massive size
of real-world graphs makes the exact computation of graphlets extremely
expensive. Secondly, the graph topology may not be readily available so one has
to resort to web crawling using the available application programming
interfaces (APIs). In this work, we propose a general and novel framework to
estimate graphlet statistics of "any size". Our framework is based on
collecting samples through consecutive steps of random walks. We derive an
analytical bound on the sample size (via the Chernoff-Hoeffding technique) to
guarantee the convergence of our unbiased estimator. To further improve the
accuracy, we introduce two novel optimization techniques to reduce the lower
bound on the sample size. Experimental evaluations demonstrate that our methods
outperform the state-of-the-art method up to an order of magnitude both in
terms of accuracy and time cost.
