High-Performance Massive Subgraph Counting using Pipelined Adaptive-Group Communication

Langshi Chen, Bo Peng, Sabra Ossen, Anil Vullikanti, Madhav V. Marathe, Lei Jiang, Judy Qiu

Abstract

Subgraph counting aims to count the number of occurrences of a subgraph $T$ (template) in a given graph $G$. This problem is computationally challenging, with complexity growing as a function of both $T$ and $G$. Recent applications require solving these problems on massive networks with billions of vertices. This paper presents several system-level strategies to substantially improve performance in massive subgraph counting. We propose: 1) a novel pipelined Adaptive-Group communication pattern to improve inter-node scalability, 2) a fine-grained pipeline design to reduce the memory space of intermediate results, and 3) partitioning neighbor lists of subgraph vertices to achieve better thread concurrency and workload balance. Experimentation on an Intel Xeon E5 cluster shows that our implementation achieves a 5x speedup and reduces peak memory utilization by a factor of 2 on large templates (12 to 15 vertices) and input graphs with up to 5 billion edges.

Introduction

Subgraph counting—identifying the frequency of specific small patterns or "motifs" within a large graph—is a foundational task in social network analysis, bioinformatics, and cybersecurity. However, the problem is NP-hard, and as the size of the template or the target graph increases, the computational requirements explode.

Existing parallel solutions typically encounter three major bottlenecks:

  1. Communication Overhead: Large graphs must be partitioned across multiple machines, leading to massive network traffic during connectivity checks.
  2. Memory Constraints: Storing intermediate results for complex templates often exceeds the available RAM in modern clusters.
  3. Load Imbalance: Real-world graphs are often highly skewed, with a few high-degree nodes causing most processors to idle while one struggles with a "heavy" vertex.

Methodology

The framework builds upon the color-coding technique, a randomized approximation algorithm. The core algorithmic approach involves partitioning the template into smaller components and counting colorful embeddings.

Template Partition and Colorful Embedding Counting

To address the system-level bottlenecks, the authors implemented several optimizations within the Harp-DAAL framework:

Pipelined Adaptive-Group Communication

Instead of traditional "all-to-all" communication where nodes wait for a global synchronization, the system breaks communication into discrete steps. This allows for the overlapping of computation and communication; while one data chunk is being transmitted, the CPU processes the previously received chunk. The system adaptively switches between standard all-to-all mode for simple templates and this pipelined mode for high-intensity tasks.

Pipelined Adaptive-Group Communication Steps

Fine-Grained Load Balancing

To mitigate the "skewed node" problem, the system employs neighbor list partitioning. By breaking down the neighbor lists of high-degree vertices into smaller, equal-sized tasks, the workload is distributed evenly across all available CPU threads, preventing idle time.

Experimental Evaluation

The system was evaluated using massive real-world datasets, including Twitter (2B edges) and Friendster (5B edges), alongside synthetic RMAT graphs to test various levels of connectivity skewness. The templates used were tree-like structures (treelets) ranging from 3 to 15 vertices.

Key Results

  • Performance: The "AdaptiveLB" (Load Balance) version achieved up to a 5x speedup over state-of-the-art tools like MPI-Fascia.
  • Memory Efficiency: Peak memory utilization was reduced by 50% on large templates (12–15 vertices), allowing the system to process complex structures that previously caused out-of-memory errors.
  • Scalability: The system successfully handled the Friendster graph (5 billion edges), a scale beyond the reach of many previous algorithms.
  • Thread Efficiency: Neighbor-partitioning improved execution time by up to 9x on highly skewed graphs compared to naive thread distribution.

Conclusion

This work demonstrates that combining algorithmic approximations like color-coding with system-level pipelining and adaptive load balancing can significantly push the boundaries of subgraph counting. While the current focus is on treelets (subgraphs without cycles), the pipelined approach offers a robust foundation for future extensions into more general graph mining tasks and templates with cycles.

Reference: Chen, L., et al. (2018). High-Performance Massive Subgraph Counting using Pipelined Adaptive-Group Communication. arXiv:1804.09764v1 [cs.DC].

Summary updated

Abstract

Subgraph counting aims to count the number of occurrences of a subgraph T (aka as a template) in a given graph G. The basic problem has found applications in diverse domains. The problem is known to be computationally challenging - the complexity grows both as a function of T and G. Recent applications have motivated solving such problems on massive networks with billions of vertices. In this chapter, we study the subgraph counting problem from a parallel computing perspective. We discuss efficient parallel algorithms for approximately resolving subgraph counting problems by using the color-coding technique. We then present several system-level strategies to substantially improve the overall performance of the algorithm in massive subgraph counting problems. We propose: 1) a novel pipelined Adaptive-Group communication pattern to improve inter-node scalability, 2) a fine-grained pipeline design to effectively reduce the memory space of intermediate results, 3) partitioning neighbor lists of subgraph vertices to achieve better thread concurrency and workload balance. Experimentation on an Intel Xeon E5 cluster shows that our implementation achieves 5x speedup of performance compared to the state-of-the-art work while reduces the peak memory utilization by a factor of 2 on large templates of 12 to 15 vertices and input graphs of 2 to 5 billions of edges.
BibTeX
@inproceedings{chen2017high,
  author = {Langshi Chen and Bo Peng and Sabra Ossen and Anil Vullikanti and Madhav V. Marathe and Lei Jiang and Judy Qiu},
  title = {{High-Performance Massive Subgraph Counting using Pipelined Adaptive-Group Communication}},
  booktitle = {TopHPC},
  year = {2017},
  url = {https://openreview.net/forum?id=MAxtiMCqrnd},
}
Figure