# ESCAPE: Efficiently Counting All 5-Vertex Subgraphs

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

## Key facts

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

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

- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [Learning to Count Isomorphisms with Graph Neural Networks](https://mlsanity.com/paper/2302.03266/) (2023)
- [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)
- [Subgraph Frequency Distribution Estimation using Graph Neural Networks](https://mlsanity.com/paper/2207.06684/) (2022)
- [BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs](https://mlsanity.com/paper/2504.10948/) (2025)

## 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 or 5-vertex patterns is highly challenging, and there are few practical results known that can scale to massive sizes. We introduce an algorithmic framework that can be adopted to count any small pattern in a graph and apply this framework to compute exact counts for all 5-vertex subgraphs. Our framework is built on cutting a pattern into smaller ones, and using counts of smaller patterns to get larger counts. Furthermore, we exploit degree orientations of the graph to reduce runtimes even further. These methods avoid the combinatorial explosion that typical subgraph counting algorithms face. We prove that it suffices to enumerate only four specific subgraphs (three of them have less than 5 vertices) to exactly count all 5-vertex patterns. We perform extensive empirical experiments on a variety of real-world graphs. We are able to compute counts of graphs with tens of millions of edges in minutes on a commodity machine. To the best of our knowledge, this is the first practical algorithm for 5-vertex pattern counting that runs at this scale. A stepping stone to our main algorithm is a fast method for counting all 4-vertex patterns. This algorithm is typically ten times faster than the state of the art 4-vertex counters.