# A General Framework for Estimating Graphlet Statistics via Random Walk

arXiv: https://arxiv.org/abs/1603.07504 · HTML: https://mlsanity.com/paper/1603.07504/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Mar 2016.

## Built on by (most cited first, 10 of 10)

- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [Going Deeper into Permutation-Sensitive Graph Neural Networks](https://mlsanity.com/paper/2205.14368/) (2022)
- [Agent-based Graph Neural Networks](https://mlsanity.com/paper/2206.11010/) (2022)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)
- [Representation Learning for Frequent Subgraph Mining](https://mlsanity.com/paper/2402.14367/) (2024)
- [Reinforcement Learning Enhanced Weighted Sampling for Accurate Subgraph Counting on Fully Dynamic Graph Streams](https://mlsanity.com/paper/2211.06793/) (2022)
- [Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index](https://mlsanity.com/paper/2609.26199/) (2026)

## Abstract (arXiv)

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.