GraphPi: High Performance Graph Pattern Matching through Effective Redundancy Elimination

Tianhui Shi, Mingshu Zhai, Yi Xu, Jidong Zhai

Abstract

Graph pattern matching, which aims to discover structural patterns in graphs, is considered one of the most fundamental graph mining problems in many real applications. Despite previous efforts, existing systems face two main challenges. First, inherent symmetry existing in patterns can introduce a large amount of redundant computation. Second, different matching orders for a pattern have significant performance differences and are quite hard to predict. When these factors are mixed, this problem becomes extremely complicated. High efficient pattern matching remains an open problem currently. To address these challenges, we propose GraphPi, a high performance distributed pattern matching system. GraphPi utilizes a new algorithm based on 2-cycles in group theory to generate multiple sets of asymmetric restrictions, where each set can eliminate redundant computation completely. We further design an accurate performance model to determine the optimal matching order and asymmetric restriction set for efficient pattern matching. We evaluate GraphPi on Tianhe-2A supercomputer. Results show that GraphPi outperforms the state-ofthe-art system, by up to 105X for 6 real-world graph datasets on a single node. We also scale GraphPi to 1,024 computing nodes (24,576 cores).

Introduction

Graph pattern matching—the task of finding all instances of a template graph within a larger data graph—is essential for fields like social network analysis, bioinformatics, and fraud detection. However, the problem is computationally intensive due to two primary factors: symmetry and search scheduling.

Symmetry, or automorphisms, occurs when a pattern can be mapped to the same physical subgraph in multiple ways. For example, a square pattern has multiple symmetries; a naive search would find and process the same subgraph eight times. This redundancy significantly inflates the search space and wastes computational resources.

Illustration of graph pattern matching and redundant automorphic embeddings.

Furthermore, the "schedule"—the order in which vertices are discovered—drastically affects performance. A sub-optimal schedule can lead to millions of unnecessary set intersections, while an optimal one minimizes the workload. Existing systems often fail to accurately predict which schedule will be the fastest for a specific graph's topology.

Methodology

GraphPi addresses these challenges through a multi-faceted optimization strategy:

  1. 2-Cycle Based Automorphism Elimination: Using group theory, GraphPi identifies "2-cycles" (exchangeable vertex pairs) to generate multiple valid sets of symmetry-breaking restrictions. Unlike prior systems that use a single fixed set, GraphPi can choose the restriction set that best complements a specific search schedule.
  2. 2-Phase Schedule Generation: The system filters the $n!$ possible search orders by first ensuring connectivity in the partial subgraph and then prioritizing vertex placements that minimize expensive intersection operations.
  3. Performance Prediction Model: GraphPi employs a nested cost model using graph metadata (e.g., edge count, triangle density) to estimate the efficiency of various schedule and restriction combinations. This allows the system to pick the most efficient configuration before execution.
  4. Inclusion-Exclusion Principle (IEP): For counting-only tasks, GraphPi applies the IEP to mathematically derive counts for the final vertices, bypassing explicit iteration and providing massive speedups.
Impact of different search schedules and symmetry-breaking restrictions on performance.

Evaluation and Results

The system was evaluated using six real-world datasets, including social networks (LiveJournal, Orkut, Twitter) and citation graphs (Patents).

  • Performance: GraphPi achieved an average speedup of 9.7× to 60.3× over GraphZero, with a peak speedup of 105× on the Wiki-Vote dataset.
  • Counting Optimization: The IEP-based counting method was up to 1110.5× faster than standard listing, turning an $O(N^k)$ problem into a simpler combinatorial calculation.
  • Scalability: On the Tianhe-2A supercomputer, GraphPi demonstrated near-linear scalability up to 1,024 nodes (24,576 cores) using the massive Twitter dataset (1.2 billion edges).

Conclusion

GraphPi demonstrates that effective redundancy elimination through group theory and accurate performance modeling can overcome the traditional bottlenecks of graph pattern matching. While current memory constraints require replicating the data graph on every node, future work will focus on memory-aware partitioning and improved load balancing to handle even larger graphs in highly distributed environments.

Summary updated

Abstract

Graph pattern matching, which aims to discover structural patterns in graphs, is considered one of the most fundamental graph mining problems in many real applications. Despite previous efforts, existing systems face two main challenges. First, inherent symmetry existing in patterns can introduce a large amount of redundant computation. Second, different matching orders for a pattern have significant performance differences and are quite hard to predict. When these factors are mixed, this problem becomes extremely complicated. High efficient pattern matching remains an open problem currently. To address these challenges, we propose GraphPi, a high performance distributed pattern matching system. GraphPi utilizes a new algorithm based on 2-cycles in group theory to generate multiple sets of asymmetric restrictions, where each set can eliminate redundant computation completely. We further design an accurate performance model to determine the optimal matching order and asymmetric restriction set for efficient pattern matching. We evaluate GraphPi on Tianhe-2A supercomputer. Results show that GraphPi outperforms the state-ofthe-art system, by up to 105X for 6 real-world graph datasets on a single node. We also scale GraphPi to 1,024 computing nodes (24,576 cores).
BibTeX
@misc{shi2020graphpi,
  author = {Tianhui Shi and Mingshu Zhai and Yi Xu and Jidong Zhai},
  title = {{GraphPi: High Performance Graph Pattern Matching through Effective Redundancy Elimination}},
  year = {2020},
  eprint = {2009.10955},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.10955},
}
Figure