PaperlayerView exact revision on arXiv

Source-linked AI summary

ESCAPE: Efficiently Counting All 5-Vertex Subgraphs

Ali Pinar, C. Seshadhri, V. Vishal

arXiv:1610.09411v1cs.SIcs.DS

TL;DR

Exact counting of 4- and 5-vertex subgraphs is difficult because direct enumeration faces combinatorial explosion and existing scalable methods are limited. ESCAPE cuts patterns into smaller subpatterns and exploits degree orientations to compute exact counts with minimal enumeration. It handles graphs with tens of millions of edges in minutes and substantially accelerates 4-vertex counting.

  • Problem

    Exact, scalable counting of all subgraphs up to five vertices remains difficult because pattern occurrences can reach billions to trillions and direct enumeration becomes impractical.

  • Method

    ESCAPE formalizes cutting patterns into smaller subpatterns, enumerates only a small subset, and uses degree-style orientations to reduce counting costs.

  • Results

    More than 500 times faster than PGD on the 234M-edge orkut graph, while exact 5-vertex counts take under 5 minutes for tech-ip with 21.6M edges.

  • Takeaways & Limitations

    ESCAPE makes exact counting of 5-vertex patterns practical on graphs with tens of millions of edges and provides a graph-mining tool for studying pattern trends.

Abstract

from arXiv · show

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.

V. Vishal ONU Technology

The section is represented by keywords naming motif analysis, subgraph counting, and graph orientations.

  • Motif analysis is identified as a topic.
  • Subgraph counting is identified as a topic.
  • Graph orientations are identified as a topic.

1. INTRODUCTION

The paper targets exact counting of all connected subgraphs up to five vertices, addressing scalability limits caused by combinatorial explosion. ESCAPE combines cutting-based counting with graph orientations and achieves practical runtimes on large graphs, including minutes for 5-vertex patterns and substantial speedups for 4-vertex counting.

  • 1. INTRODUCTION: Small-subgraph frequencies support network analysis, model evaluation, network summarization, and vertex-role classification.
  • 1. INTRODUCTION: The central challenge is combinatorial explosion: 5-vertex pattern counts can reach billions to trillions, making direct enumeration impractical.
  • 1.1 The problem: ESCAPE exactly counts all connected subgraphs up to five vertices, covering 21 connected patterns and also all 3- and 4-vertex patterns.
  • 1.2 Summary of our contributions: ESCAPE computes all 5-vertex counts on a 22M-edge router graph in under 5 minutes on a commodity machine.
  • 1.2 Summary of our contributions: ESCAPE formalizes cutting patterns into smaller subpatterns, requiring exhaustive enumeration of only a small subset to derive all 5-vertex counts.
  • 1.2 Summary of our contributions: Degree-style edge orientations extend orientation techniques beyond triangles, enabling feasible 5-vertex counting and faster 4-vertex counting.
  • 1.2 Summary of our contributions: ESCAPE is significantly faster than PGD for 4-vertex counting, by factors reaching thousands in some instances.

2. PRELIMINARIES

The problem uses an undirected simple graph and seeks induced and non-induced counts for patterns up to five vertices. The method relies on connected-pattern counts, adjacency-list edge queries, degree orientations, and selected local pattern counts.

  • 2.1 Formal description of the problem: The input is an undirected simple graph G=(V,E) with n vertices and m edges.
  • 2.1 Formal description of the problem: A subgraph selects a subset of edges, whereas an induced subgraph includes all edges among a selected vertex subset.
  • 2.1 Formal description of the problem: Counts are sought for induced and non-induced patterns up to size five, with disconnected counts derived from connected patterns by combinatorics.
  • 2.1 Formal description of the problem: Induced counts Ci are the primary target, while non-induced counts Ni are related through a simple invertible linear transformation.
  • 2.2 Notation: The graph is stored as adjacency-list hash tables so edge queries take constant time.
  • 2.2 Notation: Edges are oriented by degree ordering, breaking equal-degree ties by vertex id to form the degree-ordered DAG G→.
  • 2.2 Notation: The notation includes total, per-vertex, and per-edge counts, such as T(G), T(i), and T(e) for triangles.

3. MAIN THEOREMS

