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

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. Get-ting results for 4-vertex patterns is highly challenging, and there are few practical results known that can scale to mas-sive 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 em-ploy clusters and massive parallelization. We provide a sampling algorithm that provably and accu-rately 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 decreas