# Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2014.

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

- [Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching](https://mlsanity.com/paper/2112.08764/) (2021)
- [Representation Learning for Frequent Subgraph Mining](https://mlsanity.com/paper/2402.14367/) (2024)
- [DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting](https://mlsanity.com/paper/2308.08198/) (2023)
- [LLMTM: Benchmarking and Optimizing LLMs for Temporal Motif Analysis in Dynamic Graphs](https://mlsanity.com/paper/2512.22266/) (2025)
- [Randomized Algorithms for Scientific Computing (RASC)](https://mlsanity.com/paper/2104.11079/) (2021)
- [Towards Subgraph Isomorphism Counting with Graph Kernels](https://mlsanity.com/paper/2405.07497/) (2024)
- [Multi-order Graph Clustering with Adaptive Node-level Weight Learning](https://mlsanity.com/paper/2405.12183/) (2024)
- [GCN-MPPR: Enhancing the Propagation of Message Passing Neural Networks via Motif-Based Personalized PageRank](https://mlsanity.com/paper/2602.07903/) (2026)

## Abstract (arXiv)

Counting the frequency of small subgraphs is a fundamental technique in network analysis across various domains, most notably in bioinformatics and social networks. The special case of triangle counting has received much attention. Getting results for 4-vertex patterns is highly challenging, and there are few practical results known that can scale to massive sizes. Indeed, even a highly tuned enumeration code takes more than a day on a graph with millions of edges. Most previous work that runs for truly massive graphs employ clusters and massive parallelization. We provide a sampling algorithm that provably and accurately approximates the frequencies of all 4-vertex pattern subgraphs. Our algorithm is based on a novel technique of 3-path sampling and a special pruning scheme to decrease the variance in estimates. We provide theoretical proofs for the accuracy of our algorithm, and give formal bounds for the error and confidence of our estimates. We perform a detailed empirical study and show that our algorithm provides estimates within 1% relative error for all subpatterns (over a large class of test graphs), while being orders of magnitude faster than enumeration and other sampling based algorithms. Our algorithm takes less than a minute (on a single commodity machine) to process an Orkut social network with 300 million edges.