ESCAPE: Efficiently Counting All 5-Vertex Subgraphs

Abstract

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 \emph{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.

References in corpus (8)

• Higher-order organization of complex networks
• Multirelational Organization of Large-scale Social Networks in an Online World
• Clustering in Complex Directed Networks
• Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web
• Community structure and scale-free collections of Erdös-Rényi graphs
• Counting Triangles in Massive Graphs with MapReduce
• Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections
• Degree Relations of Triangles in Real-world Networks and Models

Cited by in corpus (8)

• A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets
• Hypergraph Motifs: Concepts, Algorithms, and Discoveries
• The Power of Pivoting for Exact Clique Counting
• Statistical inference for network samples using subgraph counts
• Learning to Count Isomorphisms with Graph Neural Networks
• Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
• DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
• A Fast Counting Method for 6-motifs with Low Connectivity