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

TL;DR

This paper introduces a high-performance framework for counting subgraphs (motifs) in massive networks with billions of edges. By combining a novel pipelined communication strategy with fine-grained load balancing, the authors achieved a 5x speedup and a 2x reduction in memory usage compared to previous state-of-the-art implementations, successfully scaling to complex templates with up to 15 vertices.

What Problem Does This Paper Address?

Subgraph counting—finding how many times a specific small pattern (like a "treelet") appears in a large graph—is a fundamental task in social network analysis, bioinformatics, and cybersecurity. However, it is computationally "hard" (NP-hard). As the size of the template or the main graph grows, the complexity explodes.

Existing parallel solutions often hit two walls:

  1. Communication Bottlenecks: When a graph is too big for one machine, it must be split. Moving data between machines to check for connections creates massive network overhead.
  2. Memory Footprints: Storing intermediate results for large templates can easily exceed the RAM of modern clusters.
  3. Load Imbalance: Real-world graphs are "skewed" (some nodes have thousands of connections, others have two). Standard parallel approaches often leave most processors idling while one struggles with a "heavy" node.

Methods

The authors build upon the color-coding technique, a randomized approximation algorithm that makes subgraph counting more manageable. Their core contributions are system-level optimizations implemented in the Harp-DAAL framework:

  • Pipelined Adaptive-Group Communication: Instead of a traditional "all-to-all" communication where every machine waits for everyone else, they break communication into steps. This allows the system to "overlap" work: while one part of the data is being sent over the network, the CPU is already processing the previously received chunk.
  • Adaptive Switching: The system automatically chooses between a standard all-to-all mode (for small, simple templates) and the pipelined mode (for large, complex templates) based on the "computation intensity" of the task.
  • Neighbor List Partitioning: To solve the "skewed node" problem, they break down the neighbor lists of high-degree vertices into smaller, equal-sized tasks. This ensures that work is distributed evenly across all CPU threads.

Datasets

The researchers evaluated their system using a mix of massive real-world and synthetic datasets:

  • Real-world: Twitter (2B edges), Friendster (5B edges), Orkut (230M edges), and others like Miami, NYC, and Sk-2005.
  • Synthetic: RMAT graphs (up to 500M edges), specifically used to test how the system handles different levels of "skewness" or irregular connectivity.
  • Templates: Tree-like structures (treelets) ranging from 3 to 15 vertices.

Key Insights and Ideas

  • Computation vs. Communication Intensity: The authors found that the shape of a template matters as much as its size. A 12-vertex template with a specific "bushy" shape might require twice the computation of a "stringy" 12-vertex template. Their system adapts to this "intensity."
  • Hiding Latency: By using a "cold start" pipeline, they effectively hide the time spent waiting for the network. By the time the first communication step finishes, the computation pipeline is full and stays busy.
  • Breaking the Memory Barrier: Previous state-of-the-art tools (like MPI-Fascia) often crashed due to "Out of Memory" errors on templates larger than 12 vertices. This paper’s fine-grained partitioning allows it to process these larger templates by never holding too much intermediate data in RAM at once.

Key Results

  • Speedup: The proposed "AdaptiveLB" (Load Balance) version achieved up to a 5x speedup over MPI-Fascia on large templates.
  • Memory Efficiency: Peak memory utilization was reduced by a factor of 2 on large templates (12–15 vertices).
  • Scalability: The system successfully processed the Friendster graph (0.66 billion vertices and 5 billion edges), a scale that many previous algorithms could not handle.
  • Thread Efficiency: On highly skewed graphs, their neighbor-partitioning technique improved execution time by up to 9x compared to naive thread distribution.

Limitations and Future Work

  • Template Constraints: The current work focuses primarily on "treelets" (subgraphs without cycles). While color-coding can be extended to graphs with cycles (using treewidth), this paper does not deeply explore those more complex structures.
  • Future Directions: The authors suggest applying this pipelined, adaptive approach to other data-intensive irregular graph problems beyond counting, such as finding random subgraphs or more general graph mining tasks.

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},
}

Loading related content...

Figure