The paper gives exact-counting algorithms for connected 4- and 5-vertex patterns, with runtimes expressed through oriented subgraph counts. Inclusion-exclusion then extends connected counts to all k-vertex patterns, while the main text focuses on connected patterns.

  • Despite many possible subgraphs, the algorithms enumerate only a small, carefully chosen set and enumerate those patterns with minimal overhead.
  • The framework counts all connected 4-vertex patterns exactly in O(W++(G→) + W+−(G→) + DD(G→) + m + n) time and O(n + m) storage.
  • The framework counts all connected 5-vertex patterns exactly in O(W(G) + D(G) + DP(G→) + DBP(G→) + m + n) time and O(n + m + T(G)) storage.
  • Counts for all disconnected k-vertex patterns can be determined in constant time from counts of all connected patterns of sizes at most k.
  • The main body focuses on connected patterns because the proof and discussion of the disconnected-pattern theorem are placed in the appendix.

4. MAIN IDEAS

ESCAPE addresses the combinatorial explosion of explicit subgraph enumeration by cutting patterns into smaller fragments and orienting the graph to reduce search. These ideas make larger-pattern counts computable from smaller enumerations and local counts.

  • Graphs with millions of edges can contain billions or trillions of 5-vertex patterns, making explicit enumeration impractical.The tech-as-skitter graph has 11M edges but 2 trillion 5-cycles.
  • A cut set disconnects a pattern, allowing it to be represented through smaller induced fragments around the cut.For a pattern H, removing the cut set produces components whose unions with the cut set form smaller graphs Hi.
  • Counting uses occurrences of fragments incident to each cut vertex or edge together with counts of smaller patterns.The framework turns these quantities into polynomial formulas that can be evaluated with suitable data structures.
  • A degree orientation converts the undirected graph into a DAG and searches for non-isomorphic directed versions of patterns.The directed search is combined with pattern cutting so smaller patterns are enumerated with reduced combinatorial search.

5. THE CUTTING FRAMEWORK

The cutting framework counts a target pattern by combining fragment extensions of a partial match and correcting overlaps through shrinkages. Labeled counts are normalized by automorphisms to obtain unlabeled frequencies.

  • A match is an induced subgraph of G exactly isomorphic to H, while a partial match injectively maps only part of H.
  • The H-degree of a partial match σ is the number of H matches extending σ.
  • C-fragments are the subgraphs induced by a non-trivial cut set C together with each connected component created by removing C.
  • Disjoint extensions of all fragments combine into a copy of H; intersecting extensions instead produce a shrinkage H′.
  • The main lemma derives the count of H from fragment degrees for every partial match and counts of every possible shrinkage.
  • For 5-vertex patterns, fragments usually attach to a vertex or edge and have at most four vertices, enabling their enumeration from smaller-pattern counts.
  • Unlabeled frequency is obtained by dividing labeled match(H) by |Aut(H)|.This removes multiple labeled matches representing the same unlabeled pattern.

6. COUNTING 4-VERTEX PATTERNS

The 4-vertex algorithms combine oriented wedge and triangle enumeration with the cutting framework to count cycles and cliques efficiently. Their runtime supports per-vertex, per-edge, and per-triangle pattern counts.

  • All acyclic orientations of the 4-cycle are used to organize cycle counting under the degree ordering.The highest-ranked vertex and its opposite endpoint classify wedges into directed types.
  • 4-cycle counting on an edge examines wedges involving that edge and matches directed wedge types across the opposite endpoint.The method subtracts the original wedge through a −1 correction term.
  • Four-clique counting enumerates directed diamonds and checks each for the missing edge that would complete a clique.Every four-clique contains exactly one directed diamond, enabling enumeration proportional to the number of directed diamonds.
  • Theorem 8 computes per-vertex, per-edge, and per-triangle counts for triangles, 4-cycles, and 4-cliques in O(W++ + W+− + DD + m) time and O(T) additional space.
  • The framework combines oriented triangle counts with directed wedge enumeration to obtain all 4-vertex counts beyond 4-cycles and 4-cliques in linear time.

7. ONTO 5-VERTEX COUNTS

ESCAPE extends its cutting framework to count 5-vertex patterns, including the difficult 5-cycle and 5-clique, using directed structures and efficiently computed intermediate counts.

  • Cutting framework: The framework generates formulas for all 5-vertex patterns except the 5-cycle and 5-clique by cutting patterns at vertices, edges, triangles, or wedges.The formulas use TT(G) for tailed-triangle counts and derive larger-pattern counts from smaller structures.
  • Cutting framework: Theorem 13 computes the counts from Theorems 9–11 in O(W(G) + D(G) + n + m) time using O(n + m + T(G)) storage.The component counts require O(n), O(m), and O(T) time, while N13 can be counted by enumerating wedges.
  • The 5-cycle and 5-clique: For 5-cycles, ESCAPE sums products of directed 3-path counts and wedge counts, then subtracts directed tailed-triangles counted by the product.The two possible 5-cycle DAGs share a directed three-path and an outwedge or inout-wedge between the cut vertices.
  • The 5-cycle and 5-clique: Five-cliques are counted by enumerating directed bipyramids, because every 5-clique contains one, in O(DBP(G) + D(G) + T(G) + n + m) time.Triangle-incidence lists from Theorem 8 support the enumeration of directed bipyramids with limited overhead.
  • The 5-cycle and 5-clique: Combining Theorems 8, 13, 14, and 15 yields exact counting of all connected 5-vertex patterns in O(W(G) + D(G) + DP(G→) + DBP(G→) + m + n) time.The resulting storage complexity is O(n + m + T(G)).

8. EXPERIMENTAL RESULTS

ESCAPE exactly counts 5-vertex patterns at practical scale and substantially accelerates 4-vertex counting. Experiments also examine runtime predictability and structural trends in real-world graphs.

  • 4-vertex pattern counting: More than 500× speedup over PGD is achieved on the 234M-edge orkut graph for 4-vertex pattern counting.ESCAPE also took 21.79 seconds on the 11.1M-edge asskitter graph.
  • 5-vertex Pattern Counting: Less than 5 minutes suffices to compute all 5-patterns for tech-ip, with 2.25M nodes and 21.6M edges.The authors report no other known method handles even such medium-sized graphs for this problem.
  • Runtime Predictions: Runtime is accurately predicted from counts of the base patterns identified in Theorem 2.The fitted model uses W(G), D(G), DP(G→), and DBP(G→), excluding m and n.
  • Trends in pattern counts: Patterns 16–20 are extremely rarely induced across the evaluated graphs, while pattern 1 frequently remains induced despite six potential missing edges.The authors suggest these distributions may support edge prediction and reveal structures beyond 3- and 4-vertex patterns.
  • Trends in pattern counts: Three common neighbors significantly increase the likelihood of an edge, especially in social networks.The comparison uses transitivity involving three versus two common neighbors.
  • Trends in pattern counts: Pattern 18 is more than twice as likely as pattern 19 to acquire an additional edge and become pattern 20.The two patterns have the same number of edges; the result is presented in Figure 9.

A. DISCONNECTED PATTERNS

Disconnected pattern counts can be derived from connected pattern counts through inclusion-exclusion and related constant-time transformations. This extends the counting framework to all k-vertex patterns, including disconnected ones.

  • A. DISCONNECTED PATTERNS: Counts for all disconnected k-vertex patterns can be determined in constant time once all connected patterns of sizes at most k are known.The additional time depends only on k.
  • A. DISCONNECTED PATTERNS: The proof partitions matches of a pattern with multiple components into component-wise injective maps and corrects overlaps using one-step inclusion-exclusion.Each component map contributes its pattern’s match count, while non-injective global maps are handled separately.
  • A. DISCONNECTED PATTERNS: Overlapping component maps correspond to matches of patterns formed by merging vertex subsets across components.These merged patterns have fewer connected components, enabling induction.
  • B. CONVERSION BETWEEN INDUCED AND NONINDUCED COUNTS: Induced and non-induced 5-pattern counts are mutually convertible through an invertible linear transformation.The relation is N = AC, with induced counts recovered as C = A^-1N.

C. DETAILED INDUCED COUNTS

The paper reports detailed induced counts for connected 4- and 5-vertex patterns, including all 5-vertex patterns across tables and runtime measurements for patterns 13–21.

  • C. DETAILED INDUCED COUNTS: Figures 12 and 13 provide matrices converting induced 5-vertex counts to non-induced counts and back.The matrices correspond to the transformations described for C and N.
  • C. DETAILED INDUCED COUNTS: Table 2 reports induced counts for various 4- and 5-vertex patterns across graphs.It also includes all connected 4-patterns and selected 3-vertex patterns relevant to the algorithms.
  • C. DETAILED INDUCED COUNTS: Tables 3 and 4 report induced counts for all connected 5-vertex patterns.Table 3 covers patterns 1–12, while Table 4 covers patterns 13–21 and runtimes in seconds.
Loading 1610.09411v1…